问题描述
我需要标准 GCC STL 地图容器的订单统计树.
I need an order statistic tree for standard GCC STL map containers.
我查了一下,有一种叫做 PBDS 的东西.基于策略的数据结构.我也不清楚这种用法.
I checked and there is something known as PBDS. Policy based data structures. That usage is also not clear to me.
谁能告诉我如何将 STL 映射容器用于订单统计树?即使它只在 GNU G++ 上就足够了吗?
Anyone can tell me how to use STL map containers for order statistic tree? Even if its only on GNU G++ its enough?
推荐答案
以下是将 GNU Policy-Based STL MAP 实现为订单统计树的示例(在 Linux gcc 4.6.1 上测试):
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 << '
';
return 0;
}
这里是基于 GNU 策略的数据结构概述的链接.这是其他 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++中的订单统计树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!