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_key
和find_by_order
。
这是一些常用的成员函数(基于 Cmp_Fn
比较):
insert(x)
返回std::pair<point_iterator, bool>
erase(x)
删除一个元素或迭代器- $x$ 为迭代器:返回下一个迭代器,若为末尾则返回
end()
- $x$ 为元素:返回是否删除成功(不存在就删除失败咯)
- $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$ 当前树内的所有值),否则会throw
出join_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
个位置替换为other
,len
可省略:$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]);