c++ - 搜索 std::set 的最佳方式

Question

当速度是他/她的项目的关键标准时，应该如何搜索 std::set？

set:find ？

复杂度:

大小为对数。

std::binary_search ？

复杂度:

平均而言，第一个和最后一个之间的距离为对数:执行大约 log2(N)+2 个元素比较(其中 N 是此距离)。在非随机访问的迭代器上，迭代器的进步给自己带来了平均 N 的额外线性复杂度。

只是他/她执行的二进制搜索(如 this 一个)？还是 STL 的就足够了？

有没有办法从理论上回答这个问题？还是我们必须自己测试？如果有人有，如果他能与我们分享这些信息就太好了(如果没有，我们并不懒惰 :))。

Answer 1

std::set 提供的迭代器类型是 bidirectional_iterator ，一个不需要随机访问元素的类别，而只需要在两个方向上逐元素移动。所有 random_access_iterator 都是 bidirectional_iterator，但反之则不然。

因此，根据您引用的评论，在 std::set 上使用 std::binary_search 可以产生 O(n) 运行时，而 std::set::find 保证了 O(logn)。

因此要搜索集合，请使用set::find。