Мне нужно дерево статистики заказа для стандартных контейнеров карт GCC STL.
Я проверил, и есть что-то известное как PBDS. Структуры данных на основе политик. Это использование также не ясно для меня.
Кто-нибудь может сказать мне, как использовать контейнеры карт STL для дерева статистики заказа? Даже если его только на GNU g++ достаточно?
Вот пример STL MAP на основе политик GNU, реализованный как дерево статистики заказов (проверено на 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;
}
Вот ссылка на обзор структур данных на основе политик GNU. Вот еще один пример tree_order_statistics. Я не могу найти хорошую ссылку для структур данных на основе политик, но вы можете использовать эти ссылки, а также источники PBDS.