c++ - 当我们在 vector 上使用 unique 函数时，移位是如何工作的？

Question

所以，我目前正在阅读一些 c++ 的东西，我在 cppreference 上看到了这个例子，但我不明白转变是如何工作的。

#include <iostream>
#include <algorithm>
#include <vector>

int main() 
{
    std::vector<int> v{1, 2, 2, 2, 3, 3, 2, 2, 1};
    std::vector<int>::iterator last;

    last = std::unique(v.begin(), v.end()); // 1 2 3 2 1 3 2 2 1
                                            //           ^
    for (std::vector<int>::iterator it = v.begin(); it != last; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
}

我知道当我们使用 unique 时它会改变事情，但是我不确定我们如何获得从 last 到 v 给我们的序列。结束()。

通过我自己在纸上的绘图，我了解我们如何实现从 v.begin() 到 v.last() 的序列，但不是 的序列>v.last() 到 v.end() 如前所述。

这是 reference site .

Answer 1

std:unique 实际上只是根据需要将元素移到开头。这种转变并不像你想象的那样。它不需要是某种传播的一次一个元素的东西。它可以利用元素必须可移动分配 的要求。根据移动赋值的定义，一旦元素被移动，其先前的内容是未指定的。在您的情况下，它只是将“值”保留在那里，但它不是指定值。

简而言之，您看到的是剩余值，其中一些可能是非特定。

以下是使用您的数据的简单演示。最初我们有两个插槽位置，R 和一个 W。我不保证这是 std::unique 使用的 算法(老实说我不知道​​)。

简单情况下(0 或 1 长度的序列)，当要保留一个值时，它被移动分配到 W 上方的下一个槽中, W 是先进的。不管保留与否，R总是提前的。完成后，槽 过去 W 是最后(即剩余槽的第一个，其中一些可以具有未指定的值)。

给定您的数据，序列将是这样的:

1, 2, 2, 2, 3, 3, 2, 2, 1 - different, since the write target
W  R                        is the same as the read-point, do nothing,
                            and advance both R and W

1, 2, 2, 2, 3, 3, 2, 2, 1 - equivalent, advance R only
   W  R                     

1, 2, 2, 2, 3, 3, 2, 2, 1 - equivalent, advance R only
   W     R                     

1, 2, 2, 2, 3, 3, 2, 2, 1 - different, move the 3 to the next write
   W        R               point and advance both R and W

1, 2, 3, 2, 3, 3, 2, 2, 1 - equivalent, advance R only
      W        R

1, 2, 3, 2, 3, 3, 2, 2, 1 - different, move the 2 to the next write
      W           R         slot and advance both R and W

1, 2, 3, 2, 3, 3, 2, 2, 1 - equivalent, advance R only
         W           R      

1, 2, 3, 2, 3, 3, 2, 2, 1 - different, move the 1 to the next write
         W              R   slot and advance both R and W

1, 2, 3, 2, 1, 3, 2, 2, 1 - read is at end-of-sequence
            W             R 

至此，读者阅读完毕。随着算法的进行，W 之后的第一个槽位是 last(如果原始序列没有重复，则可能确实是 end)。我留给你的挑战是在完成此操作后确定哪些元素 (3,2,2,1) 处于“未指定”状态。

_{提示:什么被移动了？跳过了什么？什么被覆盖了？为什么这有关系？尝试在任何移动的读取槽上写入0，然后查看从last到end .}