estadístico de orden Árbol en C++

Question

Necesito un árbol de orden estadístico para contenedores STL mapa del CCG estándar.

I marcada y hay algo conocido como PBDS. Estructuras de datos basadas en políticas. Ese uso tampoco es claro para mí.

alguien me puede decir cómo utilizar los contenedores STL mapa para el árbol estadístico de orden? Incluso si es solo en GNU G ++ es suficiente?

Answer 1

Aquí es el ejemplo de MAP STL basado en políticas GNU implementado como árbol orden estadística (probado en gcc Linux 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; 
} 

Aquí es a link to the overview of GNU Policy-Based Data Structures. Aquí está el otro tree_order_statistics example. No puedo encontrar una buena referencia para las estructuras de datos basadas en políticas, pero puede usar estos enlaces, así como las fuentes de PBDS.