Does std::set support any method that returns the number of elements that are lower than a given element?
I know that we have lower_bound that returns the iterator to the lower bound of the given element; but it does not return to me the number of elements before a given element.
I know that I can iterate from the beginning to the lower bound iterator; but this will take O(n) time in the worst case. Do we have a method that does this in O(logn)?
If you specifically have a std::set, then you can use the custom std::set::lower_bound like this:
auto lb = s.lower_bound(key);
which is guaranteed O(log n) complexity.
And to get the count of elements, you can use std::distance like this:
auto count = std::distance(s.begin(), s.lower_bound(key));
However, std::set doesn't support random access iterators, so the std::distance call has O(n) complexity.
If you have some sorted range, you can still use lower_bound and distance like this:
auto lb = std::lower_bound(s.begin(), s.end(), key);
auto count = std::distance(s.begin(), lb);
But note that if s doesn't support random access, then both these operations have O(n) complexity.