How to find rank of an element in stl set in O(logn)
algorithm, c++, data-structures, stl
Solution
No; a balanced tree does not need to store the number of descendants of each node, which is required to more quickly compute `distance( s.begin(), iter )` for `std::set s` and iterator `iter` (which is what I suppose you mean). Therefore the information simply doesn't exist except by counting the items one by one.
If you need to perform many such computations, copy the `set` into a sorted, random-access sequence such as `vector` or `deque`, but then modification of the sequence becomes expensive.
A tree data structure that does what you ask probably exists in a free library somewhere, but I don't know of one.
Problem
I want to find rank of an element in stl set. I am able to traverse from beginning to that element and find out its rank but that is taking O(n). Is there any method to find the rank in O(logn).