Boost C++ 库

typedef bstree_algo::insert_commit_data insert_commit_data;

此类型是 insert_unique_check 将填充的信息

static node_ptr get_header(const_node_ptr n) noexcept;

要求：'n' 是树的节点或头部节点。

效果：返回树的头部。

复杂度：对数。

抛出：无。

static node_ptr begin_node(const_node_ptr header) noexcept;

要求：'header' 是树的头部节点。

效果：返回树的第一个节点，如果树为空则返回头部。

复杂度：常量时间。

抛出：无。

static node_ptr end_node(const_node_ptr header) noexcept;

要求：'header' 是树的头部节点。

效果：返回树的头部。

复杂度：常量时间。

抛出：无。

static void swap_tree(node_ptr header1, node_ptr header2);

要求：header1 和 header2 必须是两个树的头部节点。

效果：交换两个树。函数执行后，header1 将包含指向第二个树的链接，header2 将包含指向第一个树的链接。

复杂度：常量。

抛出：无。

static void swap_nodes(node_ptr node1, node_ptr node2) noexcept;

要求：node1 和 node2 不能是两个树的头部节点。

效果：交换两个节点。函数执行后，node1 将被插入到 node2 原来的位置之前，node2 将被插入到 node1 原来的位置之前。

复杂度：对数。

抛出：无。

注意：如果 node1 和 node2 根据排序规则不相等，此函数将破坏容器的排序不变量。

实验性函数

static void swap_nodes(node_ptr node1, node_ptr header1, node_ptr node2, 
                       node_ptr header2) noexcept;

要求：node1 和 node2 不能是具有头部 header1 和 header2 的两个树的头部节点。

效果：交换两个节点。函数执行后，node1 将被插入到 node2 原来的位置之前，node2 将被插入到 node1 原来的位置之前。

复杂度：常量。

抛出：无。

注意：如果 node1 和 node2 根据排序规则不相等，此函数将破坏容器的排序不变量。

实验性函数

static void replace_node(node_ptr node_to_be_replaced, node_ptr new_node) noexcept;

要求：node_to_be_replaced 必须已插入到树中，而 new_node 必须未插入到树中。

效果：用 new_node 替换其在树中位置上的 node_to_be_replaced。树不需要重新平衡。

复杂度：对数。

抛出：无。

注意：如果 new_node 根据排序规则不等于 node_to_be_replaced，此函数将破坏容器的排序不变量。此函数比删除和插入节点更快，因为无需重新平衡和比较。实验性函数

static void replace_node(node_ptr node_to_be_replaced, node_ptr header, 
                         node_ptr new_node) noexcept;

要求：node_to_be_replaced 必须已插入到具有头部 "header" 的树中，而 new_node 必须未插入到树中。

效果：用 new_node 替换其在树中位置上的 node_to_be_replaced。树不需要重新平衡。

复杂度：常量。

抛出：无。

注意：如果 new_node 根据排序规则不等于 node_to_be_replaced，此函数将破坏容器的排序不变量。此函数比删除和插入节点更快，因为无需重新平衡或比较。实验性函数

static void unlink(node_ptr n) noexcept;

要求：'n' 是一个树节点，但不是头部。

效果：移除节点并将树重新平衡。

复杂度：平均复杂度为常量时间。

抛出：无。

static node_ptr unlink_leftmost_without_rebalance(node_ptr header) noexcept;

要求：header 是树的头部。

效果：从树中移除最左边的节点，并更新头部链接指向新的最左边节点。

复杂度：平均复杂度为常量时间。

抛出：无。

注意：此函数会破坏树，并且只能用于后续的 unlink_leftmost_without_rebalance 调用。此函数通常用于实现树的逐步受控销毁。

static bool unique(const_node_ptr n) noexcept;

要求：'n' 是树的节点或由 init(...) 或 init_node() 初始化过的节点。

效果：如果节点是由 init() 或 init_node() 初始化，则返回 true。

复杂度：常量时间。

抛出：无。

static std::size_t size(const_node_ptr header) noexcept;

要求：'header' 是树的头部。

效果：返回树中的节点数。

复杂度：线性时间。

抛出：无。

static node_ptr next_node(node_ptr n) noexcept;

要求：'n' 是树中的一个节点，不是头部。

效果：返回树中的下一个节点。

复杂度：平均常数时间。

抛出：无。

static node_ptr prev_node(node_ptr n) noexcept;

要求：'n' 是树中的一个节点，不是最左边的节点。

效果：返回树中的上一个节点。

复杂度：平均常数时间。

抛出：无。

static void init(node_ptr n) noexcept;

要求：'n' 不能是任何树的一部分。

效果：函数执行后，unique(node) == true。

复杂度：常量。

抛出：无。

节点：如果节点被插入到树中，此函数会破坏树。

static void init_header(node_ptr header) noexcept;

要求：header 不能是任何树的一部分。

效果：将头部初始化为表示一个空树。unique(header) == true。

复杂度：常量。

抛出：无。

节点：如果头部被插入到树中，此函数会破坏树。

static void erase(node_ptr header, node_ptr z) noexcept;

要求：header 必须是树的头部，z 是该树的一个非头部节点。

效果：从具有头部 "header" 的树中删除节点 "z"。

复杂度：摊销常数时间。

抛出：无。附加说明：对 z 的前驱节点进行伸展以加速范围删除。

template<typename NodePtrCompare> 
  static bool transfer_unique(node_ptr header1, NodePtrCompare comp, 
                              node_ptr header2, node_ptr z);

要求：header1 和 header2 分别是 tree1 和 tree2 的头部节点，z 是 tree1 的非头部节点。NodePtrCompare 是 tree1 的比较函数。

效果：如果 tree1 不包含与 z 等效的节点，则将节点 "z" 从 tree1 转移到 tree2。

返回值：如果节点被转移，则返回 true，否则返回 false。

复杂度：对数。

抛出：如果比较操作抛出异常。

template<typename NodePtrCompare> 
  static void transfer_equal(node_ptr header1, NodePtrCompare comp, 
                             node_ptr header2, node_ptr z);

要求：header1 和 header2 分别是 tree1 和 tree2 的头部节点，z 是 tree1 的非头部节点。NodePtrCompare 是 tree1 的比较函数。

效果：将节点 "z" 从 tree1 转移到 tree2。

复杂度：对数。

抛出：如果比较操作抛出异常。

template<typename Cloner, typename Disposer> 
  static void clone(const_node_ptr source_header, node_ptr target_header, 
                    Cloner cloner, Disposer disposer);

要求："cloner" 必须是一个函数对象，它接受一个 node_ptr 并返回其克隆的新节点。"disposer" 必须接受一个 node_ptr 并且不抛出异常。

效果：首先清空目标树，为树中的每个节点（除了头部）调用 void disposer::operator()(node_ptr)。

然后，复制“source_header”指向的整个树，使用 node_ptr Cloner::operator()(node_ptr) 克隆每个源节点，以获得目标树的节点。如果“cloner”抛出异常，则使用 void disposer(node_ptr ) 处理克隆的目标节点。

复杂度：调用此函数时，复杂度与源树的元素数量加上目标树的元素数量成线性关系。

抛出：如果 cloner 函数对象抛出异常。如果发生这种情况，将处理目标节点。

template<typename Disposer> 
  static void clear_and_dispose(node_ptr header, Disposer disposer) noexcept;

要求："disposer" 必须是一个函数对象，它接受一个 node_ptr 参数并且不抛出异常。

效果：清空目标树，为树中的每个节点（除了头部）调用 void disposer::operator()(node_ptr)。

复杂度：调用此函数时，复杂度与源树的元素数量加上目标树的元素数量成线性关系。

抛出：无。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::size_t 
  count(node_ptr header, const KeyType & key, KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：返回根据 "comp" 与 "key" 相等的元素的数量。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：对键为 key 的元素进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::size_t 
  count(const_node_ptr header, const KeyType & key, KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：返回根据 "comp" 与 "key" 相等的元素的数量。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：不执行伸展操作。

template<typename KeyType, typename KeyNodePtrCompare> 
  static node_ptr 
  lower_bound(node_ptr header, const KeyType & key, KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：根据 "comp" 返回第一个不小于 "key" 的元素的 node_ptr，如果不存在这样的元素则返回 "header"。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：对范围的第一个节点进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static node_ptr 
  lower_bound(const_node_ptr header, const KeyType & key, 
              KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：根据 "comp" 返回第一个不小于 "key" 的元素的 node_ptr，如果不存在这样的元素则返回 "header"。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：不执行伸展操作。

template<typename KeyType, typename KeyNodePtrCompare> 
  static node_ptr 
  upper_bound(node_ptr header, const KeyType & key, KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：根据 "comp" 返回第一个大于 "key" 的元素的 node_ptr，如果不存在这样的元素则返回 "header"。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：对范围的第一个节点进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static node_ptr 
  upper_bound(const_node_ptr header, const KeyType & key, 
              KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：根据 "comp" 返回第一个大于 "key" 的元素的 node_ptr，如果不存在这样的元素则返回 "header"。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：不执行伸展操作。

template<typename KeyType, typename KeyNodePtrCompare> 
  static node_ptr 
  find(node_ptr header, const KeyType & key, KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：根据 "comp" 返回第一个等于 "key" 的元素的 node_ptr，如果不存在这样的元素则返回 "header"。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：对找到的下界节点进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static node_ptr 
  find(const_node_ptr header, const KeyType & key, KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：根据 "comp" 返回第一个等于 "key" 的元素的 node_ptr，如果不存在这样的元素则返回 "header"。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：不执行伸展操作。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::pair< node_ptr, node_ptr > 
  equal_range(node_ptr header, const KeyType & key, KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：返回一个 node_ptr 对，该对界定一个包含所有根据“comp”等效于“key”的元素的范围，或者一个空范围，表示如果不存在等效元素，则这些元素可能存在的位置。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：对范围的第一个节点进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::pair< node_ptr, node_ptr > 
  equal_range(const_node_ptr header, const KeyType & key, 
              KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：返回一个 node_ptr 对，该对界定一个包含所有根据“comp”等效于“key”的元素的范围，或者一个空范围，表示如果不存在等效元素，则这些元素可能存在的位置。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：不执行伸展操作。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::pair< node_ptr, node_ptr > 
  lower_bound_range(node_ptr header, const KeyType & key, 
                    KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：返回一个 node_ptr 对，该对界定一个包含根据“comp”等效于“key”的第一个元素的范围，或者一个空范围，表示如果不存在该元素，则该元素可能存在的位置。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：对范围的第一个节点进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::pair< node_ptr, node_ptr > 
  lower_bound_range(const_node_ptr header, const KeyType & key, 
                    KeyNodePtrCompare comp);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。

效果：返回一个 node_ptr 对，该对界定一个包含根据“comp”等效于“key”的第一个元素的范围，或者一个空范围，表示如果不存在该元素，则该元素可能存在的位置。

复杂度：对数。

抛出：如果“comp”抛出异常。附加说明：不执行伸展操作。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::pair< node_ptr, node_ptr > 
  bounded_range(node_ptr header, const KeyType & lower_key, 
                const KeyType & upper_key, KeyNodePtrCompare comp, 
                bool left_closed, bool right_closed);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。根据“comp”，“lower_key”不得大于“upper_key”。如果“lower_key”==“upper_key”，则（“left_closed”||“right_closed”）必须为 true。

效果：返回具有以下标准的 pair。

first = lower_bound(lower_key) 如果 left_closed，否则 upper_bound(lower_key)

second = upper_bound(upper_key) 如果 right_closed，否则 lower_bound(upper_key)

复杂度：对数。

抛出：如果 "comp" 抛出异常。

注意：与为 lower_key 和 upper_key 调用 upper_bound 和 lower_bound 相比，此函数可能更有效。

注意：实验性函数，接口可能会更改。附加说明：对范围的第一个节点进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::pair< node_ptr, node_ptr > 
  bounded_range(const_node_ptr header, const KeyType & lower_key, 
                const KeyType & upper_key, KeyNodePtrCompare comp, 
                bool left_closed, bool right_closed);

要求：“header”必须是树的头节点。KeyNodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。KeyNodePtrCompare 可以比较 KeyType 与树的 node_ptrs。根据“comp”，“lower_key”不得大于“upper_key”。如果“lower_key”==“upper_key”，则（“left_closed”||“right_closed”）必须为 true。

效果：返回具有以下标准的 pair。

first = lower_bound(lower_key) 如果 left_closed，否则 upper_bound(lower_key)

second = upper_bound(upper_key) 如果 right_closed，否则 lower_bound(upper_key)

复杂度：对数。

抛出：如果 "comp" 抛出异常。

注意：与为 lower_key 和 upper_key 调用 upper_bound 和 lower_bound 相比，此函数可能更有效。

注意：实验性函数，接口可能会更改。附加说明：不执行伸展操作。

template<typename NodePtrCompare> 
  static node_ptr 
  insert_equal_upper_bound(node_ptr header, node_ptr new_node, 
                           NodePtrCompare comp);

要求：“h”必须是树的头节点。NodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。NodePtrCompare 比较两个 node_ptrs。

效果：根据 "comp"，在 upper bound 之前将 new_node 插入到树中。

复杂度：插入元素的平均复杂度最多为对数。

抛出：如果“comp”抛出异常。附加说明：对插入的节点进行伸展。

template<typename NodePtrCompare> 
  static node_ptr 
  insert_equal_lower_bound(node_ptr header, node_ptr new_node, 
                           NodePtrCompare comp);

要求：“h”必须是树的头节点。NodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。NodePtrCompare 比较两个 node_ptrs。

效果：根据 "comp"，在 lower bound 之前将 new_node 插入到树中。

复杂度：插入元素的平均复杂度最多为对数。

抛出：如果“comp”抛出异常。附加说明：对插入的节点进行伸展。

template<typename NodePtrCompare> 
  static node_ptr 
  insert_equal(node_ptr header, node_ptr hint, node_ptr new_node, 
               NodePtrCompare comp);

要求：“header”必须是树的头节点。NodePtrCompare 是一个函数对象，它引发一个严格弱序，该序与用于创建树的严格弱序兼容。NodePtrCompare 比较两个 node_ptrs。“hint”是来自“header”树的节点。

效果：使用 "hint" 作为插入提示，将 new_node 插入到树中。如果 "hint" 是 upper_bound，则插入需要常数时间（最坏情况为两次比较）。

复杂度：一般情况下为对数时间，但如果 new_node 被插入到 "hint" 之前，则为摊还的常数时间。

抛出：如果“comp”抛出异常。附加说明：对插入的节点进行伸展。

static node_ptr 
insert_before(node_ptr header, node_ptr pos, node_ptr new_node) noexcept;

要求：“header”必须是树的头节点。“pos”必须是一个有效的迭代器或头节点（尾部）节点。“pos”必须是一个迭代器，指向插入“new_node”后根据已插入节点的顺序，其后面的节点。此函数不检查“pos”，此前提条件必须由调用者保证。

效果：在 "pos" 之前将 new_node 插入到树中。

复杂度：常数时间。

抛出：无。

注意：如果“pos”不是新插入的“new_node”的后继节点，则可能破坏树的不变量。附加说明：对插入的节点进行伸展。

static void push_back(node_ptr header, node_ptr new_node) noexcept;

要求："header" 必须是树的 header 节点。根据使用的排序规则，"new_node" 必须不小于已插入的最大键。

效果：在 "pos" 之前将 new_node 插入到树中。

复杂度：常数时间。

抛出：无。

注意：如果“new_node”小于已插入的最大键，则破坏树的不变量。此函数比使用“insert_before”稍快。附加说明：对插入的节点进行伸展。

static void push_front(node_ptr header, node_ptr new_node) noexcept;

要求："header" 必须是树的 header 节点。根据使用的排序规则，"new_node" 必须不大于已插入的最小键。

效果：在 "pos" 之前将 new_node 插入到树中。

复杂度：常数时间。

抛出：无。

注意：如果“new_node”大于已插入的最小键，则破坏树的不变量。此函数比使用“insert_before”稍快。附加说明：对插入的节点进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::pair< node_ptr, bool > 
  insert_unique_check(node_ptr header, const KeyType & key, 
                      KeyNodePtrCompare comp, 
                      insert_commit_data & commit_data);

附加说明：对具有给定键的节点进行伸展。

template<typename KeyType, typename KeyNodePtrCompare> 
  static std::pair< node_ptr, bool > 
  insert_unique_check(node_ptr header, node_ptr hint, const KeyType & key, 
                      KeyNodePtrCompare comp, 
                      insert_commit_data & commit_data);

附加说明：对具有给定键的节点进行伸展。

static void insert_unique_commit(node_ptr header, node_ptr new_value, 
                                 const insert_commit_data & commit_data) noexcept;

static bool is_header(const_node_ptr p) noexcept;

要求：p 是树中的一个节点。

效果：如果 p 是树的头部，则返回 true。

复杂度：常量。

抛出：无。

static void rebalance(node_ptr header) noexcept;

要求：header 必须是树的头节点。

效果：重新平衡树。

抛出：无。

复杂度：线性。

static node_ptr rebalance_subtree(node_ptr old_root) noexcept;

要求：old_root 是树的节点。它不应为 null。

效果：重新平衡以 old_root 为根的子树。

返回：子树的新根。

抛出：无。

复杂度：线性。

static void splay_up(node_ptr n, node_ptr header) noexcept;

template<typename KeyType, typename KeyNodePtrCompare> 
  static node_ptr 
  splay_down(node_ptr header, const KeyType & key, KeyNodePtrCompare comp, 
             bool * pfound = 0);