C ++ STL container suitable for finding the nth element in a dynamic ordered list?

Question

Using a balanced BST such as AVL or Red-Black-Tree, we can easily maintain a set of values ​​that:

• Insert / delete / request setpoint.
• Count items that are less than / greater than the set value.
• Find the item with rank k after sorting.

All of the above can be archived in O(log N) complexity.

My question is: is there any STL container that supports all three of the above operations in the same complexity?

I know that STL set / multiset can be used for 1 and 2. And I looked at the container map / set / multiset based on _Rb_tree, but none of them support support 3. Is there a way to subclass ext / rb_tree to solve this problem ?

Answer 1

The data structure you are looking for is a statistics tree, which is a binary search tree in which each node stores the size of the subtree embedded in that node.

This supports all of the above operations in O (log n).

There is a tree of order statistics in the GNU Policy-Based Data Structures (part of GNU C ++).

The code looks something like this:

 #include <iostream> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> set_t; int main() { set_t s; s.insert(12); s.insert(50); s.insert(30); s.insert(20); cout << "1st element: " << *s.find_by_order(1) << '\n'; // 20 cout << "Position of 30: " << s.order_of_key(30) << '\n'; // 2 return 0; } 

Live demo .

^{[Derived from this answer ]}