平衡树


__gnu_pbds :: tree

附:官方文档地址

模板形参

  • Key: 储存的元素类型,如果想要存储多个相同的 Key 元素,则需要使用类似于 std::pairstruct 的方法,并配合使用 lower_boundupper_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_keyfind_by_order 方法,需要使用 tree_order_statistics_node_update
  • Allocator:空间分配器类型

构造方式

成员函数

  • 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():返回大小。

示例

贡献者:@Ir1d@Flex@Danni@opsiff

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组