C++ std::map 或 std::set - 高效插入重复项

Question

我有一堆数据，里面有很多重复的元素，我想要去除这些重复的元素，例如 [1, 1, 3, 5, 5, 5, 7] 变成 [1, 3, 5, 7]。

看起来我可以使用 std::map 或者 std::set 来处理这个问题。但是我不确定哪种方法更快：（a）将所有值都插入到容器中，或者（b）检查它们是否已经存在于容器中，只有在不存在时才进行插入 - 插入操作非常高效吗？即使有更好的方法...你能否建议一种快速的方法来完成这个任务？

另一个问题 - 如果我存储在容器中的数据不像整数那么简单，而是一个自定义类，那么 std::map 是如何正确存储（哈希？）数据以通过 operator[] 进行快速访问的？

- Gigi

---

一个 set 更适合，因为你不需要每个元素都有关联的值。我猜查找并插入到集合中会比直接插入慢，因为在前者中你实际上需要进行两次键查找。 - GWW

按照定义，它们中的任何一个在执行插入操作时都会为您检查。换句话说，它们将执行您用其他容器进行的操作：检查是否存在。个人建议使用set，除非您有意将某些东西映射到其他东西上。 - WhozCraig

数据是否总是已排序？因为看起来你想要使用std::unique，而不是一个新的容器。 - Mooing Duck

不，它没有排序。但是我需要一个容器来从原始数据集中返回结果（我必须保持其完整性）。 - Gigi

感谢大家的回答。不幸的是，我不能将它们全部标记。 :) - Gigi

Answer 1

std::map 不使用哈希，而 std::unordered_map 使用哈希，但这是 C++11 的功能。 std::map 和 std::set 都使用你提供的比较器(comparator)。类模板有默认的比较器，它将归结为一个 operator< 比较，但你可以自己提供。

如果你不需要存储键值对（看起来你不需要），你应该使用std::set，因为那更合适。

标准并未说明 map 和 set 在底层使用什么数据结构，只说明了某些操作的时间复杂度。实际上，我知道的大多数实现都使用树(Tree)。

在时间复杂度方面使用 operator[] 或 insert 没有任何区别，但如果项目未找到，则我会首先使用 insert 或 operator[] ，而不是先进行一次搜索，然后再进行插入。后者意味着要进行两个单独的搜索才能将一个项目插入到集合中。

- John Dibling

Answer 2

在任何一个相关的容器上进行insert()操作时都会执行find()来查看对象是否存在，然后插入该对象。将元素简单地插入到std::set<T>中可以有效地去除重复项。

根据您的集合大小及重复值与唯一值的比率，将对象放入std::vector<T>中，使用std::sort()进行排序，然后结合使用std::unique()和std::vector<T>::erase()来去除重复值可能更快。

- Dietmar Kühl

---

"insert() [...] 做了一个 find() [但如果没有找到] 就插入..." - 在这里，find() 的代码格式可能会被一些读者误认为是对 find() API 调用的调用，而 insert(x) 实现不会字面上使用 .find(x)，因为当没有找到时，没有记录（迭代器）搜索被放弃的位置，这是需要跳过另一个 O(logN) 树遍历以进行实际插入的。你可以通过使用迭代器 "hint" 的 lower_bound，然后使用 insert 重载来接近，但是 insert 实现将在内部处理此操作以获得最佳性能。 - Tony Delroy

Answer 3

你需要执行多少次？

如果插入是常见操作：

//*/
std::set<int> store;
/*/
// for hash:
std::unordered_set<int> store;
//*/
int number;

if ( store.insert(number).second )
{
  // was not in store
}

如果您只填写一次：

std::vector<int> store;
int number;

store.push_back(number);
std::sort(store.begin(),store.end());
store.erase(std::unique(store.begin(),store.end()),store.end() );

// elements are unique

- Naszta

Answer 4

假设对于 std::map 和 std::set 的常见实现策略，即平衡二叉搜索树，插入和查找都必须进行树遍历以找到应该放置键的位置。因此，失败的查找后跟插入将大约比仅插入慢两倍。

std::map 如何正确存储（哈希？）数据以通过 operator[] 进行快速访问？

通过您指定的比较函数（或 std::less，如果在自定义类型上重载了 operator<）。无论如何，std::map 和 std::set 都不是哈希表。

- Fred Foo

Answer 5

std::set和std::map据我所知都是用红黑树实现的。也许只使用插入操作会更快（因为这样可以减少查找时间）。

此外，map和set使用operator <。只要你的类定义了operator <，就可以将其作为键来使用。

- tozka