Let suppose the values in my set are S={1,2,3,4}; Now I want to know how many numbers are there which are smaller than 3,then I will use s.lower_bound(3); But I am not able to get the count of numbers less than 3 when I write S.lower_bound(3)-s.begin()

CodePudding user response：

The class template std::set does not have random access iterators. So the operator - is not defined for its iterators. You need to use the standard function std::distance

#include <set>
#include <iterator>

//...

auto n = std::distance( S.begin(), S.lower_bound( 3 ) );

Pay attention to that the index will be one less than the number of elements that precede the current element provided that the number is not equal to 0.

CodePudding user response：

Existing answer by Vlad is a valid and intuitive way to do this, but doesn't need to be the fastest way. As explained, std::set is not a random access container, and its iterators can only access its direct neighbours by decrement or increment, aka a bidirectional iterator.

The way that std::distance calculates the distance between two iterators is by incrementing the starting iterator until it is equal to the end iterator. On average, that is N / 2 steps required. Iteration through a set is fairly expensive since each element is allocated separately, so it is likely that you get a new cache miss every step of the loop.

Now, lookups in std::set are pretty fast, O(log(N)). However we still need to loop through the set linearly from the start afterwards in std::distance, which likely will be the more expensive part. Because of that we might as well do the search at the same time as we iterate the set and avoid having to do the extra lookup. It does add one extra comparison in the loop, but no extra branching on top of the already existing end iterator check in std::distance