什么是最有效的方法来判断密钥是否在c ++ unordered_map中？

Question

现在,如果我们说的unordered_map是"mp",我告诉一个键是否在unordered_map中的方法是:

mp.find(key) != mp.end()

但看起来我们必须遍历mp中的所有键.这是正确的吗？

如果有更好的方法来检查密钥是否在unordered_map中？

Answer 1

不,a std::unordered_map是哈希表,std::unordered_map::find平均是恒定时间.您不必遍历所有键.在散列冲突的情况下,桶内可能会有一些顺序查找.

请注意,您也可以使用该count成员,这可以为您节省一个比较:

bool b = mp.count(key);

这是否更"高效"应该通过剖析来确定.

C++11§23.2.5/ 10表103(来自N3290):
b.find(k)...平均情况O(1),最差情况O(b.size()).