Order Statistic Tree in C++

by

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.

More Related Contents:

  1. How to get the maximum number after erasing n digits from the number [closed]
  2. Why is std::map implemented as a red-black tree?
  3. Why does the C++ STL not provide any “tree” containers?
  4. Looking for C++ STL-like vector class but using stack storage
  5. Is there a way to access the underlying container of STL container adaptors?
  6. Where can I get a “useful” C++ binary search algorithm?
  7. Relative performance of std::vector vs. std::list vs. std::slist?
  8. std::transform() and toupper(), no matching function
  9. How to get a random element from a C++ container?
  10. LRU cache design
  11. c++ sort keeping track of indices [duplicate]
  12. A proper way to create a matrix in c++
  13. Reorder vector using a vector of indices [duplicate]
  14. How to choose between map and unordered_map?
  15. what is the difference between set and unordered_set in C++?
  16. Efficiency of the STL priority_queue
  17. How can I sort an STL map by value?
  18. TMP: how to generalize a Cartesian Product of Vectors?
  19. How can std::make_heap be implemented while making at most 3N comparisons?
  20. What is the right approach when using STL container for median calculation?
  21. Why would anyone use set instead of unordered_set?
  22. std::back_inserter for a std::set?
  23. Easiest way of using min priority queue with key update in C++
  24. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  25. Why there is no std::copy_if algorithm?
  26. stl ordering – strict weak ordering
  27. In STL maps, is it better to use map::insert than []?
  28. does (w)ifstream support different encodings
  29. std::string length() and size() member functions
  30. Cut set of a graph, Boost Graph Library

Leave a Comment