Cấu trúc dữ liệu dựa trên chính sách (Policy-based data structures) trong g++

Trình biên dịch g++ là trình biên dịch C++ cho GNU trong Linux.

Trình biên dịch g++ cũng hỗ trợ một số cấu trúc dữ liệu đặc biệt không có trong thư viện chuẩn C++. Chúng được gọi là cấu trúc dữ liệu dựa trên chính sách (policy-based data structures).

Các cấu trúc dữ liệu dựa trên chính sách cung cấp cho lập trình viên hiệu suất cao, an toàn về ngữ nghĩa (semantic safety) và linh hoạt hơn so với cấu trúc dữ liệu chuẩn của thư viện std C++.

Để bao gồm các cấu trúc dữ liệu này vào chương trình, thêm các dòng sau:

#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds;

Ví dụ

Chương trình minh họa cách hoạt động của các cấu trúc dữ liệu dựa trên chính sách:

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> 
#include <iostream> 
using namespace __gnu_pbds; 
using namespace std; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set; 

int main() { 
    new_data_set data; 
    data.insert(34); 
    data.insert(785); 
    data.insert(12); 
    data.insert(87); 
    cout << "Giá trị tại chỉ số 2 là " << *data.find_by_order(2) << endl; 
    cout << "Chỉ số của số 87 là " << data.order_of_key(87) << endl; 
    return 0; 
}

Kết quả

Giá trị tại chỉ số 2 là 785 
Chỉ số của số 87 là 4

Các cấu trúc dữ liệu này rất linh hoạt, cho phép nhiều thao tác như kiểm tra chỉ số của phần tử, tìm phần tử tại chỉ số, v.v.