文档:Policy-Based Data Structures
相关文章:pb_ds库实现支持多个相同的值的名次树
建议使用
using namespace __gnu_pbds; |
¶ tree
参考:https://www.cnblogs.com/keshuqi/p/6257895.html
文档:
tree
tree_order_statistics_node_update
¶ 头文件
¶ 原型
template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, typename Tag = rb_tree_tag, template< typename Node_CItr, typename Node_Itr, typename Cmp_Fn_, typename _Alloc_ > class Node_Update = null_node_update, typename _Alloc = std::allocator<char>> |
¶ 说明
- Mapped
被映射的东西。如果没有则为null_type - Tag
常用rb_tree_tag, splay_tree_tag - Node_Update
常用tree_order_statistics_node_update
。
它提供了以下成员函数
size_type order_of_key(key_const_reference key) const
返回比key
小的元素的个数iterator find_by_order (size_type order)
以及其const版本
返回第order
大的元素的迭代器
## 用法举例
- 一颗名次红黑树
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t;
## 常用成员函数 - clear
- insert
- erase
- lower_bound(Key key)
返回最小的 >= key 的元素的迭代器 - upper_bound
返回最小的 > key 的元素的迭代器 a.join(tree& b)
b并入a,前提是两棵树的key的取值范围不相交。b会被清空。a.split(Key v, tree& b)
key小于等于v的元素属于a,其余的属于b。b原有的元素会被清空。
¶ 堆
文档:https://gcc.gnu.org/onlinedocs/gcc-4.7.0/libstdc++/api/a00356.html
具体用法和普通优先队列差不多。
## 头文件
¶ 声明
template<typename _Tv, typename Cmp_Fn = std::less<_Tv>, typename Tag = pairing_heap_tag, typename _Alloc = std::allocator<char>> |
使用时必须带上__gnu_pbds::
,因为它与std::priority_queue
重名了。
¶ 迭代器
它的迭代器叫做point_iterator
。例如
__gnu_pbds::priority_queue<int>::point_iterator it; |
## Tag
- pairing_heap_tag
默认的,最快
- binary_heap_tag
- binomial_heap_tag
- rc_binomial_heap_tag
- thin_heap_tag
¶ 常用成员函数
同std::priority_queue
的成员函数有
- top
- size
- empty
- clear
- pop
不同的有
- push
返回迭代器
- join(priority_queue &other)
合并两个堆,other会被清空
- split(Pred prd,priority_queue &other)
分离出两个堆。其中Pred是predicate(谓词)的缩写,用于判断哪些元素被放入other中。如果prd(key)返回true,key被放入other中。
例如把a中小于3的数放入b中
template<typename T, T val> |
-
modify(point_iterator it,const key)
修改迭代器
it
指向的值为key
。