Gig*_*igi 7 c++ performance stdmap stdset
我有一堆完整的重复数据,我想消除重复.你知道,例如[1,1,3,5,5,5,7]变成[1,3,5,7].
看起来我可以使用std :: map或std :: set来处理这个问题.但是我不确定(a)是否只是将所有值插入容器中,或者(b)检查它们是否已经存在于容器中并且仅在它们不存在时插入 - 是否插入非常有效？即使有更好的方法......你能建议一个快速的方法吗？
另一个问题 - 如果我存储在其中的数据不像整数那么简单,而是一个自定义类,std :: map如何管理以正确存储(哈希？)数据以便通过运算符快速访问[ ]？
Joh*_*ing 11
std::map不使用散列. std::unordered_map是的,但这是C++ 11. std::map并且std::set都使用您提供的比较器.类模板具有此比较器的默认值,可归结为operator<比较,但您可以提供自己的比较器.
如果你不需要存储一个键和一个值(看起来你没有),你应该只使用一个std::set,因为这更合适.
标准没有说明什么数据结构map和sets使用在引擎盖下,只有certian行为具有一定的时间复杂性.实际上,我所知道的大多数实现都使用树.
如果你使用operator[]或者它没有时间复杂性insert,但我会使用insert或operator[]之前我做了一个search后跟一个insert如果没有找到该项.后者意味着两个单独的搜索将项目插入到集合中.
一个insert()上的任何相关联的容器的不一find(),以查看是否该对象存在,然后插入的对象.简单地将元素插入到一个std::set<T>应该合理有效地摆脱重复.
根据您的集合的大小以及重复项与唯一值的比率,将对象放入其中可能会更快std::vector<T>,std::sort()然后std::unique()一起使用std::vector<T>::erase()以消除重复项.