### bazsi700's blog

By bazsi700, history, 2 years ago, , I have just discovered, that std::set::lower_bound for larger sets is much-much faster than std::lower_bound.

Can anyone give explanation why does this happen?

Also, use std::set::lower_bound instead of std::lower_bound, I struggled on a problem for like 2 hours because of getting TLE for this.  Comments (8)
 » On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average. iterator — a bidirectional iterator to const value_type
 » As far as i know std::lower_bound works with complexity O(log n) * O(access_of_element), it is O(log n) for vectors, arrays, but for sets it is something like O(n * log^2 n) (because you can get element in set in O(n log n)). std::set::lower_bound is function specified for using in sets, it has complexity O(log n).
•  » » 2 years ago, # ^ | ← Rev. 2 →   Actually, std::lower_bound on a set is (not much better anyway). See this StackOverflow question and, especially, WaltK's comment.
•  » » » Yes, i just thought that we need about O(log n) operations to go to the next element in rb-tree every time, but it is O(n) in total, so final complexity is O(n * log n).
•  » » » I'm pretty sure it's implemented in O(n)
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   I'm not so sure. Performs approximately log2(N)+1 element comparisons (where N is this distance). It is a binary search, after all, and generally cannot be replaced with a linear one, because the comparison function might have insanely huge complexity.In my STL implementation: template _ForwardIterator __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val, _Compare __comp) { typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType; _DistanceType __len = std::distance(__first, __last); while (__len > 0) { _DistanceType __half = __len >> 1; _ForwardIterator __middle = __first; std::advance(__middle, __half); if (__comp(__middle, __val)) { __first = __middle; ++__first; __len = __len - __half - 1; } else __len = __half; } return __first; } 
•  » » » » » It still does O(n) advances
•  » » » » » » You're right, sorry.