Дерево статистики по заказу в С++

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

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

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

Ответы

Ответ 1

Вот пример 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.