CODEWITHSUNDEEP
c++stlset
Olivia Pearls
Olivia Pearls

Reputation: 139

std::set method to get number of elements lower than a given element?

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)?

Upvotes: 2

Views: 1864

Answers (1)

cigien
cigien

Reputation: 60238

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.

Upvotes: 3

Related Questions