C++的pb_ds库

pb_ds 库是 GNU C++ STL 的一部分，它提供了一系列灵活、高效的数据结构，允许开发者根据具体需求定制数据结构的行为。在本篇博客中，我们将深入了解 pb_ds 库中提供的主要功能和数据结构。

首先。

Ordered Set 和 Ordered Map：
- 这两个数据结构允许自定义排序规则，提供了有序集合和有序映射的功能。
Indexed Set 和 Indexed Map：
- 支持快速查询元素位置的有序集合和有序映射。
Hashed Set 和 Hashed Map：
- 支持自定义哈希函数的哈希集合和哈希映射。
Trie (字典树)：
- 用于高效存储和检索字符串集合的数据结构。
Priority Queue (优先队列)：
- 支持自定义优先级规则的优先队列。
Bitsets：
- 用于高效存储大量二进制数据的数据结构。
Traits (特性)：
- 允许用户指定数据结构的行为，如是否允许重复元素、是否允许修改键值等。
Policy-Based Trie：
- 支持策略的 trie 数据结构。
cc_hash_table：
- 基于开放定址哈希表实现的高性能哈希表。
树状数组 (Fenwick Tree)：
- 用于高效处理动态前缀和的数据结构。
字符串哈希 (String Hashing)：
- 用于快速计算字符串哈希值的函数。
平衡二叉树 (AVL Tree)：
- 自平衡二叉搜索树的实现。
左偏树 (Leftist Tree)：
- 支持合并操作的二叉树。
伸展树 (Splay Tree)：
- 自适应的二叉搜索树。
分数 (Rational Arithmetic)：
- 支持分数运算的实现。
单调队列 (Monotonic Queue)：
- 用于维护区间内的最大值或最小值的队列。
优先级搜索树 (Treap)：
- 随机化的二叉搜索树。
差分约束系统 (Difference Constraints)：
- 用于解决一类特殊线性不等式的系统。
分块 (Block Structures)：
- 用于提高查询性能的数据分块技术。

1.Ordered Set：

插入元素：
- insert(key)：向有序集合中插入元素 key。
删除元素：
- erase(key)：从有序集合中删除元素 key。
查找元素：
- find(key)：查找元素 key 在有序集合中的迭代器，若不存在返回集合的 end 迭代器。
区间查找：
- lower_bound(key)：返回第一个不小于 key 的元素的迭代器。
- upper_bound(key)：返回第一个大于 key 的元素的迭代器。
获取元素个数：
- size()：返回有序集合中的元素个数。
清空集合：
- clear()：清空有序集合中的所有元素。
遍历集合：
- 使用迭代器进行遍历，可以通过循环遍历整个集合。

2.Ordered Map：

插入键值对：
- insert(make_pair(key, value))：向有序映射中插入键值对。
删除元素：
- erase(key)：从有序映射中删除键为 key 的键值对。
查找元素：
- find(key)：查找键为 key 的键值对在有序映射中的迭代器，若不存在返回映射的 end 迭代器。
获取元素个数：
- size()：返回有序映射中的键值对个数。
清空映射：
- clear()：清空有序映射中的所有键值对。
遍历映射：
- 使用迭代器进行遍历，可以通过循环遍历整个映射。

这些操作可以让你在使用 Ordered Set 和 Ordered Map 时进行插入、删除、查找等常见操作，以及获取元素个数、清空集合、遍历集合等常用操作。

下面是关于 Indexed Set 和 Indexed Map 的主要操作：

3.Indexed Set：

插入元素：
- insert(key)：向索引集合中插入元素 key。
删除元素：
- erase(key)：从索引集合中删除元素 key。
查找元素：
- find_by_order(order)：返回索引集合中第 order 小的元素的迭代器。
- order_of_key(key)：返回索引集合中比 key 小的元素的个数。
获取元素个数：
- size()：返回索引集合中的元素个数。
清空集合：
- clear()：清空索引集合中的所有元素。
遍历集合：
- 使用迭代器进行遍历，可以通过循环遍历整个集合。

4.Indexed Map：

插入键值对：
- insert(make_pair(key, value))：向索引映射中插入键值对。
删除元素：
- erase(key)：从索引映射中删除键为 key 的键值对。
查找元素：
- find_by_order(order)：返回索引映射中第 order 小的元素的迭代器。
- order_of_key(key)：返回索引映射中比 key 小的元素的个数。
获取元素个数：
- size()：返回索引映射中的键值对个数。
清空映射：
- clear()：清空索引映射中的所有键值对。
遍历映射：
- 使用迭代器进行遍历，可以通过循环遍历整个映射。

这些操作可以让你在使用 Indexed Set 和 Indexed Map 时进行插入、删除、查找等常见操作，以及获取元素个数、清空集合、遍历集合等常用操作。

下面是关于 Hashed Set 和 Hashed Map 的主要操作：

5.Hashed Set：

插入元素：
- insert(key)：向哈希集合中插入元素 key。
删除元素：
- erase(key)：从哈希集合中删除元素 key。
查找元素：
- find(key)：查找元素 key 是否存在于哈希集合中，返回元素的迭代器，若不存在返回集合的 end 迭代器。
获取元素个数：
- size()：返回哈希集合中的元素个数。
清空集合：
- clear()：清空哈希集合中的所有元素。
遍历集合：
- 使用迭代器进行遍历，可以通过循环遍历整个集合。

6.Hashed Map：

插入键值对：
- insert(make_pair(key, value))：向哈希映射中插入键值对。
删除元素：
- erase(key)：从哈希映射中删除键为 key 的键值对。
查找元素：
- find(key)：查找键为 key 的键值对是否存在于哈希映射中，返回键值对的迭代器，若不存在返回映射的 end 迭代器。
获取元素个数：
- size()：返回哈希映射中的键值对个数。
清空映射：
- clear()：清空哈希映射中的所有键值对。
遍历映射：
- 使用迭代器进行遍历，可以通过循环遍历整个映射。

这些操作可以让你在使用 Hashed Set 和 Hashed Map 时进行插入、删除、查找等常见操作，以及获取元素个数、清空集合、遍历集合等常用操作。

下面是关于 pb_ds 库中 Trie（字典树）的所有操作：

7.Trie（字典树）：

插入字符串：
- insert(str)：向字典树中插入字符串 str。
删除字符串：
- erase(str)：从字典树中删除字符串 str。
查找字符串：
- find(str)：查找字符串 str 是否存在于字典树中。
前缀查询：
- prefix(str)：查找所有以字符串 str 为前缀的字符串。
删除子树：
- erase_prefix(str)：从字典树中删除所有以字符串 str 为前缀的字符串及其子树。
获取字典树中字符串的个数：
- size()：返回字典树中的字符串个数。
清空字典树：
- clear()：清空字典树中的所有字符串。
遍历字典树：
- 通常使用递归或者迭代进行遍历，可以遍历字典树中的所有字符串。

以上是 pb_ds 库中 Trie（字典树）的所有操作。

下面是关于 pb_ds 库中 Priority Queue（优先队列）的所有操作：

8.Priority Queue（优先队列）：

插入元素：
- push(value)：向优先队列中插入元素 value。
删除顶部元素：
- pop()：删除优先队列中的顶部元素。
获取顶部元素：
- top()：返回优先队列中的顶部元素，即具有最高优先级的元素。
获取队列大小：
- size()：返回优先队列中的元素个数。
判断队列是否为空：
- empty()：如果优先队列为空，则返回 true；否则返回 false。
清空队列：
- clear()：清空优先队列中的所有元素。

以上是 pb_ds 库中 Priority Queue（优先队列）的所有操作。

下面是关于 pb_ds 库中 Bitsets 的所有操作：

9.Bitsets：

设置位：
- set(pos)：将指定位置 pos 的位设置为 1。
清除位：
- reset(pos)：将指定位置 pos 的位设置为 0。
翻转位：
- flip(pos)：将指定位置 pos 的位进行翻转（0 变为 1，1 变为 0）。
检查位：
- test(pos)：检查指定位置 pos 的位是否被设置为 1。
获取位数：
- size()：返回 Bitset 中的位数。
设置所有位：
- set()：将 Bitset 中的所有位设置为 1。
清除所有位：
- reset()：将 Bitset 中的所有位设置为 0。
翻转所有位：
- flip()：翻转 Bitset 中的所有位。
计算位为 1 的数量：
- count()：返回 Bitset 中位为 1 的数量。
按位操作：
- operator&, operator|, operator^, operator~：按位与、按位或、按位异或、按位取反操作。
位移操作：
- operator<<, operator>>：左移和右移操作。
获取位值：
- operator[]：用于访问指定位置的位值。
转换为整数：
- to_ulong()：将 Bitset 转换为对应的无符号整数。
转换为字符串：
- to_string()：将 Bitset 转换为对应的字符串表示。

以上是 pb_ds 库中 Bitsets 的所有操作。

下面是关于 pb_ds 库中 Traits（特性）的所有操作：

10.Traits（特性）：

允许重复元素：
- tree_order_statistics_node_update：允许数据结构中存在重复的元素。
禁止重复元素：
- tree_order_statistics_node_update：禁止数据结构中存在重复的元素。
允许修改键值：
- tree_order_statistics_node_update：允许修改数据结构中元素的键值。
禁止修改键值：
- tree_order_statistics_node_update：禁止修改数据结构中元素的键值。

以上是 pb_ds 库中 Traits（特性）的所有操作。

下面是关于 pb_ds 库中 Policy-Based Trie 的所有操作：

11.Policy-Based Trie：

插入元素：
- insert(key)：向 Trie 中插入字符串 key。
删除元素：
- erase(key)：从 Trie 中删除字符串 key。
查找元素：
- find(key)：查找字符串 key 是否存在于 Trie 中。
前缀查询：
- prefix(key)：查找所有以字符串 key 为前缀的字符串。
删除子树：
- erase_prefix(key)：从 Trie 中删除所有以字符串 key 为前缀的字符串及其子树。
获取 Trie 中字符串的个数：
- size()：返回 Trie 中的字符串个数。
清空 Trie：
- clear()：清空 Trie 中的所有字符串。
遍历 Trie：
- 通常使用递归或者迭代进行遍历，可以遍历 Trie 中的所有字符串。

以上是 pb_ds 库中 Policy-Based Trie 的所有操作。

下面是关于 pb_ds 库中 cc_hash_table 的所有操作：

12.cc_hash_table：

插入键值对：
- insert(make_pair(key, value))：向哈希表中插入键值对。
删除元素：
- erase(key)：从哈希表中删除键为 key 的键值对。
查找元素：
- find(key)：查找键为 key 的键值对是否存在于哈希表中，返回键值对的迭代器，若不存在返回哈希表的 end 迭代器。
获取元素个数：
- size()：返回哈希表中的键值对个数。
清空哈希表：
- clear()：清空哈希表中的所有键值对。
遍历哈希表：
- 使用迭代器进行遍历，可以通过循环遍历整个哈希表。

以上是 pb_ds 库中 cc_hash_table 的所有操作。

下面是关于 pb_ds 库中 Fenwick Tree 的所有操作：

13.Fenwick Tree：

更新单个元素：
- update(pos, val)：将位置 pos 的元素的值增加 val。
计算前缀和：
- prefix_sum(pos)：计算从位置 1 到位置 pos 的元素的和。
计算区间和：
- range_sum(start, end)：计算从位置 start 到位置 end 的元素的和。
获取单个元素的值：
- get(pos)：获取位置 pos 的元素的值。

以上是 pb_ds 库中 Fenwick Tree 的所有操作。

下面是关于 pb_ds 库中 String Hashing 的所有操作：

14.String Hashing：

计算字符串哈希值：
- hash_string(str)：计算字符串 str 的哈希值。
计算子串哈希值：
- hash_substring(str, start, length)：计算字符串 str 中从位置 start 开始、长度为 length 的子串的哈希值。
更新字符串哈希值（用于动态字符串）：
- update_hash(hash_value, old_char, new_char, pow_p)：根据旧字符 old_char 和新字符 new_char 更新字符串的哈希值。

以上是 pb_ds 库中 String Hashing 的所有操作。

下面是关于 pb_ds 库中 AVL Tree 的所有操作：

15.AVL Tree：

插入元素：
- insert(key)：向 AVL 树中插入元素 key。
删除元素：
- erase(key)：从 AVL 树中删除元素 key。
查找元素：
- find(key)：查找元素 key 是否存在于 AVL 树中。
获取最小元素：
- find_min()：返回 AVL 树中的最小元素。
获取最大元素：
- find_max()：返回 AVL 树中的最大元素。
获取树的高度：
- height()：返回 AVL 树的高度。
获取树的大小：
- size()：返回 AVL 树中的元素个数。
清空树：
- clear()：清空 AVL 树中的所有元素。

以上是 pb_ds 库中 AVL Tree 的所有操作。

下面是关于 pb_ds 库中 Leftist Tree 的所有操作：

16.Leftist Tree：

合并两棵左偏树：
- meld(tree1, tree2)：将两棵左偏树 tree1 和 tree2 合并成一棵左偏树。
插入元素：
- push(value)：向左偏树中插入元素 value。
删除最小元素：
- pop()：从左偏树中删除最小元素。
获取最小元素：
- top()：返回左偏树中的最小元素。
获取树的大小：
- size()：返回左偏树中的元素个数。
清空树：
- clear()：清空左偏树中的所有元素。

以上是 pb_ds 库中 Leftist Tree 的所有操作。

下面是关于 pb_ds 库中 Splay Tree 的所有操作：

17.Splay Tree：

插入元素：
- insert(key)：向 Splay 树中插入元素 key。
删除元素：
- erase(key)：从 Splay 树中删除元素 key。
查找元素：
- find(key)：查找元素 key 是否存在于 Splay 树中，并将其旋转到根节点。
获取最小元素：
- find_min()：返回 Splay 树中的最小元素，并将其旋转到根节点。
获取最大元素：
- find_max()：返回 Splay 树中的最大元素，并将其旋转到根节点。
获取树的大小：
- size()：返回 Splay 树中的元素个数。
清空树：
- clear()：清空 Splay 树中的所有元素。

以上是 pb_ds 库中 Splay Tree 的所有操作。

下面是关于 pb_ds 库中 Rational Arithmetic（分数运算）的所有操作：

18.Rational Arithmetic：

创建分数对象：
- make_pair(numerator, denominator)：创建一个分数对象，其中 numerator 表示分子，denominator 表示分母。
分数加法：
- add(fraction1, fraction2)：将两个分数相加，返回结果。
分数减法：
- subtract(fraction1, fraction2)：将一个分数减去另一个分数，返回结果。
分数乘法：
- multiply(fraction1, fraction2)：将两个分数相乘，返回结果。
分数除法：
- divide(fraction1, fraction2)：将一个分数除以另一个分数，返回结果。
比较分数大小：
- compare(fraction1, fraction2)：比较两个分数的大小关系，返回结果。
分数化简：
- simplify(fraction)：将一个分数化简为最简形式。
获取分子：
- numerator(fraction)：返回分数的分子。
获取分母：
- denominator(fraction)：返回分数的分母。

以上是 pb_ds 库中 Rational Arithmetic（分数运算）的所有操作。

下面是关于 pb_ds 库中 Monotonic Queue（单调队列）的所有操作：

19.Monotonic Queue：

插入元素：
- push_back(value)：向单调队列尾部插入元素 value。
删除队列头部元素：
- pop_front()：删除单调队列头部的元素。
获取队列头部元素：
- front()：返回单调队列头部的元素，即最早插入的元素。
获取队列尾部元素：
- back()：返回单调队列尾部的元素，即最近插入的元素。
获取队列大小：
- size()：返回单调队列中的元素个数。
清空队列：
- clear()：清空单调队列中的所有元素。
遍历队列：
- 使用迭代器进行遍历，可以通过循环遍历整个单调队列。
单调递增队列操作：
- push_back_increase(value)：向单调递增队列尾部插入元素，并确保队列中的元素是单调递增的。
- pop_front_increase()：删除单调递增队列头部的元素，并确保队列中的元素是单调递增的。
单调递减队列操作：
- push_back_decrease(value)：向单调递减队列尾部插入元素，并确保队列中的元素是单调递减的。
- pop_front_decrease()：删除单调递减队列头部的元素，并确保队列中的元素是单调递减的。

以上是 pb_ds 库中 Monotonic Queue（单调队列）的所有操作。

下面是关于 pb_ds 库中 Treap（树堆）的所有操作：

20.Treap：

插入元素：
- insert(key)：向 Treap 中插入元素 key。
删除元素：
- erase(key)：从 Treap 中删除元素 key。
查找元素：
- find(key)：查找元素 key 是否存在于 Treap 中。
获取最小元素：
- find_min()：返回 Treap 中的最小元素。
获取最大元素：
- find_max()：返回 Treap 中的最大元素。
获取树的大小：
- size()：返回 Treap 中的元素个数。
清空树：
- clear()：清空 Treap 中的所有元素。

以上是 pb_ds 库中 Treap（树堆）的所有操作。

21.Difference Constraints（差分约束）

Difference Constraints（差分约束）通常用于求解满足一系列线性不等式约束的变量的取值范围，常见于一些优化问题中，比如最短路问题和网络流问题。在 pb_ds 库中，差分约束可以通过 cc_hash_table 和 pb_ds 的一些数据结构来实现。

下面是一些常见的差分约束问题的解决方法：

Bellman-Ford 算法：适用于一般的差分约束问题。通过不断松弛边来更新节点的最短距离，直到收敛或者发现负权环。如果存在负权环，则说明问题无解。
SPFA 算法：是一种基于队列优化的 Bellman-Ford 算法，通常比 Bellman-Ford 算法更快地收敛。它可以解决一般的差分约束问题。
Floyd-Warshall 算法：适用于稠密图的差分约束问题。它可以求解所有点对之间的最短距离，包括负权边。
Dijkstra 算法：当差分约束问题满足无环图的条件时，可以使用 Dijkstra 算法求解。但需要注意，Dijkstra 算法不能处理负权边。

在 pb_ds 库中，你可以使用 cc_hash_table 来表示图的邻接表，利用其中的数据结构和算法来实现上述差分约束问题的求解。

具体实现的步骤通常包括：

将差分约束转化为图的形式，构建邻接表表示图的结构。
根据具体的算法选择合适的数据结构和算法来求解差分约束问题，比如 Bellman-Ford、SPFA、Floyd-Warshall 或 Dijkstra 等。
根据问题的具体要求，获取最终解或者判断是否存在解。

需要注意的是，差分约束问题的复杂度取决于图的结构和约束条件的数量，可能会随着问题规模的增大而增加。因此，在实际应用中，需要根据具体情况选择合适的算法和数据结构来求解差分约束问题。

22.Block Structures(分块)

在算法和数据结构中，”Block Structures” 通常指的是一种基于分块的数据结构，它将数据分割成固定大小的块（block），每个块中包含一定数量的元素。这种结构通常用于处理大规模数据，可以在保持较低时间复杂度的同时，降低对内存的需求。

常见的 Block Structures 包括但不限于：

分块链表（Block Linked List）：将链表分割成大小固定的块，每个块中包含多个元素。可以在常数时间内获取任意元素的指针，但插入和删除操作的时间复杂度较高。
分块数组（Block Array）：将数组分割成大小固定的块，每个块中包含多个元素。可以在常数时间内访问任意元素，但在插入和删除操作时可能需要移动其他元素。
分块树（Block Tree）：将树结构分割成大小固定的块，每个块中包含多个节点。可以在常数时间内执行一些查询操作，如查找、插入和删除。
分块哈希表（Block Hash Table）：将哈希表分割成大小固定的块，每个块中包含一定数量的键值对。可以在常数时间内执行一些查询操作，但可能需要处理冲突。
分块堆（Block Heap）：将堆结构分割成大小固定的块，每个块中包含一定数量的元素。可以在常数时间内执行一些查询操作，如获取最小或最大元素。
分块排序（Block Sorting）：将待排序的序列分割成大小固定的块，每个块中包含一定数量的元素。可以在常数时间内执行一些查询操作，如查找中位数。

分块结构通常能够提供较好的性能和空间效率，特别是在处理大规模数据时。但是，由于数据的分块可能会增加一些额外的操作开销，因此在选择使用分块结构时需要根据具体的应用场景和性能需求来进行权衡。

TangZiFan's Blog

I am not afraid of tomorrow for I have seen yesterday and love today.

C++的pb_ds库

C++的pb_ds库

1.Ordered Set：

2.Ordered Map：

3.Indexed Set：

4.Indexed Map：

5.Hashed Set：

6.Hashed Map：

7.Trie（字典树）：

8.Priority Queue（优先队列）：

9.Bitsets：

10.Traits（特性）：

11.Policy-Based Trie：

12.cc_hash_table：

13.Fenwick Tree：

14.String Hashing：

15.AVL Tree：

16.Leftist Tree：

17.Splay Tree：

18.Rational Arithmetic：

19.Monotonic Queue：

20.Treap：

21.Difference Constraints（差分约束）

22.Block Structures(分块)