当我们在向量上使用 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 到 [=12] 给我们的序列=].

通过我自己在纸上画的图，我明白了我们是如何实现从v.begin()到v.last()的序列，而不是上面提到的从v.last()到v.end()的序列。

这里是 reference site.

Answer 1

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

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

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

排除简单情况（0 或 1 长度序列），当要 kept 值时，它在 next[ 中移动分配=43=]插槽在W上面，W是进阶的。不管保留与否，R总是提前的。完成后，插槽 past W 是 last（即剩余插槽中的第一个，其中一些可以具有未指定的值）。

根据您的数据，序列将是这样的：

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

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

_{提示：移动了什么？跳过了什么？什么被覆盖了？为什么这有关系？尝试在任何移动的的读取槽上写入 0 并查看从 last 到 end.[=52 的序列中剩余的内容=]}

Answer 2

独特的算法非常简单。给定范围 [First,Last)，您使用两个迭代器 In 和 Out 来删除连续的重复项。 In 和 Out 最初分配给序列中的第一个元素。

In = Out = First

如果范围不为空，算法将按如下方式进行。

while (++In != Last)
{
    if (*In != *Out)
    {
        ++Out;
        *Out = *In;
    }
}

现在只需继续，直到 In 到达范围的末尾。那我们return++Out.

Out 基本上是一个输出迭代器，将唯一元素写入同一范围，因此我们可以在上述算法完成后通过递增它来检索最后一个迭代器。

如果您不考虑移动而是输出到（并覆盖）相同的范围，那就更容易了。唯一棘手的部分是我们正在覆盖我们正在阅读的相同范围。如果您将唯一元素推回到不同的序列并 returning 该序列，那么掌握该算法会容易得多。现在你只需应用一个小的优化来避免通过覆盖你正在阅读的同一个输出范围来需要一个单独的输出范围。

这是我迅速实现的一个快速实现，它可能比供应商版本更容易理解。它没有一些常见的问题，比如重用 'first' 作为输入迭代器，使用运算符！=（而不是 ! 和 ==）等

template <class Iterator>
Iterator my_unique(Iterator first, Iterator last)
{
    if (first != last)
    {
        Iterator in = first;
        Iterator out = first;
        while (++in != last)
        {
            if (*in != *out)
            {
                ++out;
                *out = *in;
            }
        }
        return ++out;
    }
    return last;
}

当我们在向量上使用 unique 函数时，移位是如何工作的？

How does the shifting work when we use the unique function on a vector?

c++

stl

vector