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

我有一堆数据充满重复项，我想消除重复项。你知道，例如[1，1，3，5，5，5，7]变成[1,3,5,7]。C++ std :: map或std :: set - 高效地插入重复项

它看起来像我可以使用std :: map或std :: set来处理这个。然而，我不确定（a）是简单地将所有值插入到容器中，还是（b）检查它们是否已经存在于容器中，并且只在插入时才插入 - 插入是否非常有效？即使有更好的方法......你能建议一个快速的方法来做到这一点吗？

另一个问题 - 如果我在其中存储的数据不像整数那样微不足道，而是一个自定义类，那么std :: map如何设法正确地存储（散列？）数据以便快速通过操作员[]访问？

来源

2012-10-10 Gigi

'set'会更合适，因为您不需要每个元素的关联值。我猜测检查然后插入到集合中会比插入要慢，因为你必须在前者中进行两个关键查找。 – GWW

按照定义，在执行插入操作时，其中的任何一个都会为您*检查。即他们会用别的容器来做你想做的事情：检查是否存在。就我个人而言，除非你故意将某些东西映射到其他东西，否则我会与该集合一起使用。 – WhozCraig

数据是否总是排序？因为它看起来像你想[std :: unique]（http://msdn.microsoft.com/en-us/library/9f5eztca（v = vs.100）.aspx），而不是一个新的容器 –

std::map不使用哈希。 std::unordered_map确实，但那是C++ 11。 std::map和std::set都使用您提供的比较器。类模板具有此比较器的默认值，归结为operator<比较，但您可以提供自己的比较。

如果你不需要存储一个密钥和一个值（看起来像你没有），你应该只使用std::set，因为这样更合适。

该标准没有说明什么数据结构map s和set在引擎盖下使用，只有certian行为有一定的时间复杂性。实际上，我知道的大多数实现都使用树。

这没有什么区别时，复杂性，明智的，如果你使用operator[]或insert，但我会用insert或operator[]我做了search后跟insert之前，如果没有找到该项目。后者意味着两个单独的搜索将一个项目插入到该集合中。据我所知，

来源

2012-10-10 19:01:22

假设针对std::map和std::set（即平衡二叉搜索树）的通用实现策略，插入和查找都必须进行树遍历以找到密钥应该在的位置。因此插入后失败的查找速度大概是插入速度的两倍。

std :: map如何正确存储（散列？）数据以便通过运算符[]快速访问？

通过您指定的比较函数（或std::less，如果您在自定义类型上重载operator<时适用）。在任何情况下，std::map和std::set都是而不是哈希表。

来源

2012-10-10 18:59:19

任何相关容器上的insert()都会执行find()以查看该对象是否存在，然后插入该对象。只需将元素插入到std::set<T>中即可合理有效地消除重复项。

根据您设定的大小和重复的重复值的比率，它可以更快地把对象变成std::vector<T>，std::sort()那么，再一起使用std::unique()与std::vector<T>::erase()摆脱重复的。

来源

2012-10-10 19:00:18

*“'insert（）'[...]做一个'find（）'[但是如果找不到]插入...”* - 可能会采用'find（）'的代码风格格式由一些读者调用find（）API调用，而'insert（x）'实现不会在字面上使用'.find（x）'，因为当不存在时，没有（迭代器）的记录，搜索被放弃，这是跳过另一个O（logN）树traveral为实际插入所需。你可以用'lower_bound'关闭，然后用迭代器'hint'重载'insert'，但是'insert'实现将在内部处理这个操作以获得最佳性能。 –

你应该做几次？

如果刀片是平常：

//*/ 
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

来源

2012-10-10 19:00:19 Naszta

std::set和std::map都实现为红黑树。可能只使用插入会更快（然后两者，因为你会加倍查找时间）。

另外map和set使用operator <。只要你的班级已经定义了operator <它将能够使用它们作为键。

来源

2012-10-10 19:01:41 tozka

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

回答

相关问题