22

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?

0

1 Answer 1

26

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.

5
  • Is there a way to use these libraries using the Visual Studio compiler? (cl) Apr 20, 2015 at 14:26
  • As you can see from documentation, it should be compatible with cl. But I never tried to use it this way. Apr 20, 2015 at 14:58
  • How would I go about importing this library into my Visual Studio environment? Apr 20, 2015 at 15:29
  • No idea. Probably the only thing you have to do is to add library's directory to the list of "include" directories... Apr 20, 2015 at 15:35
  • 2
    Note that if we specify null_type for the second template parameter of tree<..>, we get an order-statistic set. Nov 30, 2015 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.