set和map具有lower_bound(以及upper_bound和equal_range)成员函数,具有Log(N)时间复杂度.还有非成员lower_bound,可通过包含算法头来获得.根据描述,非成员函数的复杂性是随机访问迭代器的Log(N),否则是线性的.set和map迭代器不是随机访问.这是否意味着我应该避免非会员职能？
std::lower_bound意要在由一对迭代,典型的所定义的排序的范围内使用begin,并end从一些容器.如果将它与来自std::set或的双向(非随机访问)迭代器一起使用std::map,那么它将不得不线性地遍历该范围,这与随机访问迭代器不同.这种方法std::set::lower_bound和std::map::lower_bound存在是因为它可以利用容器的内部结构比其自由功能对应物更好地执行.所以是的,的确,你应该在使用时使用这种方法,std::set或者std::map,如果可以的话.