I need an order statistic tree for standard GCC STL map containers.
I checked and there is something known as PBDS. Policy based data structures. That usage is also not clear to me.
Anyone can tell me how to use STL map containers for order statistic tree? Even if its only on GNU G++ its enough?
In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree) that supports two additional operations beyond insertion, lookup and deletion: Select(i) – find the i'th smallest element stored in the tree.
order tree (plural order trees) (topology) A set that is the union of subsets (called segments), each of which is totally ordered, such that the segments fit together a certain way.
"Order statistics" is a fancy name for "K-th element of an N-element sequence sorted in ascending order". The rest of the slide simply illustrates the idea, explaining that 1-order statistics is the smallest element in a sequence, n-order statistics is the largest element, n/2 order statistics is the median, and so on.
It should support four operations: Insert, Delete, Select and Rank.
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;
}
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With