Order Statistic Tree in C++

Question

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?

Carrelli

Answer 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 << '\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.

Alisonalissa

Is there a way to use these libraries using the Visual Studio compiler? (cl) – Asis

As you can see from documentation, it should be compatible with cl. But I never tried to use it this way. – Alisonalissa

How would I go about importing this library into my Visual Studio environment? – Asis

No idea. Probably the only thing you have to do is to add library's directory to the list of "include" directories... – Alisonalissa

Note that if we specify null_type for the second template parameter of tree<..>, we get an order-statistic set. – Imperialism