c++ - vector 与集合的搜索性能

Question

在阅读了以下内容的几个问题和答案之后:

Look up in a set is asymptotically faster than in a vector. (Since a set is basically a binary search tree ). For the task at hand, set is faster than vector because it keeps its contents sorted and does a binary search to find a specified item, giving logarithmic complexity instead of linear complexity.

我的问题是 - 使用二进制搜索在排序 vector 中搜索元素是否与在集合中搜索元素花费相同的时间？如果不是，那么性能差异背后的原因是什么？

Answer 1

如果你能保持 vector 排序，使用std::lower_bound ,搜索是 O(lg(n))对彼此而言。需要注意的是 std::vector享有更好的位置，等等机器，将有一个明显较低的常数因子。它也可能导致更有效的内存使用，由于较少碎片——如果你知道前面的最大尺寸，可以使用 std::vector<>::reserve .