如何高效地在向量中删除重复元素

Question

我有

 vector<string> data ; // I hold some usernames in it

在这个向量中，我有重复的元素，所以我想要删除这些元素。是否有任何算法或库函数可以删除重复的元素？

ex :
    In data;
           abba, abraham, edie, Abba, edie
    After operation;
           abba, abraham, edie, Abba

- user478571

---

元素的相对顺序重要吗？也就是说，在操作过程中，您是否关心元素被重新排列，还是希望获得完全相同顺序的序列？ - Matthieu M.

Answer 1

如果你可以对容器中的元素进行排序，那么一个直观且相对高效的解决方案是：

std::sort(data.begin(), data.end());
data.erase(std::unique(data.begin(), data.end()), data.end());

- James McNellis

---

在这里使用stable_sort会不会更好呢？ - Naveen

为什么需要稳定排序呢？如果你只是想删除重复项，那么等价元素的相对位置显然并不重要。 - James McNellis

除非您特别想保留等价组的第一个出现，否则请仅返回已翻译的文本。 - Matthieu M.

Answer 2

我不确定有一个真正好的方法来做到这一点。 我会先排序（如果您需要原始数据保持不变，则在另一个数组中），然后再运行它。

- Elad Lachmi

Answer 3

"set" 不允许重复。您可以使用它来过滤掉重复项。

1. 创建一个集合
2. 将所有用户名添加到集合中
3. 创建一个新的向量
4. 将集合中的所有元素添加到向量中

- Shamit Verma

---

但这样做将无法保留vector中的顺序。 - Naveen

是的，它不会。如果您想保留顺序，则复杂度将增加。基本上创建一个新向量，对于现有向量中的每个项目：{如果它存在于集合中，则不执行任何操作；否则将其添加到集合并添加到目标向量}。 - Shamit Verma

Answer 4

如果你真的需要高效地完成它，那么应该先进行原地排序，然后自己遍历容器，而不是使用std::unique，将唯一项提取到一个新向量中，在最后进行交换。

我刚刚检查了std::unique的源代码，发现它在找到一个重复项时会进行大量移动操作，这会损害向量的性能。

- Shuo

---

std::unique 应该只需要对排序后的序列进行一次遍历。你所说的“当找到一个重复项时，它会执行很多移动操作”是什么意思？ - James McNellis

这是一次遍历，但每次找到重复项时，需要将其移动到末尾。0 1 1 2 2 3 -> 0 1 2 2 3 1 -> 0 1 2 3 1 2。 - Shuo