Contenitore STL C++ adatto per trovare l'ennesimo elemento nell'elenco dinamico ordinato?

Question

BST equilibrato come AVL o Rosso-Nero-Tree, possiamo mantenere facilmente una serie di valori che:

1. Inserire/cancellare/interrogazione dato valore.
2. Contare gli elementi più piccoli/più grandi del valore dato.
3. Trova l'elemento con il rango k dopo l'ordinamento.

Tutti sopra possono essere archiviati nella complessità O(log N).

La mia domanda è, c'è qualche contenitore STL che supporta tutte e 3 le operazioni sopra nella stessa complessità?

So che il set STL/multiset può essere utilizzato per 1 e 2. E ho esaminato i contenitori basati su _Rb_tree map/set/multiset, ma nessuno fornisce il supporto per 3. C'è un modo per creare una sottoclasse di ext/rb_tree per risolvere questo ?

Answer 1

La struttura dati che stai cercando è un order statistic tree, che è un albero di ricerca binario in cui ogni nodo memorizza la dimensione del sottoalbero radicato in quel nodo.

Questo supporta tutte le operazioni elencate in O (log n).

Esiste un albero di statistica degli ordini in GNU Policy-Based Data Structures (parte di GNU C++).

Il codice dovrebbe essere simile a questa:

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

^{[Derivato da this answer]}