c++ - 关联容器的 lower_bound 复杂度 : member function vs non-member function

Question

set 和 map 有 lower_bound(以及 upper_bound 和 equal_range ) 具有 Log(N) 时间复杂度的成员函数。还有非成员 lower_bound 可以通过包含 algorithm header 获得。根据描述，非成员函数的复杂性对于随机访问迭代器是 Log(N)，否则是线性的。 set 和 map 迭代器不是随机访问。这是否意味着我应该避免使用非成员函数？

Answer 1

std::lower_bound旨在用于由一对迭代器定义的排序范围，通常是来自某个容器的 begin 和 end 。如果您将它与来自 std::set 或 std::map 的双向(非随机访问)迭代器一起使用，那么它将必须线性遍历范围，与随机访问迭代器不同。方法 std::set::lower_bound和 std::map::lower_bound存在是因为它可以利用容器的内部结构比其自由功能对应物执行得更好。所以是的，确实，如果可以的话，在使用 std::set 或 std::map 时，您应该喜欢这种方法。