Boost C++ 库

splaytree();

效果：构造一个空容器。

复杂度：常量。

抛出：如果 value_traits::node_traits::node 的构造函数抛出（使用预定义的 Boost.Intrusive 钩子时不会发生此情况），或者 key_compare 对象的复制构造函数抛出。基本保证。

explicit splaytree(const key_compare & cmp, 
                   const value_traits & v_traits = value_traits());

template<typename Iterator> 
  splaytree(bool unique, Iterator b, Iterator e, 
            const key_compare & cmp = key_compare(), 
            const value_traits & v_traits = value_traits());

splaytree(splaytree && x);

效果：构造一个容器，将资源从另一个容器移动过来。内部比较对象和值特性被移动构造，属于 x 的节点（除了表示“结束”的节点）会被链接到 *this。

复杂度：常量。

抛出：如果 value_traits::node_traits::node 的移动构造函数抛出（使用预定义的 Boost.Intrusive 钩子时不会发生此情况），或者比较对象的移动构造函数抛出。

splaytree & operator=(splaytree && x);

效果：等同于 swap。

~splaytree();

效果：从本容器中分离所有元素。集合中的对象不会被删除（即不会调用析构函数），但根据 value_traits 模板参数，节点会被重新初始化，从而可以被复用。

复杂度：相对于 *this 中的元素为线性。

抛出：无。

iterator begin() noexcept;

效果：返回一个指向容器开头的迭代器。

复杂度：常量。

抛出：无。

const_iterator begin() const noexcept;

效果：返回一个指向容器开头的 const_iterator。

复杂度：常量。

抛出：无。

const_iterator cbegin() const noexcept;

效果：返回一个指向容器开头的 const_iterator。

复杂度：常量。

抛出：无。

iterator end() noexcept;

效果：返回一个指向容器末尾的迭代器。

复杂度：常量。

抛出：无。

const_iterator end() const noexcept;

效果：返回一个指向容器末尾的 const_iterator。

复杂度：常量。

抛出：无。

const_iterator cend() const noexcept;

效果：返回一个指向容器末尾的 const_iterator。

复杂度：常量。

抛出：无。

reverse_iterator rbegin() noexcept;

效果：返回一个指向反向容器开头的 reverse_iterator。

复杂度：常量。

抛出：无。

const_reverse_iterator rbegin() const noexcept;

效果：返回一个指向反向容器开头的 const_reverse_iterator。

复杂度：常量。

抛出：无。

const_reverse_iterator crbegin() const noexcept;

效果：返回一个指向反向容器开头的 const_reverse_iterator。

复杂度：常量。

抛出：无。

reverse_iterator rend() noexcept;

效果：返回一个指向反向容器末尾的 reverse_iterator。

复杂度：常量。

抛出：无。

const_reverse_iterator rend() const noexcept;

效果：返回一个指向反向容器末尾的 const_reverse_iterator。

复杂度：常量。

抛出：无。

const_reverse_iterator crend() const noexcept;

效果：返回一个指向反向容器末尾的 const_reverse_iterator。

复杂度：常量。

抛出：无。

iterator root() noexcept;

效果：返回一个指向容器根节点的迭代器，如果根节点不存在，则返回 end()。

复杂度：常量。

抛出：无。

const_iterator root() const noexcept;

效果：返回一个指向容器根节点的 const_iterator，如果根节点不存在，则返回 cend()。

复杂度：常量。

抛出：无。

const_iterator croot() const noexcept;

效果：返回一个指向容器根节点的 const_iterator，如果根节点不存在，则返回 cend()。

复杂度：常量。

抛出：无。

key_compare key_comp() const;

效果：返回容器使用的 key_compare 对象。

复杂度：常量。

抛出：如果 key_compare 的复制构造函数抛出。

value_compare value_comp() const;

效果：返回容器使用的 value_compare 对象。

复杂度：常量。

抛出：如果 value_compare 的复制构造函数抛出。

bool empty() const noexcept;

效果：如果容器为空，则返回 true。

复杂度：常量。

抛出：无。

size_type size() const noexcept;

效果：返回容器中存储的元素数量。

复杂度：如果启用了常量时间大小选项，则为常量时间；否则，相对于 *this 中的元素为线性。

抛出：无。

void swap(splaytree & other);

效果：交换两个容器的内容。

复杂度：常量。

抛出：如果比较函子的 swap 调用抛出。

template<typename Cloner, typename Disposer> 
  void clone_from(const splaytree & src, Cloner cloner, Disposer disposer);

要求：Disposer::operator()(pointer) 不应抛出。Cloner 应产生与原始节点等效的节点。

效果：通过调用 Disposer::operator()(pointer) 来删除 *this 中的所有元素，通过调用 Cloner::operator()(const_reference) 来克隆 src 中的所有元素，并将它们插入到 *this 中。从源容器复制谓词。

如果 cloner 抛出，所有克隆的元素都会被解除链接并调用 Disposer::operator()(pointer) 进行处理。

复杂度：相对于擦除和插入的元素为线性。

抛出：如果 cloner 抛出异常或谓词复制赋值抛出异常。基本保证。附加说明：它还从源容器复制 alpha 因子。

template<typename Cloner, typename Disposer> 
  void clone_from(splaytree && src, Cloner cloner, Disposer disposer);

要求：Disposer::operator()(pointer) 不应抛出。Cloner 应产生与原始节点等效的节点。

效果：通过调用 Disposer::operator()(pointer) 来删除 *this 中的所有元素，通过调用 Cloner::operator()(reference) 来克隆 src 中的所有元素，并将它们插入到 *this 中。从源容器复制谓词。

如果 cloner 抛出，所有克隆的元素都会被解除链接并调用 Disposer::operator()(pointer) 进行处理。

复杂度：相对于擦除和插入的元素为线性。

抛出：如果 cloner 抛出或谓词复制赋值抛出。基本保证。

注意：此版本可以修改源容器，适用于实现移动语义。

iterator insert_equal(reference value);

iterator insert_equal(const_iterator hint, reference value);

template<typename Iterator> void insert_equal(Iterator b, Iterator e);

要求：解引用迭代器必须产生类型为 value_type 的左值。

效果：将范围 [first, last) 中的每个元素插入容器，在每个元素的键的 upper bound 之前。

复杂度：插入范围通常为 O(N * log(N))，其中 N 是范围的大小。然而，如果范围已按 value_comp() 排序，则为 O(N)。

抛出：如果比较函子调用抛出。

注意：不影响迭代器和引用的有效性。不调用拷贝构造函数。

std::pair< iterator, bool > insert_unique(reference value);

iterator insert_unique(const_iterator hint, reference value);

std::pair< iterator, bool > 
insert_unique_check(const key_type & key, insert_commit_data & commit_data);

std::pair< iterator, bool > 
insert_unique_check(const_iterator hint, const key_type & key, 
                    insert_commit_data & commit_data);

template<typename KeyType, typename KeyTypeKeyCompare> 
  std::pair< iterator, bool > 
  insert_unique_check(const KeyType & key, KeyTypeKeyCompare comp, 
                      insert_commit_data & commit_data);

template<typename KeyType, typename KeyTypeKeyCompare> 
  std::pair< iterator, bool > 
  insert_unique_check(const_iterator hint, const KeyType & key, 
                      KeyTypeKeyCompare comp, 
                      insert_commit_data & commit_data);

iterator insert_unique_commit(reference value, 
                              const insert_commit_data & commit_data) noexcept;

要求：value 必须是 value_type 类型的左值。commit_data 必须是之前调用“insert_check”获得的。在填充“commit_data”的“insert_check”和调用“insert_commit”之间，不应向容器插入或删除任何对象。

效果：使用 "commit_data"（由先前 "insert_check" 填充的信息）将 value 插入容器。

返回：指向新插入对象的迭代器。

复杂度：常量时间。

抛出：无。

注意：只有在先前执行了 "insert_check" 来填充 "commit_data" 时，此函数才有意义。在 "insert_check" 和 "insert_commit" 调用之间，不应插入或删除任何值。

template<typename Iterator> void insert_unique(Iterator b, Iterator e);

要求：解引用迭代器必须产生类型为 value_type 的左值。

效果：尝试将范围中的每个元素插入容器。

复杂度：插入范围通常为 O(N * log(N))，其中 N 是范围的大小。然而，如果范围已按 value_comp() 排序，则为 O(N)。

抛出：如果比较函子调用抛出。

注意：不影响迭代器和引用的有效性。不调用拷贝构造函数。

iterator insert_before(const_iterator pos, reference value) noexcept;

要求：value 必须是左值，"pos" 必须是一个有效迭代器（或 end），并且根据谓词，它将是插入 value 后的后继。

效果：在 "pos" 之前将 x 插入容器。

复杂度：常量时间。

抛出：无。

注意：此函数不检查前置条件，因此如果“pos”不是“value”的后继者，容器的排序不变性将被破坏。这是一个低级函数，仅供高级用户出于性能原因使用。

void push_back(reference value) noexcept;

要求：value 必须是左值，并且它不小于已插入的最大键。

效果：将 x 插入容器的最后一个位置。

复杂度：常量时间。

抛出：无。

注意：此函数不检查前置条件，因此如果 value 小于已插入的最大键，容器的排序不变性将被破坏。此函数比使用“insert_before”稍微高效一些。这是一个低级函数，仅供高级用户出于性能原因使用。

void push_front(reference value) noexcept;

要求：value 必须是左值，并且它不大于已插入的最小键。

效果：将 x 插入容器的第一个位置。

复杂度：常量时间。

抛出：无。

注意：此函数不检查前置条件，因此如果 value 大于已插入的最小键，容器的排序不变性将被破坏。此函数比使用“insert_before”稍微高效一些。这是一个低级函数，仅供高级用户出于性能原因使用。

iterator erase(const_iterator i) noexcept;

iterator erase(const_iterator b, const_iterator e) noexcept;

size_type erase(const key_type & key);

template<typename KeyType, typename KeyTypeKeyCompare> 
  size_type erase(const KeyType & key, KeyTypeKeyCompare comp);

要求：key 是一个值，使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 进行分区，其中 comp(nk, key) 暗示 !comp(key, nk)，其中 nk 是插入到 *this 的 value_type 的 key_type。

效果：根据比较函子 "comp" 擦除所有具有给定键的元素。

返回：被擦除的元素数量。

复杂度：O(log(size() + N)。

抛出：无。

注意：使被擦除元素的迭代器（但不影响引用）无效。不调用析构函数。

template<typename Disposer> 
  iterator erase_and_dispose(const_iterator i, Disposer disposer) noexcept;

template<typename Disposer> 
  iterator erase_and_dispose(const_iterator b, const_iterator e, 
                             Disposer disposer) noexcept;

template<typename Disposer> 
  size_type erase_and_dispose(const key_type & key, Disposer disposer);

template<typename KeyType, typename KeyTypeKeyCompare, typename Disposer> 
  size_type erase_and_dispose(const KeyType & key, KeyTypeKeyCompare comp, 
                              Disposer disposer);

要求：key 是一个值，使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 进行分区，其中 comp(nk, key) 暗示 !comp(key, nk)，并且 nk 是插入到 *this 的 value_type 的 key_type。

要求：Disposer::operator()(pointer) 不应抛出。

效果：根据比较函子 "comp" 擦除所有具有给定键的元素。Disposer::operator()(pointer) 将被调用以处理移除的元素。

返回：被擦除的元素数量。

复杂度：O(log(size() + N)。

抛出：无。

注意：使被擦除元素的迭代器无效。

void clear() noexcept;

效果：擦除所有元素。

复杂度：相对于容器中的元素数量为线性。如果 value_type 是安全模式或自动解除链接；否则为常量时间。

抛出：无。

注意：使被擦除元素的迭代器（但不影响引用）无效。不调用析构函数。

template<typename Disposer> void clear_and_dispose(Disposer disposer) noexcept;

效果：通过对每个要删除的节点调用 disposer(p) 来删除所有元素。 复杂度：平均复杂度最多为 O(log(size() + N))，其中 N 是容器中的元素数量。

抛出：无。

注意：使被擦除元素的迭代器（但不影响引用）无效。调用 disposer 函子 N 次。

size_type count(const key_type & key);

附加说明：非 const 函数，执行 splay 操作。

template<typename KeyType, typename KeyTypeKeyCompare> 
  size_type count(const KeyType & key, KeyTypeKeyCompare comp);

要求：key 是一个值，使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 进行分区，其中 comp(nk, key) 暗示 !comp(key, nk)，并且 nk 是插入到 *this 的 value_type 的 key_type。

效果：返回具有给定键的包含元素的数量。

复杂度：包含元素的数量的对数加上具有给定键的对象数量的线性。

抛出：如果 comp 抛出。附加说明：非 const 函数，执行 splaying。

size_type count(const key_type & key) const;

附加说明：const 函数，不执行 splay 操作

template<typename KeyType, typename KeyTypeKeyCompare> 
  size_type count(const KeyType & key, KeyTypeKeyCompare comp) const;

要求：key 是一个值，使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 进行分区，其中 comp(nk, key) 暗示 !comp(key, nk)，并且 nk 是插入到 *this 的 value_type 的 key_type。

效果：返回具有给定键的包含元素的数量。

复杂度：包含元素的数量的对数加上具有给定键的对象数量的线性。

抛出：如果 comp 抛出。附加说明：const 函数，不执行 splay 操作

iterator lower_bound(const key_type & key);

附加说明：非 const 函数，执行 splay 操作。

const_iterator lower_bound(const key_type & key) const;

附加说明：const 函数，不执行 splay 操作

template<typename KeyType, typename KeyTypeKeyCompare> 
  iterator lower_bound(const KeyType & key, KeyTypeKeyCompare comp);

附加说明：非 const 函数，对 "key" 的相等范围的第一个元素执行 splay 操作。

template<typename KeyType, typename KeyTypeKeyCompare> 
  const_iterator 
  lower_bound(const KeyType & key, KeyTypeKeyCompare comp) const;

附加说明：const 函数，不执行 splay 操作

iterator upper_bound(const key_type & key);

附加说明：非 const 函数，对 "value" 的相等范围的第一个元素执行 splay 操作。

const_iterator upper_bound(const key_type & key) const;

附加说明：const 函数，不执行 splay 操作

template<typename KeyType, typename KeyTypeKeyCompare> 
  iterator upper_bound(const KeyType & key, KeyTypeKeyCompare comp);

要求：key 是一个值，使得 *this 相对于 !comp(key, nk) 进行分区，其中 nk 是插入到 *this 的 value_type 的 key_type。

效果：根据 comp 返回一个指向第一个键大于 k 的元素的迭代器，如果该元素不存在，则返回 end()。

复杂度：对数。

抛出：如果 comp 抛出。附加说明：非 const 函数，对 "key" 的相等范围的第一个元素执行 splay 操作。

template<typename KeyType, typename KeyTypeKeyCompare> 
  const_iterator 
  upper_bound(const KeyType & key, KeyTypeKeyCompare comp) const;

要求：key 是一个值，使得 *this 相对于 !comp(key, nk) 进行分区，其中 nk 是插入到 *this 的 value_type 的 key_type。

效果：根据 comp 返回一个指向第一个键大于 k 的元素的迭代器，如果该元素不存在，则返回 end()。

复杂度：对数。

抛出：如果 comp 抛出。附加说明：const 函数，不执行 splay 操作

iterator find(const key_type & key);

附加说明：非 const 函数，对 "value" 的相等范围的第一个元素执行 splay 操作。

const_iterator find(const key_type & key) const;

附加说明：const 函数，不执行 splay 操作

template<typename KeyType, typename KeyTypeKeyCompare> 
  iterator find(const KeyType & key, KeyTypeKeyCompare comp);

要求：key 是一个值，使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 进行分区，其中 comp(nk, key) 暗示 !comp(key, nk)，并且 nk 是插入到 *this 的 value_type 的 key_type。

效果：查找一个指向第一个键为 k 的元素的迭代器，如果该元素不存在，则返回 end()。

复杂度：对数。

抛出：如果 comp 抛出。附加说明：非 const 函数，对 "key" 的相等范围的第一个元素执行 splay 操作。

template<typename KeyType, typename KeyTypeKeyCompare> 
  const_iterator find(const KeyType & key, KeyTypeKeyCompare comp) const;

要求：key 是一个值，使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 进行分区，其中 comp(nk, key) 暗示 !comp(key, nk)，并且 nk 是插入到 *this 的 value_type 的 key_type。

效果：查找一个指向第一个键为 k 的元素的迭代器，如果该元素不存在，则返回 end()。

复杂度：对数。

抛出：如果 comp 抛出。附加说明：const 函数，不执行 splay 操作

std::pair< iterator, iterator > equal_range(const key_type & key);

附加说明：非 const 函数，对 "value" 的相等范围的第一个元素执行 splay 操作。

std::pair< const_iterator, const_iterator > 
equal_range(const key_type & key) const;

附加说明：const 函数，不执行 splay 操作

template<typename KeyType, typename KeyTypeKeyCompare> 
  std::pair< iterator, iterator > 
  equal_range(const KeyType & key, KeyTypeKeyCompare comp);

要求：key 是一个值，使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 进行分区，其中 comp(nk, key) 暗示 !comp(key, nk)，其中 nk 是插入到 *this 的 value_type 的 key_type。

效果：查找包含所有键为 k 的元素的范围，或者一个空范围，该范围指示如果不存在键为 k 的元素，这些元素将插入的位置。

复杂度：对数。

抛出：如果 comp 抛出。附加说明：非 const 函数，对 "key" 的相等范围的第一个元素执行 splay 操作。

template<typename KeyType, typename KeyTypeKeyCompare> 
  std::pair< const_iterator, const_iterator > 
  equal_range(const KeyType & key, KeyTypeKeyCompare comp) const;

要求：key 是一个值，使得 *this 相对于 comp(nk, key) 和 !comp(key, nk) 进行分区，其中 comp(nk, key) 暗示 !comp(key, nk)，其中 nk 是插入到 *this 的 value_type 的 key_type。

效果：查找包含所有键为 k 的元素的范围，或者一个空范围，该范围指示如果不存在键为 k 的元素，这些元素将插入的位置。

复杂度：对数。

抛出：如果 comp 抛出。附加说明：const 函数，不执行 splay 操作

std::pair< iterator, iterator > 
bounded_range(const key_type & lower_key, const key_type & upper_key, 
              bool left_closed, bool right_closed);

template<typename KeyType, typename KeyTypeKeyCompare> 
  std::pair< iterator, iterator > 
  bounded_range(const KeyType & lower_key, const KeyType & upper_key, 
                KeyTypeKeyCompare comp, bool left_closed, bool right_closed);

要求：lower_key 是一个值，使得 *this 相对于 comp(nk, lower_key) 进行分区（如果 left_closed 为 true），否则相对于 !comp(lower_key, nk)。

upper_key 是一个值，使得 *this 相对于 !comp(upper_key, nk) 进行分区（如果 right_closed 为 true），否则相对于 comp(nk, upper_key)。

upper_key 不得根据 comp 排在 lower_key 之前 [comp(upper_key, lower_key) 应为 false]

如果 lower_key 等价于 upper_key [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)]，则 ('left_closed' || 'right_closed') 必须为 false。

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

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

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

复杂度：对数。

抛出：如果 comp 抛出。

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

注意：实验性功能，接口可能在未来版本中更改。

std::pair< const_iterator, const_iterator > 
bounded_range(const key_type & lower_key, const key_type & upper_key, 
              bool left_closed, bool right_closed) const;

template<typename KeyType, typename KeyTypeKeyCompare> 
  std::pair< const_iterator, const_iterator > 
  bounded_range(const KeyType & lower_key, const KeyType & upper_key, 
                KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;

要求：lower_key 是一个值，使得 *this 相对于 comp(nk, lower_key) 进行分区（如果 left_closed 为 true），否则相对于 !comp(lower_key, nk)。

upper_key 是一个值，使得 *this 相对于 !comp(upper_key, nk) 进行分区（如果 right_closed 为 true），否则相对于 comp(nk, upper_key)。

upper_key 不得根据 comp 排在 lower_key 之前 [comp(upper_key, lower_key) 应为 false]

如果 lower_key 等价于 upper_key [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)]，则 ('left_closed' || 'right_closed') 必须为 false。

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

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

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

复杂度：对数。

抛出：如果 comp 抛出。

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

注意：实验性功能，接口可能在未来版本中更改。

iterator iterator_to(reference value) noexcept;

const_iterator iterator_to(const_reference value) const noexcept;

pointer unlink_leftmost_without_rebalance() noexcept;

效果：从容器中解除链接最左边的节点。

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

抛出：无。

备注：此函数会破坏容器，并且容器只能用于更多的 unlink_leftmost_without_rebalance 调用。此函数通常用于实现分步控制的容器销毁。

void replace_node(iterator replace_this, reference with_this) noexcept;

要求：replace_this 必须是 *this 的有效迭代器，并且 with_this 不能插入到任何容器中。

效果：在容器中用 with_this 替换 replace_this 的位置。容器不需要重新平衡。

复杂度：常量。

抛出：无。

注意：如果 with_this 不等同于 *replace_this（根据排序规则），此函数将破坏容器排序不变性。此函数比删除和插入节点更快，因为它不需要重新平衡或比较。

void remove_node(reference value) noexcept;

效果：从容器中移除 "value"。

抛出：无。

复杂度：对数时间。

注意：此静态函数仅可与非常量时间大小的容器以及有状态的比较函子一起使用。

如果用户将此函数与常量时间大小容器或有状态比较函子一起调用，将产生编译错误。

template<typename T, class ... Options2> 
  void merge_unique(splaytree< T, Options2... > &);

template<typename T, class ... Options2> 
  void merge_equal(splaytree< T, Options2... > &);

void splay_up(iterator i) noexcept;

要求：i 必须是 *this 的有效迭代器。

效果：重新排列容器，使由 i 指向的元素成为树的根节点，从而改进对该值的未来搜索。

复杂度：摊销对数。

抛出：无。

template<typename KeyType, typename KeyTypeKeyCompare> 
  iterator splay_down(const KeyType & key, KeyTypeKeyCompare comp);

效果：重新排列容器，以便如果 *this 存储一个键与 value 等效的元素，则该元素将成为树的根。如果元素不存在，则返回与该键进行比较的最后一个节点。如果树为空，则返回 end()。

复杂度：摊销对数。

返回：指向新树根的迭代器，如果树为空，则为 end()。

抛出：如果比较函数抛出。

iterator splay_down(const key_type & key);

效果：重新排列容器，使得如果 *this 存储一个键等于 value 的元素，则该元素成为树的根节点。

复杂度：摊销对数。

返回：指向新树根的迭代器，如果树为空，则为 end()。

抛出：如果谓词抛出。

void rebalance() noexcept;

效果：重新平衡树。

抛出：无。

复杂度：线性。

iterator rebalance_subtree(iterator root) noexcept;

要求：old_root 是树的一个节点。

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

返回：子树的新根。

抛出：无。

复杂度：相对于子树中的元素为线性。

static splaytree & container_from_end_iterator(iterator end_iterator) noexcept;

static const splaytree & 
container_from_end_iterator(const_iterator end_iterator) noexcept;

static splaytree & container_from_iterator(iterator it) noexcept;

static const splaytree & container_from_iterator(const_iterator it) noexcept;

static iterator s_iterator_to(reference value) noexcept;

static const_iterator s_iterator_to(const_reference value) noexcept;

static void init_node(reference value) noexcept;