Zamów drzewo statystyczne w C++

Question

Potrzebuję drzewa statystyk zamówień dla standardowych kontenerów map GCC STL.

Sprawdziłem i jest coś takiego jak PBDS. Struktury danych oparte na polityce. To użycie również nie jest dla mnie jasne.

Ktoś może mi powiedzieć, jak używać kontenerów mapy STL dla drzewa statystyk zamówień? Nawet jeśli jego tylko na GNU G ++ wystarczy?

Answer 1

Oto przykład GNU Policy-Based MAP STL realizowanego jako drzewo Kolejność statystycznego (testowane na Linux gcc 4.6.1):

#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, 
    int, 
    less<int>, 
    rb_tree_tag, 
    tree_order_statistics_node_update> 
map_t; 

int main() 
{ 
    map_t s; 
    s.insert(make_pair(12, 1012)); 
    s.insert(make_pair(505, 1505)); 
    s.insert(make_pair(30, 1030)); 
    cout << s.find_by_order(1)->second << '\n'; 
    return 0; 
} 

Oto a link to the overview of GNU Policy-Based Data Structures. Oto inne tree_order_statistics example. Nie mogę znaleźć dobrego odniesienia do struktur danych opartych na zasadach, ale możesz używać tych łączy, jak również źródeł PBDS.