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?

Hans Olsson · Accepted Answer · 2025-08-13 16:12:00Z

12

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.

edited Aug 13 at 16:12

answered Aug 13 at 16:03

Hans Olsson

13k22 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

許恩嘉 Aug 13 at 16:09

You MUST use the same predicate, otherwise the lower_bound prerequisites are not met.

Caleth Aug 13 at 16:13

Not quite. [](int lhs, int rhs) { return (lhs / 10) < (rhs / 10); } is a valid compare argument for std::lower_bound applied to a std::set<int>, because it's never inconsistent with the ordering of the set.

Caleth Aug 13 at 16:10

the container lower_bounds don't have a compare parameter, they always use the container's comparison.

Hans Olsson Aug 13 at 16:16

I removed the part about want lower bound for the same predicate as the container, since it was a minor footnote that attracted too much problems.

Ted Lyngmo Aug 13 at 21:22

@Caleth Nitpick: std::set<int> foo{1, 2, 3}; - With [](int lhs, int rhs) { return (lhs / 10) < (rhs / 10); } it will return false for every comparison in contrast to what the comparator used by the std::set<int> will return. :)

Caleth Aug 14 at 8:14

Yes, and that's fine. std::lower_bound will find the first element of the equivalence group. It even works with the compares flipped, but not for multi_set

Ted Lyngmo Aug 14 at 8:30

@Caleth Ah... you're right. I wasn't restricting my thought to lower_bound specifically. :)

463035818_is_not_an_ai · Accepted Answer · 2025-08-14 08:45:09Z

Yes, as you already mentioned, the container offers a container::foo when it can be implemented more efficiently than the generic foo. Note that the latter is agnostic of the underlying container, you either use iterators or a ranges view, hence it cannot use knowledge of the containers internals as container::foo can. Though, when calling code is aware of the type of the container, as eg in

template <typename container> void bar(container& c) { // do something that requires lower_bound }

then the trade off is to write code to call container::lower_bound when it exists, and the generic algorithm otherwise, or just call the generic algorithm always at the expense of possibly worse runtime.

Collectives™ on Stack Overflow

Prefer container::lower_bound to std::lower_bound?

2 Answers 2

7 Comments

Comments

Hot Network Questions