Policy-Based Data Structures（pb_ds）简介：让编程像开挂一样的高效容器

从课堂点名说起：为什么需要更强大的工具箱？

想象你是一位班长，要在一次全班50人的考试后快速完成三件事：

• 按分数从低到高排序，然后说出第10名考了多少分。
• 想知道有多少人分数低于80分（即80分的排名）。
• 如果新转来一个同学，要把他插入到排名中，并且马上知道新的第10名是多少。

用普通的C++ set 只能做到排序和插入，却无法直接回答“第10名是谁”和“80分排第几”这类问题。你需要自己写一棵平衡树或者用二分法配合动态数组（但插入又慢）。这时候，C++ 的扩展库 Policy-Based Data Structures (pb_ds) 就像给你一个自带“排名查询”功能的智能书柜，你只需要告诉它“我要第10名”或“80分排第几”，它立刻就能回答。

pb_ds 是 GCC 编译器（如 MinGW、Linux 下的 g++）提供的一套高级数据结构集合，可以看作是标准 STL 的“增强版”。它包含了：

• 平衡树（tree）：比 set 多出按排名查找、查询排名的功能。
• 哈希表（gp_hash_table）：比 unordered_map 更快，特别适合海量数据。
• 优先队列（priority_queue）：支持合并两个堆、修改堆中元素的值，就像能合并两个装满零食的袋子，还能随时调整某个零食的优先级。

这些数据结构在信息学奥赛中非常实用，很多难题用它们能大幅简化代码。不过要注意，pb_ds 不是 C++ 标准的一部分，只在 GCC 下能用，比如 NOI Linux 评测环境是支持的。

一、pb_ds 是什么？—— 工具箱里的三个“特殊工具”

pb_ds 的全称是 Policy-Based Data Structures，意思是“基于策略的数据结构”。你可以通过模板参数（称为“策略”）来定制容器的行为，就像买工具箱时可以选择不同规格的螺丝刀头。

使用 pb_ds 需要包含的头文件：

#include <ext/pb_ds/assoc_container.hpp>   // 关联容器（tree, hash_table）
#include <ext/pb_ds/tree_policy.hpp>        // tree 的策略
#include <ext/pb_ds/hash_policy.hpp>        // hash_table 的策略
#include <ext/pb_ds/priority_queue.hpp>     // 优先队列

命名空间：所有类都在 __gnu_pbds 里面，通常我们会写 using namespace __gnu_pbds;。

分类：主要分为两类

• 关联容器：像 set / map，底层可以用红黑树、伸展树、有序向量、哈希表等实现。通过标签（tag）选择。
• 容器适配器：主要是 priority_queue，支持堆合并、修改节点。

二、平衡树（tree）：能查排名的“超级set”

生活例子：班级成绩排行榜

假设班里成绩存到一个 set 里，你只能知道“60分、70分、80分、90分”都在，但无法知道“80分是第几名”，也无法直接取出“第3名（60分）”。
如果用 pb_ds 的 tree，就可以：

• order_of_key(80) → 返回比80小的元素个数，即“80分”的排名（0-based）。
• find_by_order(3) → 返回排名为3的元素（0-based），即“第4名”的成绩。

代码详解：从定义到使用

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;  // pb_ds 的命名空间
using namespace std;

// 定义一个有序集合：key是int，没有映射值（类似set），less<int>升序，
// 底层用红黑树（rb_tree_tag），更新策略为tree_order_statistics_node_update（维护子树大小）
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;

int main() {
    ordered_set s;  // 创建一个空的成绩集合

    // 插入一些分数（模拟考试成绩）
    s.insert(78);   // 78分
    s.insert(92);   // 92分
    s.insert(65);   // 65分
    s.insert(88);   // 88分

    // 查询比80分小的元素个数（即成绩低于80分的人数）
    int rank_of_80 = s.order_of_key(80);
    cout << "低于80分的人数: " << rank_of_80 << endl;  // 输出2（65和78）

    // 查询排名为2的元素（0-indexed），即第3名（65->第1，78->第2，88->第3）
    auto it = s.find_by_order(2);
    if (it != s.end()) {
        cout << "第3名的成绩: " << *it << endl;  // 输出88
    }

    // 和普通set一样可以删除、遍历
    s.erase(78);              // 删除78分
    cout << "删除后集合大小: " << s.size() << endl;  // 3

    // 遍历输出所有分数（升序）
    for (auto x : s) {
        cout << x << " ";
    }
    cout << endl;  // 输出65 88 92

    return 0;
}

模板参数解释（以 tree 为例）：

• 第一个参数：key 的类型（比如 int）。
• 第二个参数：mapped 的类型。如果不需要映射值（类似 set），写 null_type；如果需要类似 map 的功能，写成 int 或 string 等。
• 第三个参数：比较函数，默认 less<key> 升序，可以用 greater<key> 降序。
• 第四个参数：底层树类型标签。
  • rb_tree_tag：红黑树（常用，平衡性好）。
  • splay_tree_tag：伸展树（某些特殊场景更快）。
  • ov_tree_tag：有序向量（适合小数据，像数组一样连续）。
• 第五个参数：节点更新策略（node update）。最常用的就是 tree_order_statistics_node_update，它会在每个节点里额外保存子树大小，从而实现 order_of_key 和 find_by_order。如果不需要排名功能，可以用 null_node_update（默认，和普通 set 一样）。

新手容易犯的错

1. 忘记写更新策略
   如果只写了 tree<int, null_type, less<int>, rb_tree_tag>（漏掉第五个参数），那么 order_of_key 和 find_by_order 就不存在！一定要加上 tree_order_statistics_node_update。

2. 把 null_type 当成 void 或 int
null_type 是 pb_ds 特有的，不能写成 void 或直接省略。它代表“没有映射值”。

3. 和 std::set 搞混
   ordered_set 虽然可以像 set 一样用，但它的迭代器类型不同，不能直接赋值给 std::set::iterator。你通常只会用 auto。

三、哈希表（gp_hash_table）：比 unordered_map 更快的“万能笔记本”

生活例子：班级通讯录 vs 全校花名册

假如你有一个班级通讯录，要找“小明”的电话，用 map 或 unordered_map 都很轻松。但如果全校有10万学生，而且你需要频繁查找，unordered_map 在极端情况下可能因为碰撞变慢。gp_hash_table 使用开放寻址法（元素直接存在数组里，而不是拉链表），就像每个座位只坐一个人，如果有人坐了就往后看下一个空位（线性探测）。这样内存更紧凑，CPU缓存友好，所以速度更快，特别适合数据量巨大（比如 10^7 级别）且哈希函数不错的情况。

代码详解：使用 gp_hash_table

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

int main() {
    // 定义从int到int的哈希表
    gp_hash_table<int, int> mp;

    // 插入学号和成绩：学号123 -> 88分
    mp[123] = 88;
    mp[456] = 92;
    mp[789] = 76;

    // 查找学号456的成绩
    cout << "学号456的成绩: " << mp[456] << endl;  // 92

    // 判断某个学号是否存在
    if (mp.find(123) != mp.end()) {
        cout << "学号123存在" << endl;
    }

    // 修改学号789的成绩
    mp[789] = 80;
    cout << "修改后学号789的成绩: " << mp[789] << endl;  // 80

    // 遍历（顺序不确定）
    for (auto& p : mp) {
        cout << "学号" << p.first << " -> " << p.second << "分" << endl;
    }

    return 0;
}

性能优势：在数据量 10^6 以上时，gp_hash_table 通常比 std::unordered_map 快 2~3 倍。但要注意，它要求哈希函数能均匀分布，否则开放寻址的探测链会变长。如果哈希函数不好，可能反而比链地址法慢。

自定义探测策略

你可以修改模板参数来选择探测方式：

• linear_probe_fn：线性探测（默认，简单但容易聚集）。
• quadratic_probe_fn：二次探测（缓解聚集）。
• 还可以自定义。

一般用默认的线性探测就够，但如果遇到超时，可以尝试二次探测。

新手容易犯的错

1. 不注意内存
   gp_hash_table 会预先分配一个较大的桶数组（通常是质数大小），如果元素数量不稳定，可能内存占用比 unordered_map 高。但通常可以接受。

2. 误以为遍历有序
   哈希表的遍历顺序是无序的，不能用它来按顺序输出。如果需要顺序，用 tree 或 map。

3. 在大数据量下忘记设置合适的初始大小
   可以通过 mp.resize(2000000) 提前分配容量，减少重新哈希的开销。

四、优先队列（priority_queue）：能合并堆的“超级饭盒”

生活例子：合并两个零食堆 + 偷偷调换优先级

你有一个装满零食的袋子（大顶堆，最想吃的在最上面），你的朋友也有一个。你想把朋友的零食合并到自己的袋子里，如果用手动 push 每个零食，要花 O(n log n) 时间。但 pb_ds 的 priority_queue 支持 join 操作，可以在 O(log n) 时间内合并两个堆！另外，如果你突然觉得某个零食没那么好吃（优先级降低），可以用 modify 直接修改它的优先级，不需要删除再插入。

代码详解：合并堆与修改节点

#include <iostream>
#include <ext/pb_ds/priority_queue.hpp>

using namespace __gnu_pbds;
using namespace std;

int main() {
    // 默认是大顶堆（less<int>），使用配对堆（pairing_heap_tag）
    priority_queue<int> pq1, pq2;

    // 往两个堆里插入分数
    pq1.push(88);   // 88分
    pq1.push(92);   // 92分
    pq2.push(76);   // 76分
    pq2.push(95);   // 95分

    // 合并pq2到pq1，pq2变空
    pq1.join(pq2);
    cout << "合并后pq1的堆顶（最高分）: " << pq1.top() << endl;  // 95
    cout << "pq2的大小: " << pq2.size() << endl;                  // 0

    // 使用配对堆标签（pairing_heap_tag）可以获得更好的合并性能
    // 并且支持修改节点，这里演示如何修改（需要保存迭代器）
    // 注意：只有某些堆标签支持modify，如 pairing_heap_tag, binomial_heap_tag 等
    priority_queue<int, less<int>, pairing_heap_tag> paired_pq;
    auto it = paired_pq.push(80);   // 保存迭代器
    paired_pq.push(90);
    paired_pq.push(70);

    // 修改it指向的节点值（比如80 -> 100）
    paired_pq.modify(it, 100);
    cout << "修改后堆顶: " << paired_pq.top() << endl;  // 100

    return 0;
}

支持的操作：

• push(x)：插入，返回迭代器（用于修改）。
• pop()：弹出堆顶。
• top()：访问堆顶。
• join(其他堆)：合并，被合并的堆会清空。
• modify(迭代器, 新值)：修改元素，内部自动调整堆。
• erase(迭代器)：删除指定元素（某些标签支持）。

堆标签选择：

• pairing_heap_tag：配对堆，合并 O(1)，修改 O(log n)（实际很快）。
• binomial_heap_tag：二项堆，合并 O(log n)，修改 O(log n)。
• binary_heap_tag：二叉堆，没有 join 操作（和 std::priority_queue 类似）。

一般竞赛用 pairing_heap_tag 就够了。

新手容易犯的错

1. 在 priority_queue 上使用 join 后，原堆被清空，忘记这点
   注意 join 后另一个堆就空了，不要再使用它。

2. 试图修改元素却不保存迭代器
   modify 需要原插入时返回的迭代器，否则无法定位。如果你需要修改，必须用 auto it = pq.push(x); 保存。

3. 误以为 pop 后迭代器仍有效
   弹出堆顶后，指向该元素的迭代器就失效了，不能再使用。

五、性能对比：什么时候该用哪个？

生活比喻：

• tree 像带目录的书：可以翻到第几页，也能知道某页之前有多少页。
• gp_hash_table 像词典按拼音首字母查找：快速但无序。
• priority_queue 像食堂排队打饭：随时能看最前面的，还能合并两个队伍。

六、完整示例：综合运用 pb_ds 做一个“排行榜系统”

题目：设计一个班级成绩排行榜，支持以下操作：

• ADD score：添加一个成绩（可重复）。
• RANK K：查询排名第 K 的成绩（从高到低，第1名最高分）。
• COUNT score：查询低于该成绩的人数（即该成绩的排名）。

由于成绩可重复，我们需要用 tree 支持 multiset 的重复元素。pb_ds 中 tree 也内置了多重集能力：只需要把第二个模板参数改为 null_type，并且允许重复插入。但注意 order_of_key 对于重复元素，会返回小于该值的个数（不包括相等）。我们可以结合 find_by_order 轻松实现。

#include <iostream>
#include <string>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

// 定义有序多重集（允许重复，升序排序）
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_multiset;

int main() {
    ordered_multiset ms;
    int n;
    cin >> n;                 // 输入操作次数
    while (n--) {
        string op;
        cin >> op;
        if (op == "ADD") {
            int score;
            cin >> score;
            ms.insert(score);  // 插入成绩
        } else if (op == "RANK") {
            int k;
            cin >> k;
            // 注意：排名从1开始，但 find_by_order 是0-based
            // 第1名对应 find_by_order( size() - 1 )
            int total = ms.size();
            if (k > total) {
                cout << "没有第" << k << "名" << endl;
            } else {
                auto it = ms.find_by_order(total - k);  // 降序第k名
                cout << "第" << k << "名成绩: " << *it << endl;
            }
        } else if (op == "COUNT") {
            int score;
            cin >> score;
            // 低于score的人数
            int cnt = ms.order_of_key(score);
            cout << "低于" << score << "分的人数: " << cnt << endl;
        } else {
            cout << "未知操作" << endl;
        }
    }
    return 0;
}

运行示例（假设输入）：

6
ADD 88
ADD 92
ADD 76
RANK 1
RANK 2
COUNT 80

输出：

第1名成绩: 92
第2名成绩: 88
低于80分的人数: 1

七、常见错误汇总（看看你是不是也犯了）

1. 忘记包含必要的头文件

   • 只用 tree 时需 #include <ext/pb_ds/assoc_container.hpp> 和 #include <ext/pb_ds/tree_policy.hpp>。
   • 只用 gp_hash_table 需 #include <ext/pb_ds/assoc_container.hpp> 和 #include <ext/pb_ds/hash_policy.hpp>。
   • 只用 priority_queue 需 #include <ext/pb_ds/priority_queue.hpp>。
     如果只包含 assoc_container.hpp，可能找不到 tree 的某些策略。

2. 在 tree 中忘了第五个参数
   只写 tree<int, null_type, less<int>, rb_tree_tag> 没有排名功能。必须加上 tree_order_statistics_node_update。

3. 误以为 gp_hash_table 的遍历是有序的
   它和 unordered_map 一样无序。

4. 使用 priority_queue::join 后还继续用被合并的堆
   被合并的堆已经空了，再 push 或 pop 不会有预期结果。

5. 在非GCC编译器下编译
   pb_ds 是 GCC 扩展，Windows 的 MinGW 可以，但 MSVC（Visual Studio）不行。在竞赛中请确认评测机系统（如 NOI Linux 的 g++）。

6. 试图修改 priority_queue 中元素但没保存迭代器
   modify 需要迭代器，务必在 push 时 auto it = pq.push(x);。

八、总结与相关指引

pb_ds 是 C++ 竞赛选手的“秘密武器”，它让你用简洁的代码实现复杂的数据结构需求。掌握它之后，你能：

• 用 tree 解决“第 K 大 / 小”问题（配合二分可以快速查询排名）。
• 用 gp_hash_table 加速大规模哈希操作（比如统计词频）。
• 用 priority_queue 实现可合并堆（优化 Dijkstra 多源最短路或合并多个优先队列）。

接下来可以学习的方向：

• 更高级的 tree 更新策略：如 tree_order_statistics_node_update 之外，还有 null_node_update（默认）、自定义更新（如维护区间和）。
• 自定义哈希函数：避免哈希碰撞，进一步提升 gp_hash_table 性能。
• 堆的修改与删除：在最优队列算法（如 K 短路、任务调度）中，modify 和 erase 非常实用。
• 结合标准 STL：pb_ds 的迭代器与 STL 算法兼容，可以配合 sort、for_each 等。

希望这篇介绍能帮你打开 pb_ds 的大门，让编程解题变得更轻松！