Ordered Set และ GNU C++ PBDS

ในบทเรียนนี้ เราจะอธิบาย Ordered Set และ GNU C++ PBDS (Policy-Based Data Structures)

Ordered Set คืออะไร?

Ordered Set เป็น Data Structure แบบ Policy-Based (ไม่อยู่ใน STL มาตรฐาน) เก็บ Element เรียงลำดับ ไม่ซ้ำ รองรับ Operation เพิ่มเติม:

• find_by_order(k) − Iterator ชี้ Element อันดับ k (0-indexed)
• order_of_key(k) − จำนวน Element ที่น้อยกว่า k

Header และ Namespace

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

Declaration

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ตัวอย่าง

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

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ordered_set<int> os;
    os.insert(5);
    os.insert(1);
    os.insert(2);
    
    cout << *os.find_by_order(1) << endl; // Element อันดับ 1 (0-indexed) = 2
    cout << os.order_of_key(4) << endl;  // จำนวน Element < 4 = 2 (1,2)
    cout << os.order_of_key(5) << endl;  // จำนวน Element < 5 = 2 (1,2)
    
    if (os.find(2) != os.end())
        os.erase(os.find(2));
    
    cout << *os.find_by_order(1) << endl; // ตอนนี้อันดับ 1 คือ 5
    cout << os.order_of_key(4) << endl;  // จำนวน Element < 4 = 1 (1)
    
    return 0;
}

ผลลัพธ์

2
2
2
5
1

สรุป

PBDS Ordered Set ใช้ได้เฉพาะ GCC/G++ (GNU Compiler) ไม่ใช่ Standard C++ เหมาะสำหรับโจทย์แข่งขันที่ต้องการ Order Statistics