对于非重复项目,最有效的std容器是什么？

Question

将非重复元素添加到STL容器中的最有效方法是什么,哪种容器最快？我有大量的数据,我担心每次尝试检查它是否是新元素时,都需要花费很多时间.我希望地图非常快.

// 1- Map
map<int, int> Map;
...
if(Map.find(Element)!=Map.end()) Map[Element]=ID;

// 2-Vector
vector<int> Vec;
...
if(find(Vec.begin(), Vec.end(), Element)!=Vec.end()) Vec.push_back(Element);

// 3-Set
// Edit: I made a mistake: set::find is O(LogN) not O(N)

Answer 1

双方set并map具有O(log(N))用于查找键性能.vector有O(N).

对于您是否需要将键与值关联,或者只是直接存储值,您set和它之间的区别map是.如果你需要前者,使用a map,如果需要后者,请使用a set.

在这两种情况下,你应该使用insert()而不是做一个find().

原因是insert(),当且仅当容器尚未包含该值时(例如map,如果容器不包含该键),将值插入容器中.这可能看起来像

Map.insert(std::make_pair(Element, ID));

对于地图或

Set.insert(Element);

一套.

您可以查阅返回值以确定是否实际执行了插入.

如果你正在使用C++ 11,你还有两个选择,它们是std::unordered_map和std::unordered_set.这两者都具有O(1)用于插入和查找的摊销性能.但是,它们还要求密钥(或者在设置的情况下的值)是可以清洗的,这意味着您需要专门std::hash<>设置密钥.相反,std::map并std::set要求您的密钥(或值,在集合的情况下)响应operator<().

Answer 2

如果您使用的是C++ 11,则可以使用std::unordered_set.这将允许你O(1)存在检查(技术上摊销O(1)- O(n)在最坏的情况下).

std::set可能是你的第二选择O(lg n).

基本上,std::unordered_set是一个哈希表,std::set是一个树形结构(在我见过的每个实现中都是一个红黑树)¹.

根据您的哈希分布的程度以及您拥有的项目数量,std :: set实际上可能更快.如果它真的对性能至关重要,那么一如既往,您将需要进行基准测试.

^{1)从技术上讲,我不认为要么将其实现为哈希表,要么实现平衡的BST.如果我没记错的话,标准只是强制执行运行时限,而不是实现 - 它只是证明那些是唯一适合边界的可行实现.}