Geek Answers Handbook

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

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 many times. However, after submitting my solution, contrary to the math I did on paper to prove that my code was fast enough, it turned out to be 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, having received a hint from the interlocutor to use set :: lower_bound, the algorithm in question ran waaaaaaay faster than before, and this followed my math. Binary search after change:

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

My question is what is the difference between the two? Why does one work much faster than the other? Is lower_bound a binary search function that has O (log2 (n)) complexity? In my code, it turned out to be slower than that.

+4
source share
4 answers

std::set usually implemented as a self-balancing tree with some list associated with it. Knowing this structure, std::set::lower_bound will traverse the tree, knowing the properties of the tree structure. Each step in this means only the next left or right child branch.

std::lower_bound needs to do something similar to a binary data search. However, since std::set::iterator is bidirectional, it is much slower, many steps need to be taken between checked items. Thus, the work performed between the elements is much more intense. In this case, the algorithm will check the element halfway between A and B, then adjust one of A or B, find the element halfway between them and repeat.

+3
source

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

Since std::set often implemented as a red-black tree, one can imagine that std::lower_bound over all nodes, and set::lower_bound just traverses the tree.

+1
source

std::lower_bound always guarantees O(log n) comparison, only O(log n) time is guaranteed if RandomAccessIterator , and not just ForwardIterator , which does not provide constant std::advance .

Implementing the same std::set::lower_bound can use internal structure details to avoid this problem.

+1
source

After reading the std: lower_bound API: std: lower_bound

In iterators without random access, iterators on average produce additional linear complexity in N.

And I think that the STL set uses non-random access iterators, so it does not perform a binary O (log N) lookup if used in an STL set

+1
source

More articles:


All Articles