pb_ds学习笔记

阅读量: searchstar 2020-03-30 22:39:47
Categories: Tags:

文档: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

头文件

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

原型

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>>
class __gnu_pbds::tree< Key, Mapped, Cmp_Fn, Tag, Node_Update, _Alloc >

说明

  1. size_type order_of_key(key_const_reference key) const
    返回比key小的元素的个数
  2. iterator find_by_order (size_type order)以及其const版本
    返回第order大的元素的迭代器
    ## 用法举例
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t;

常用成员函数

文档:https://gcc.gnu.org/onlinedocs/gcc-4.7.0/libstdc++/api/a00356.html

具体用法和普通优先队列差不多。
## 头文件

#include<ext/pb_ds/priority_queue.hpp>

声明

template<typename _Tv, typename Cmp_Fn = std::less<_Tv>, typename Tag = pairing_heap_tag, typename _Alloc = std::allocator<char>>
class __gnu_pbds::priority_queue< _Tv, Cmp_Fn, Tag, _Alloc >

使用时必须带上__gnu_pbds::,因为它与std::priority_queue重名了。

迭代器

它的迭代器叫做point_iterator。例如

__gnu_pbds::priority_queue<int>::point_iterator it;

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>
struct less_than {
	bool operator () (T x) {
		return x < val;
	}
};

a.split(less_than<int, 3>(), b);