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.
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, 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.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With