C++的pb_ds库

C++的pb_ds库

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

1. Ordered Set 和 Ordered Map

这两个数据结构允许自定义排序规则，提供了有序集合和有序映射的功能。

Ordered Set 主要操作：

• insert(key)：向有序集合中插入元素 key
• erase(key)：从有序集合中删除元素 key
• find(key)：查找元素 key 在有序集合中的迭代器
• lower_bound(key)：返回第一个不小于 key 的元素的迭代器
• upper_bound(key)：返回第一个大于 key 的元素的迭代器
• size()：返回有序集合中的元素个数
• clear()：清空有序集合中的所有元素

Ordered Map 主要操作：

• insert(make_pair(key, value))：向有序映射中插入键值对
• erase(key)：从有序映射中删除键为 key 的键值对
• find(key)：查找键为 key 的键值对
• size()：返回有序映射中的键值对个数

2. Indexed Set 和 Indexed Map

支持快速查询元素位置的有序集合和有序映射。

• find_by_order(order)：返回第 order 小的元素的迭代器
• order_of_key(key)：返回比 key 小的元素的个数

3. Hashed Set 和 Hashed Map

支持自定义哈希函数的哈希集合和哈希映射。

4. Trie（字典树）

用于高效存储和检索字符串集合的数据结构。

• insert(str)：向字典树中插入字符串
• erase(str)：从字典树中删除字符串
• find(str)：查找字符串是否存在于字典树中
• prefix(str)：查找所有以 str 为前缀的字符串

5. Priority Queue（优先队列）

支持自定义优先级规则的优先队列。

6. Fenwick Tree（树状数组）

用于高效处理动态前缀和的数据结构。

7. 其他数据结构

pb_ds 还提供了 AVL Tree、Leftist Tree、Splay Tree、Treap、Monotonic Queue 等多种高级数据结构的实现，可根据具体需求选用。