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 from the iterator from the very beginning. One of the methods:

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

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

Do they have any way to implement the same to find an index in O (log n) in C ++?

Answer 1

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

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

If your type inside std::set<T> not as light as int , you can save both std::set<T> and the sorted vector of iterators std::vector<std::set<T>::iterator> . But it could not be trivial to synchronize these structures. Maybe you can add some position to T ? Or hold std::set<std::pair<T,int>, comp_first_of_pair<T>> , where comp_first_of_pair just has set , sorted only by T , and the second int to save the position in the set?

A few ideas - to even have an O(1) travel time ...

Answer 2

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

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

However, since comments indicate that the execution time depends on the type of iterator used. In the case of dialing, this is a bidirectional iterator, and the distance is O (n).

Answer 3

You cannot use math with bidirectional iterators. Thus, the only acceptable way is to count yourself (how many int are less than the X that you inserted into the set).

But if you clearly separated the “data collection” and “data usage” steps - it might be worth replacing std :: set with a sorted std :: vector , it’s harder to maintain, but it has its own advantages, including iterative math (so you can get search using O (log n) using std :: binary_search and distance from O (1))

Answer 4

If the calculation of the index is really your bottleneck, then I see 2 options:

• Save the index. Either in the nodes themselves, or in a separate std::map . Of course, this means that you must update this cache.
• Use std::vector . This is not as bad as it might seem at first glance. If you keep the vector always sorted, you can use it as set . Performance will be similar to set . The biggest flaw: node can be copied a lot. (This can be compensated with pointers, boost:shared_ptr or std::unique_ptr [C ++ 11 only]).
  To find an element, use std::lower_bound .
  Instead of insert / push_back you do: insert( lower_bound(b,e,x), x )

Answer 5

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