C++ Difference between std::lower_bound and std::set::lower_bound?

Question

Recently, while working on a programming problem in C++, I came across something interesting. My algorithm used a really large set and would use std::lower_bound on it a great deal of times. However, after submitting my solution, contrary to the math I did on paper to prove that my code was fast enough, it ended up being far too slow. The code looked something like this:

using namespace std;

set<int> s;
int x;

//code code code

set<int>::iterator it = lower_bound(s.begin(),s.end(),x);

However, after getting a hint from a buddy to use set::lower_bound, the algorithm in question worked waaaaaaaay faster than before, and it followed my math. The binary search after changing:

set<int>::iterator it = s.lower_bound(x);

My question is what's the difference between these two? Why does one work much, much faster than the other? Isn't lower_bound supposed to be a binary search function that has the complexity O(log2(n))? In my code it ended up being way slower than that.

If this was some sort of contest problem, be aware that you will always want to take advantage of the lower_bound found in set rather than the generic one (which will almost always be slower) — ra1nmaster, Aug 05 '15 at 01:34
Possible duplicate of [Why two seemingly lower\_bound() same method has different processing time](http://stackoverflow.com/questions/34922113/why-two-seemingly-lower-bound-same-method-has-different-processing-time) — RiaD, Jan 24 '16 at 15:58

Ryan Haining · Accepted Answer · 2022-06-08T16:54:11.460

std::set is typically implemented as a self-balancing tree with some list-like structure tied into it. Knowing this structure, std::set::lower_bound will traverse the tree knowing the properties of the tree structure. Each step in this just means following a left or right child branch.

std::lower_bound needs to run something akin to a binary search over the data. However since std::set::iterator is bidirectional (not random access), this is much slower, a lot of increments need to be done between the checked elements. The work done between elements is thus much more intense. In this case the algorithm will check the element half way between A and B, then adjust one of A or B, find the element half way between them, and repeat.

Oh I see, thanks for explaining it to me everyone. I'll remember to always use the set::lower_bound with sets now — Leonard Inkret, Aug 05 '15 at 01:43

score 3 · Answer 2 · edited Nov 25 '19 at 15:57

3

After reading the API of std::lower_bound

On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

And I think STL set is using non-random-access iterators, so it is not doing a O(log N) binary search if using on STL set

edited Nov 25 '19 at 15:57

cbuchart

10,847
9
53
93

answered Aug 05 '15 at 01:37

shole

4,046
2
29
69

You are correct, `std::set::iterator` is bidirectional, not random access – Ryan Haining Aug 05 '15 at 01:38

score 1 · Answer 3 · answered Aug 05 '15 at 01:31

std::lower_bound is a generic binary search algorithm, meant to work with most STL containers. set::lower_bound is designed to work with std::set so it takes advantages of the unique properties of std::set.

As std::set is often implemented as a red-black tree, one can imagine std::lower_bound iterating across all nodes, while set::lower_bound just traverses down the tree.

score 1 · Answer 4 · answered Aug 05 '15 at 01:32

std::lower_bound always guarantees a O(log n) comparisons, only guarantees O(log n) time if passed a RandomAccessIterator, not just a ForwardIterator which does not provide constant-time std::advance.

The std::set::lower_bound implementation of the same algorithm is able to use internal details of the structure to avoid this problem.

C++ Difference between std::lower_bound and std::set::lower_bound?

4 Answers4