前のページ

pb_ds 速通

来试试最新最酷最潮的扩展 STL 简介吧

Intro

深度好文

成文过程中参考了大量资料,这里一并谢过。

我在 2024.11.22 调试 LG P2596 到凌晨 00:32:21 破防所以加快学习了 pb_ds

pb_ds: Policy-Based Data Structures。封装了很多有用的数据结构,常用的有:

  • Hash
  • 平衡树
  • 字典树
  • 可持久化平衡树

但是严格上讲 pb_ds 并不属于 STL,只在使用 libstdc++ 为标准库的编译器下可以使用,主要内容位于 namespace __gnu_pbds 中,经 CCF 声明,在 NOI 系列比赛中可以使用(天天用 __lg__gcd 了还怕这个?)

一般而言,pb_ds 常数较大。

使用 pb_ds 需要:

#include <ext/pb_ds/assoc_container.hpp> // 必须引用,理解为底层定义
#include <ext/pb_ds/tree_policy.hpp> // tree
#include <ext/pb_ds/hash_policy.hpp> // hash
#include <ext/pb_ds/trie_policy.hpp> // trie
#include <ext/pb_ds/priority_queue.hpp> // priority_queue

有万能头,但是 Win 无法过编:

#include <bits/extc++.h>

hash & trie

pb_ds 中有两个 Hash:

cc_hash_table<Key, Value>;
gp_hash_table<Key, Value>;

第一个使用了拉链法第二个则是探测法,但是注意到我们有更稳定好用的 std::map 和手动重载后的 std::unordered_map,故在此不做赘述。

trie 类用的也比较少,毕竟手写 Trie 并不困难,而且 Trie 实在是太重要了,包括延伸出的 01-Trie……可以看源文件了解一下成员函数。

__gnu_pbds::trie<string, null_type,
                 trie_string_access_traits<>,
                 pat_trie_tag,
                 trie_prefix_search_node_update> tr;

/* 常用的操作 */
tr.insert(str);
tr.erase(str);
tr.join(another_trie);

// 遍历某一个前缀的所有字符串
std::pair<Trie::iterator, Trie::iterator> range = tr.prefix_range(prefix);
for (auto it = range.first; it != range.second; ++it) {
  cout << *it << endl;
}

priority_queue

Why not try OI-Wiki? and official docs?

学习一下仿函数便于重定义堆的排序,本质上为重载括号运算符,在 Template 中比较常用,使用方法如:

template <typename T>
struct comp {
    bool operator() (const T &x, const T &y) {
        return dis[x] > dis[y];
    }
};

std::priority_queue<int, std::vector<int>, comp> q;

这样我们的 std::priority_queue 就是存储下标,按照 $dis_i$ 来排序的小根堆。

定义如:

__gnu_pbds::priority_queue<T, Compare, Tag, Allocator>

第四个在 OI 中基本不会用到,Tag 的另外几种可以看 OI-Wiki,但是基本上我们只在自定义非原生元素时使用 pb_ds 的堆,而其中 pairing_heap_tag 的表现是最佳的。

这是一些常用的成员函数:

  • push()(会返回元素位置迭代器)
  • pop()
  • top()
  • size()
  • empty()
  • modify(point_iterator, const key) 重要好用,均摊是 $\log n$ 的
  • erase(point_iterator)
  • join(__gnu_pbds::priority_queue &x) 重要好用,合并到当前堆的同时清空 $x$

tree

Why not try OI-Wiki? and official docs?

定义如:

__gnu_pbds::tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag,
                 Node_Update = null_tree_node_update,
                 Allocator = std::allocator<char>>

其中注意到:

  • Mapped 表示映射规则,一般而言我们使用 null_type 表示无映射(类似于丢进 std::set 里);若关联到带值的集合(类似于丢到 std::map 里),则填入类似 std::map<Key, Value> 中的 Value 类型。
  • Tag 表示底层平衡树类型,一般而言我们使用 rb_tree_tag,这是一种跑得飞快但是极为难调难写的平衡树
  • Node_Update 一般使用 tree_order_statistics_node_update,因为我们需要使用 order_of_keyfind_by_order

这是一些常用的成员函数(基于 Cmp_Fn 比较):

  • insert(x) 返回 std::pair<point_iterator, bool>
  • erase(x) 删除一个元素或迭代器
    • $x$ 为迭代器:返回下一个迭代器,若为末尾则返回 end()
    • $x$ 为元素:返回是否删除成功(不存在就删除失败咯)
  • order_of_key(x):返回从 $0$ 开始的排名
  • find_by_order(x) 返回对于排名所对于元素的迭代器
  • lower_bound(x) 前驱
  • upper_bound(x) 后继
  • join(x)比较函数和元素类型 相同的情况下合并两棵 tree 到当前树,清空 $x$
  • split(x, b) 小于等于 $x$ 的属于当前树,其余的属于 $b$ 树
  • empty()
  • size()

!!!join(x) 函数需要保证两棵树的值域 不相交(也就是并入树内所有值必须全部 $\gt / \lt$ 当前树内的所有值),否则会 throwjoin_error

如果要合并两棵树且有交集,则需要将一棵树的元素一一插入到另一棵树中

rope

用于实现可持久化数组、可持久化平衡树。

如前文所述,严格来说,pb_ds 不属于 STL,然而 rope 不属于 pb_ds,头文件位于 rope,在命名空间 __gnu_cxx 中。

__gnu_cxx::rope 支持:

  • at(x) / operator[]:$O(1)$
  • push_back() / append:$O(\log n)$
  • insert(x, other)x 的位置插入另一个串:$T_{\min} O(\log n) / T_{\max} O(n)$
  • erase(x, len) 删除 x 位置开始的 len 个元素:$O(\log n)$
  • replace(x, len, other)x 位置开始的 len 个位置替换为 otherlen 可省略:$O(\log n)$
  • substr(x, len)x 开始 len 位截取:$O(\log n)$
  • operator + 联结两个 rope

黑科技:支持 $O(1)$ 复制,还不炸空间:

constexpr int N = 1e5 + 7;

rope<int> *his[N];
his[i] = new rope<int> (*his[i - 1]);
「馬鹿なわたしは歌うだけ」