Confusion about std::unique implementation?

Question

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?

Answer 1

ForwardIt result = first;
while (++first != last) {
    if (!(*result == *first) && ++result != first) {
        *result = std::move(*first);
    }
}
return ++result;

can be rewritten as

ForwardIt result = first;

// result is the last element different from previous values
// all the equal elements after result=first are useless
// *result = *first
// first is the last element examined

// determine largest range of useless elements

// *result = before(*first) 
// i.e. result has the value of former value (before call) of element *first (current value of first)
// so first is the last element on which we know something

extend_useless_range: 
    // so range ]result,first] is useless 
    first++;
    // now range ]result,first[ is useless 
    // and first is the first element yet to be examined

    if (first == last) {
         // ]result,last[ is useless 
         goto end_loop;
    }
    if (*result == *first) {
         // *first is useless
         // so range ]result,first] is useless 
         goto extend_useless_range;
    }
    // *first is useful

    // range ]result,first[ is biggest useless range after result
    result++; 
    // range [result,first[ is useless (and *first is useful)

    if (result != first) {
        // [result,first[ is nonempty
        *result = std::move(*first);
        // *result is useful and *first is useless (undetermined value)
        // ]result,first] is useless
    }
    else {
        // [result,first[ = ]result,first] = {} and is useless
    }
    // ]result,first] is useless
    goto extend_useless_range;

end_loop: // ]result,last[ is useless 
    result++; 
    // [result,last[ is useless 
    return result;

Answer 2

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

Answer 3

If you do if(!(*result++ == *first)) you always increment result in your condition. But if !(*result == *first) is false, the second part of the condition never gets evaluated thanks to short-circuit evaluation.

The difference is critical to the meaning of "unique".