Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to find rank of an element in stl set in O(logn)

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

like image 727
Vineet Setia Avatar asked Aug 07 '13 03:08

Vineet Setia


1 Answers

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.

like image 85
Potatoswatter Avatar answered Oct 14 '22 10:10

Potatoswatter