在C++中訂購統計樹

Question

我需要一個用於標準GCC STL映射容器的訂單統計樹。

我查了一下，有一種叫做PBDS的東西。基於策略的數據結構。這種用法對我來說也不清楚。

任何人都可以告訴我如何使用STL地圖容器的訂單統計樹？即使它僅在GNU G ++上就足夠了？

Answer 1

這裏是作爲順序統計樹（在Linux GCC 4.6.1測試）實施基於策略的GNU STL MAP的例子：

#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; 
} 

這裏是a link to the overview of GNU Policy-Based Data Structures。這裏是其他tree_order_statistics example。我無法找到基於策略的數據結構的良好參考，但您可以使用這些鏈接以及PBDS來源。