如何从向量中删除重复元素？

Question

因此，我有一个std::vector<type>。

类类型没有operator<，但有operator==。 因此，我不能使用std::unique对向量进行排序。

我该如何从向量中删除重复元素？

- Eduard Rostomyan

---

如果不排序，你很难高效地完成这个任务。如果没有排序功能，无序状态将使你直接进入O(N^2)的领域。 - WhozCraig

@WhozCraig：不一定，如果你能够快速生成一个完美的哈希表，那么你可以在O(N)时间内完成它。 - Matthieu M.

@MatthieuM。如果您可以提供一个完美的哈希，那么为什么一开始不使用std::unordered_set而是使用无序向量？我基于我们唯一能够使用的信息——OP提供的信息来做出这个判断。如果他们有一个合理的哈希（完美或不完美），那么这个问题中的X就是“为什么我在使用错误的容器？”显然，我不能说在这样的哈希下它不起作用；它肯定会起作用。 - WhozCraig

实际上，在这种情况下，我应该找出我的容器是否包含重复的元素，并在删除它们之后进行操作。 - Eduard Rostomyan

@WhozCraig：也许是因为序列顺序很重要？也许是因为vector对于通用操作更有效率？我不知道，我不是OP。 - Matthieu M.

@EduardRostomyan 由于这个问题已经关闭，我无法提供一个完美的解决方案。鉴于您提出的限制条件，这个可能是您想要的。它应该可以满足您的限制条件，只使用operator ==进行相等比较，尽管我只在简单的标量类型上进行了测试。无论如何，我希望它能对您有所帮助。祝您好运。 - WhozCraig

Answer 1

我认为最好的选择是编写一些二进制谓词来用于向量排序，然后使用 std::unique。请记住，谓词必须是可传递的！

如果这不是一个选项，您只能使用二次算法：

std::vector<type> a
std::vector<type> result;
for (unsigned i = 0; i < a.size(); ++i) {
  bool repeated = false;
  for (int j = 0; j < i; ++j) {
    if (a[j] == a[i]) {
      repeated = true;
      break;
    }
  }
  if (!repeated) {
    result.push_back(a[i]);
  }
}

// result stores the unique elements.

- Ivaylo Strandjev