对 std::unique 实施感到困惑？

Question

根据this article，std::unique的一种可能实现是

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;
}

但是，我不明白迭代器比较的用途是什么？为什么 if (!(*result == *first) && ++result != first) 而不仅仅是 if (!(*result++ == *first))？比较两个迭代器的目的是什么？

Answer 1

如果您这样做 if(!(*result++ == *first))，您的条件总是会增加 result。但是，如果 !(*result == *first) 为假，条件的第二部分由于短路评估而永远不会被评估。

差异对 "unique" 的含义至关重要。

Answer 2

让我们将代码重写为更小的步骤（代码等同于问题中的代码 - 我只是将 if 语句拆分为两个单独的部分）：

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;
}

这是一个例子：

result
   v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  2  |  3  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
   ^                                               ^
 first                                           last

第 1 步 - 首先递增并将 first 的值与结果的值进行比较：

result
   v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  2  |  3  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
         ^                                         ^
       first                                      last

第 2 步 - 值不同，因此增加结果，但现在它们指向同一个地方，因此移动是多余的，我们不这样做

      result
         v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  2  |  3  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
         ^                                         ^
       first                                      last

第 3 步 - 首先递增并将 first 的值与结果的值进行比较：

      result
         v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  2  |  3  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
               ^                                   ^
             first                                last

第 4 步 - 值相同，因此重新开始循环（首先递增并将 first 的值与 result 的值进行比较）：

      result
         v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  2  |  3  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                     ^                             ^
                   first                          last

第 5 步 - 值不同，因此增加结果，它们指向不同的位置，因此将 first 的值移动到 result 的值中：

            result
               v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  3  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                     ^                             ^
                   first                          last

第 6 步 - 先递增并将 first 的值与 result 的值进行比较：

            result
               v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  3  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                           ^                       ^
                         first                    last

第 7 步 - 值不同，因此增加结果，它们指向不同的位置，因此将 first 的值移动到 result 的值中：

                  result
                     v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                           ^                       ^
                         first                    last

第 8 步 - 先自增并将 first 的值与 result 的值进行比较：

                  result
                     v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                                 ^                 ^
                               first              last

第 9 步 - 值相同，因此重新开始循环（首先递增并将 first 的值与 result 的值进行比较）：

                  result
                     v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                                       ^           ^
                                     first        last

第 10 步 - 值相同，因此重新启动循环（首先递增并将 first 的值与 result 的值进行比较）：

                  result
                     v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  4  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                                             ^     ^
                                           first  last

第 11 步 - 值不同，因此增加结果，它们指向不同的位置，因此将 first 的值移动到 result 的值中：

                        result
                           v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                                             ^      ^
                                           first   last

第 12 步 - 首先递增，while 循环结束，因为第一个和最后一个指向同一个地方 - 然后在循环递增结果之后，它成为唯一范围的新结束迭代器：

                              result
                                 v
+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |  4  |  4  |  5  |
+-----+-----+-----+-----+-----+-----+-----+-----+
                                                    ^
                                                last&first

Answer 3

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

可以改写为

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;

对 std::unique 实施感到困惑？

Confusion about std::unique implementation?

c++

stl

stl-algorithm