平衡树
__gnu_pbds::tree
附:官方文档地址
1 2 3 4 5 6 |
|
模板形参
Key
: 储存的元素类型,如果想要存储多个相同的Key
元素,则需要使用类似于std::pair
和struct
的方法,并配合使用lower_bound
和upper_bound
成员函数进行查找Mapped
: 映射规则(Mapped-Policy)类型,如果要指示关联容器是 集合,类似于存储元素在std::set
中,此处填入null_type
,低版本g++
此处为null_mapped_type
;如果要指示关联容器是 带值的集合,类似于存储元素在std::map
中,此处填入类似于std::map<Key, Value>
的Value
类型Cmp_Fn
: 关键字比较函子,例如std::less<Key>
Tag
: 选择使用何种底层数据结构类型,默认是rb_tree_tag
。__gnu_pbds
提供不同的三种平衡树,分别是:rb_tree_tag
:红黑树,一般使用这个,后两者的性能一般不如红黑树splay_tree_tag
:splay 树ov_tree_tag
:有序向量树,只是一个由vector
实现的有序结构,类似于排序的vector
来实现平衡树,性能取决于数据想不想卡你
Node_Update
:用于更新节点的策略,默认使用null_node_update
,若要使用order_of_key
和find_by_order
方法,需要使用tree_order_statistics_node_update
Allocator
:空间分配器类型
构造方式
1 2 3 4 |
|
成员函数
insert(x)
:向树中插入一个元素 x,返回std::pair<point_iterator, bool>
。erase(x)
:从树中删除一个元素/迭代器 x,返回一个bool
表明是否删除成功。order_of_key(x)
:返回 x 以Cmp_Fn
比较的排名。find_by_order(x)
:返回Cmp_Fn
比较的排名所对应元素的迭代器。lower_bound(x)
:以Cmp_Fn
比较做lower_bound
,返回迭代器。upper_bound(x)
:以Cmp_Fn
比较做upper_bound
,返回迭代器。join(x)
:将 x 树并入当前树,前提是两棵树的类型一样,x 树被删除。split(x,b)
:以Cmp_Fn
比较,小于等于 x 的属于当前树,其余的属于 b 树。empty()
:返回是否为空。size()
:返回大小。
注意
join(x)
函数需要保证并入树的键的值域与被并入树的键的值域不相交,否则会抛出 join_error
异常。
如果要合并两棵值域有交集的树,需要将一棵树的元素一一插入到另一棵树中。
示例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
|
参考资料
本页面最近更新:2024/10/9 22:38:42,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:ChungZH, HeRaNO, Ir1d, isdanni, ksyx, opsiff, Tiphereth-A, Xeonacid, zyzzyh
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用