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

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

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?

Solution

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...