Статистика статистики по заказу на C++

Question

Мне нужно дерево статистики заказа для стандартных контейнеров карт GCC STL.

Я проверил и есть что-то известное как PBDS. Структуры данных на основе политик. Это использование также не ясно для меня.

Кто-нибудь может сказать мне, как использовать контейнеры для карт STL для дерева статистики заказа? Даже если его только на GNU G ++ достаточно?

Answer 1

Вот пример GNU на основе политик STL MAP реализуется как порядок статистического дерева (протестировано на 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; 
} 

Вот a link to the overview of GNU Policy-Based Data Structures. Другой раздел: tree_order_statistics example. Я не могу найти хорошую ссылку для структур данных на основе политик, но вы можете использовать эти ссылки, а также источники PBDS.