C ++，STL，次序统计树 [英] C++,STL,Order Statistic Tree

问题描述

我需要顺序统计树标准GCC STL地图容器。 我检查，有一些被称为PBDS。基于策略的数据结构。 这也用法我也不清楚。 任何人都可以告诉如何使用STL的MAP容器顺序统计树？ 即使它只能在GNU G ++的还不够吗？

I need order statistic tree for standard GCC STL MAP containers. I checked and there is something known as PBDS. Policy based data structures. That also usage is not clear to me. Anyone can tell how to use STL MAP containers for order statistic tree? Even if its only on GNU G++ its enough?

推荐答案

下面是实现为顺序统计树（在Linux GCC 4.6.1测试）GNU基于策略的STL MAP的例子：

Here is the example of GNU Policy-Based STL MAP implemented as order statistic tree (tested on 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;
}

下面是<一href="http://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures_design.html#container.tree.interface">a链接到GNU基于策略的数据结构的概述。下面是其他<一href="http://www.opensource.apple.com/source/llvmgcc42/llvmgcc42-2336.9/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc">tree_order_statistics例如的。我找不到基于策略的数据结构的一个很好的参考，但你可以使用这些链接，以及PBDS来源。

Here is a link to the overview of GNU Policy-Based Data Structures. Here is other tree_order_statistics example. I cannot find a good reference for Policy-Based Data Structures, but you can use these links as well as PBDS sources.

这篇关于C ++，STL，次序统计树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！