According to this article, one possible implementation of std::unique is
template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last)
{
if (first == last)
return last;
ForwardIt result = first;
while (++first != last) {
if (!(*result == *first) && ++result != first) {
*result = std::move(*first);
}
}
return ++result;
}
However, I do not get what the iterator comparison is for? Why if (!(*result == *first) && ++result != first) and not just if (!(*result++ == *first))? What is the purpose of comparing the two iterators?
Let's rewrite the code into smaller steps (the code is equivalent to the one in the question - I've just split the if statement into two separate parts):
template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last)
{
// are there elements to test?
if (first == last)
return last;
// there are elements so point result to the first one
ForwardIt result = first;
// then increment first and check if we are done
while (++first != last) {
// if the value of first is still the same as the value of result
// then restart the loop (incrementing first and checking if we are done)
// Notice that result isn't moved until the values differ
if (*result == *first)
continue;
// increment result and move the value of first to this new spot
// as long as they don't point to the same place
// So result is only moved when first points to a new (different) value
if (++result != first) {
*result = std::move(*first);
}
}
// return one past the end of the new (possibly shorter) range.
return ++result;
}
Here is an example:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 2 | 3 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 1 - increment first and compare the value of first with the value of result:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 2 | 3 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 2 - the values differ so increment result but now they point to the same place so moving is superfluous and we don't do it
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 2 | 3 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 3 - increment first and compare the value of first with the value of result:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 2 | 3 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 4 - the values are the same so restart the loop (incrementing first and comparing the value of first with the value of result):
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 2 | 3 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 5 - the values differ so increment result, they point to different places so moving the value of first into the value of result:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 3 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 6 - increment first and compare the value of first with the value of result:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 3 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 7 - the values differ so increment result, they point to different places so moving the value of first into the value of result:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 8 - increment first and compare the value of first with the value of result:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 9 - the values are the same so restart the loop (incrementing first and comparing the value of first with the value of result):
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 10 - the values are the same so restart the loop (incrementing first and comparing the value of first with the value of result):
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 11 - the values differ so increment result, they point to different places so moving the value of first into the value of result:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^ ^
first last
Step 12 - increment first and the while loop ends because first and last point to the same place - then after the loop increment result so it becomes the new end iterator for the unique range:
result
v
+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 | 4 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+-----+-----+
^
last&first