c++ - C++で統計ツリーを注文する

Question

標準のGCCSTLマップコンテナの注文統計ツリーが必要です。

確認したところ、PBDSと呼ばれるものがあります。ポリシーベースのデータ構造。その使用法も私にはわかりません。

注文統計ツリーにSTLマップコンテナを使用する方法を教えてもらえますか？GNU G ++だけでも十分ですか？

Answer 1

注文統計ツリーとして実装されたGNUポリシーベースのSTLMAPの例を次に示します（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;
}

これは、GNUポリシーベースのデータ構造の概要へのリンクです。これが他のtree_order_statisticsの例です。ポリシーベースのデータ構造の適切なリファレンスが見つかりませんが、これらのリンクとPBDSソースを使用できます。