Kontener C++ STL odpowiedni do znalezienia n-tego elementu na liście uporządkowanej dynamicznie?

Question

Korzystanie zbilansowanej BST jak AVL lub czerwono-czarno-Tree, możemy łatwo utrzymać zestaw wartości, które:

1. Insert/usuwać/query podana wartość.
2. Policz elementy, które są mniejsze/większe niż podana wartość.
3. Znajdź element z pozycją k po sortowaniu.

Wszystkie powyższe można zarchiwizować w złożoności O(log N).

Moje pytanie brzmi, czy istnieje kontener STL obsługujący wszystkie trzy powyższe operacje w tej samej złożoności?

Wiem, że zestaw/multiset STL może być używany dla 1 i 2. I ja sprawdziłem kontenery oparte na _Rb_tree map/set/multiset, ale żaden nie zapewnia wsparcia dla 3. Czy istnieje sposób na podklasowanie ext/rb_tree, aby rozwiązać ten problem ?

Answer 1

Struktura danych, której szukasz, to order statistic tree, które jest binarnym drzewem wyszukiwania, w którym każdy węzeł przechowuje rozmiar poddrzewa zrootowanego w tym węźle.

Obsługuje wszystkie wymienione operacje w O (log n).

Istnieje drzewo statystyk zamówień w GNU Policy-Based Data Structures (część GNU C++).

kod będzie wyglądał tak:

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

^{[Pochodzące z this answer]}