为何std::find在std::unordered_set中查找耗时比std::vector更长？

你出现测试结果不符合预期的核心原因是调用了错误的查找接口：

• 你使用的是通用算法std::find()，该函数对所有输入迭代器都执行顺序遍历匹配，时间复杂度固定为O(n)，完全无法用到std::unordered_set的哈希表O(1)查找、std::set的红黑树O(logn)查找特性。
• std::unordered_set是非连续的链表式存储结构，迭代器遍历的缓存命中率远低于连续内存存储的std::vector，所以顺序遍历查找的耗时反而比std::vector更高，和你得到的测试结果完全吻合。

将std::unordered_set和std::set的查找逻辑替换为容器自带的成员find()方法即可，修改后的查找代码如下：

// lookup time for unordered_set<int>
begin = chrono::steady_clock::now();
for(int i = 0; i < size; i++)
{
  unsetInt.find(i); // 替换为成员find，O(1)时间复杂度
}
end = chrono::steady_clock::now();
cout << "lookup time for unordered_set<int>: " << 
chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;

// lookup time for set<int>
begin = chrono::steady_clock::now();
for(int i = 0; i < size; i++)
{
  setInt.find(i); // 替换为成员find，O(logn)时间复杂度
}
end = chrono::steady_clock::now();
cout << "lookup time for set<int>: " << 
chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;

• 测试时请开启编译器O2优化，Debug模式下的STL容器会带大量调试检查，耗时数据没有参考价值
• 可以将测试规模放大到10万、100万级别，此时三种容器的耗时差异会更明显：std::vector的查找耗时会随数据量线性上涨，std::unordered_set的耗时基本保持稳定，std::set的耗时随数据量对数级上涨。

内容的提问来源于stack exchange，提问作者Ielixmar