c++ - 为什么对排序 vector 的二分查找比 std::set 查找慢？

Question

在这里您可以看到代码，运行它并查看时间。

http://rextester.com/MNQZS47293

我在我的机器上得到了类似的结果(使用相同版本的 MSVC)， vector 中的查找比 std::set 中的查找慢。

由于数据的局部性更好(缓存更友好)，我希望排序后的 vector 版本更快。在最坏的情况下，我希望它们是相似的，因为它们都执行二进制搜索，但我不明白为什么 std::set 比排序的 vector 版本快得多。

非常感谢

编辑:抱歉，我贴错链接了(我修改了代码但是忘了复制链接)旧代码使用的是unordered_set，这段代码使用的是set，问题还是一样:为什么二进制搜索排序 vector 比搜索集合慢？我注意到，如果元素的数量足够大，那么排序的 vector 会更快，但我仍然不明白为什么对于任意数量的元素，集合的性能都优于排序的 vector 。

Answer 1

链接的代码似乎使用了 unordered_set，而不是 set。

unordered_set 是一个哈希表。那里的搜索不是二分搜索。在那里，搜索性能取决于哈希函数和负载因子。