Đặt hàng cây thống kê trong C++

Question

Tôi cần một cây thống kê đơn hàng cho các thùng chứa bản đồ GCC STL tiêu chuẩn.

Tôi đã kiểm tra và có một thứ được gọi là PBDS. Cấu trúc dữ liệu dựa trên chính sách. Cách sử dụng đó cũng không rõ ràng với tôi.

Bất kỳ ai cũng có thể cho tôi biết cách sử dụng vùng chứa bản đồ STL cho cây thống kê thứ tự? Ngay cả khi nó chỉ trên GNU G ++ của nó đủ?

Answer 1

Dưới đây là ví dụ về MAP STL GNU Policy-Based thực hiện như cây để thống kê (thử nghiệm trên 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; 
} 

Đây là a link to the overview of GNU Policy-Based Data Structures. Dưới đây là tree_order_statistics example khác. Tôi không thể tìm thấy một tài liệu tham khảo tốt cho các cấu trúc dữ liệu dựa trên chính sách, nhưng bạn có thể sử dụng các liên kết này cũng như các nguồn PBDS.