distance between std::set begin() and std::set iterator in O(logn)

Question

I need to find the index of an element in std::set. This index can be visualized as the distance of the iterator from the beginning. One way can be:

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);

This clearly takes O(n) time. But we know that the distance from the root in a binary search tree as implemented by set internally can be found in O(log n) time.

Is their any way to implement the same to find the index in O(log n) time in C++ set?

Answer 1

You can use the function std::set<>::find to search for an element x and compute the distance to the first iterator of the set.

std::distance(s.begin(), s.find(x))

However, as comments indicate the runtime of distance depends on the type of iterator used. In the case of a set this is a bidirectional iterator and distance is O(n).

Answer 2

You can use sorted std::vector<int>. If it is sorted, you can find element in O(log n). And you can find distance in constant time O(1).

By sorted vector I mean that after every insertion (or after many insertions) you do std::sort(v.begin(), v.end());

If your type inside std::set<T> is not as light like int - you can keep both - std::set<T> and sorted vector of iterators std::vector<std::set<T>::iterator>. But it could not trivial to keep these structures in sync. Maybe you can add some like position to T? Or keep std::set<std::pair<T,int>, comp_first_of_pair<T>> where comp_first_of_pair is just to have set sorted only by T and the second int is for keeping position in set?

Just a few ideas - to have even O(1) distance time...

Answer 3

You can find the index of an element in a set in O(log(N)) with an ordered set: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ . This is implemented as a red-black tree. I know this topic is very old, but it might help readers in the future.