Prefer container::lower_bound to std::lower_bound?

Question

I understand that container::lower_bound harness helpful invariant of the very container hence gives a better performance than std::lower_bound.

Taking std::set::lower_bound as an example, during my own development I found it's about O(logN) as expected for bisection, while std::lower_bound on the same set object deteriorates and the cost falls back to linear time.

I wonder does it mean we should always prefer the lower_bound() or upper_bound() offered by the standard container if there is one? any tradeoff?

Answer 1

Yes, always prefer the container one.

C++ reference notes that you shouldn't use std::lower_bound if the iterator isn't LegacyRandomAccessIterator https://en.cppreference.com/w/cpp/algorithm/lower_bound.html which specifically is the case for set, map, multiset and multimap (it gives O(n) behavior).

As far I can see only the standard containers set, map, multiset and multimap have lower_bound; that is the same list of containers so always prefer the container one.