Class template bstree_algorithms . Boost , The Boost C++ Libraries BoostBook Documentation Subset , Reference

Class template bstree_algorithms

boost::intrusive::bstree_algorithms

Synopsis

// In header: <boost/intrusive/bstree_algorithms.hpp>
template<typename NodeTraits> 
class bstree_algorithms : public bstree_algorithms_base< NodeTraits > {
public:
  // types
  typedef NodeTraits::node                 node;              
  typedef NodeTraits                       node_traits;       
  typedef NodeTraits::node_ptr             node_ptr;          
  typedef NodeTraits::const_node_ptr       const_node_ptr;    
  typedef insert_commit_data_t< node_ptr > insert_commit_data;
  typedef data_for_rebalance_t< node_ptr > data_for_rebalance;
  // public static functions
  static node_ptr begin_node(const const_node_ptr &);
  static node_ptr end_node(const const_node_ptr &);
  static node_ptr root_node(const const_node_ptr &);
  static bool unique(const const_node_ptr &);
  static node_ptr get_header(const const_node_ptr &);
  static void swap_nodes(const node_ptr &, const node_ptr &);
  static void swap_nodes(const node_ptr &, const node_ptr &, const node_ptr &, 
                         const node_ptr &);
  static void replace_node(const node_ptr &, const node_ptr &);
  static void replace_node(const node_ptr &, const node_ptr &, 
                           const node_ptr &);
  static node_ptr next_node(const node_ptr &);
  static node_ptr prev_node(const node_ptr &);
  static node_ptr minimum(node_ptr);
  static node_ptr maximum(node_ptr);
  static void init(const node_ptr &);
  static bool inited(const const_node_ptr &);
  static void init_header(const node_ptr &);
  template<typename Disposer> 
    static void clear_and_dispose(const node_ptr &, Disposer);
  static node_ptr unlink_leftmost_without_rebalance(const node_ptr &);
  static std::size_t size(const const_node_ptr &);
  static void swap_tree(const node_ptr &, const node_ptr &);
  static bool is_header(const const_node_ptr &);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static node_ptr 
    find(const const_node_ptr &, const KeyType &, KeyNodePtrCompare);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static std::pair< node_ptr, node_ptr > 
    bounded_range(const const_node_ptr &, const KeyType &, const KeyType &, 
                  KeyNodePtrCompare, bool, bool);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static std::size_t 
    count(const const_node_ptr &, const KeyType &, KeyNodePtrCompare);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static std::pair< node_ptr, node_ptr > 
    equal_range(const const_node_ptr &, const KeyType &, KeyNodePtrCompare);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static std::pair< node_ptr, node_ptr > 
    lower_bound_range(const const_node_ptr &, const KeyType &, 
                      KeyNodePtrCompare);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static node_ptr 
    lower_bound(const const_node_ptr &, const KeyType &, KeyNodePtrCompare);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static node_ptr 
    upper_bound(const const_node_ptr &, const KeyType &, KeyNodePtrCompare);
  static void insert_unique_commit(const node_ptr &, const node_ptr &, 
                                   const insert_commit_data &);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static std::pair< node_ptr, bool > 
    insert_unique_check(const const_node_ptr &, const KeyType &, 
                        KeyNodePtrCompare, insert_commit_data &);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static std::pair< node_ptr, bool > 
    insert_unique_check(const const_node_ptr &, const node_ptr &, 
                        const KeyType &, KeyNodePtrCompare, 
                        insert_commit_data &);
  template<typename NodePtrCompare> 
    static node_ptr 
    insert_equal(const node_ptr &, const node_ptr &, const node_ptr &, 
                 NodePtrCompare);
  template<typename NodePtrCompare> 
    static node_ptr 
    insert_equal_upper_bound(const node_ptr &, const node_ptr &, 
                             NodePtrCompare);
  template<typename NodePtrCompare> 
    static node_ptr 
    insert_equal_lower_bound(const node_ptr &, const node_ptr &, 
                             NodePtrCompare);
  static node_ptr 
  insert_before(const node_ptr &, const node_ptr &, const node_ptr &);
  static void push_back(const node_ptr &, const node_ptr &);
  static void push_front(const node_ptr &, const node_ptr &);
  static std::size_t depth(const_node_ptr);
  template<typename Cloner, typename Disposer> 
    static void clone(const const_node_ptr &, const node_ptr &, Cloner, 
                      Disposer);
  static void erase(const node_ptr &, const node_ptr &);
  template<typename NodePtrCompare> 
    static bool transfer_unique(const node_ptr &, NodePtrCompare, 
                                const node_ptr &, const node_ptr &);
  template<typename NodePtrCompare> 
    static void transfer_equal(const node_ptr &, NodePtrCompare, 
                               const node_ptr &, const node_ptr &);
  static void unlink(const node_ptr &);
  static void rebalance(const node_ptr &);
  static node_ptr rebalance_subtree(const node_ptr &);
  template<typename Checker> 
    static void check(const const_node_ptr &, Checker, 
                      typename Checker::return_type &);
  // protected static functions
  template<typename NodePtrCompare> 
    static bool transfer_unique(const node_ptr &, NodePtrCompare, 
                                const node_ptr &, const node_ptr &, 
                                data_for_rebalance &);
  template<typename NodePtrCompare> 
    static void transfer_equal(const node_ptr &, NodePtrCompare, 
                               const node_ptr &, const node_ptr &, 
                               data_for_rebalance &);
  static void erase(const node_ptr &, const node_ptr &, data_for_rebalance &);
  static std::size_t subtree_size(const const_node_ptr &);
  static bool is_left_child(const node_ptr &);
  static bool is_right_child(const node_ptr &);
  static void insert_before_check(const node_ptr &, const node_ptr &, 
                                  insert_commit_data &);
  static void push_back_check(const node_ptr &, insert_commit_data &);
  static void push_front_check(const node_ptr &, insert_commit_data &);
  template<typename NodePtrCompare> 
    static void insert_equal_check(const node_ptr &, const node_ptr &, 
                                   const node_ptr &, NodePtrCompare, 
                                   insert_commit_data &);
  template<typename NodePtrCompare> 
    static void insert_equal_upper_bound_check(const node_ptr &, 
                                               const node_ptr &, 
                                               NodePtrCompare, 
                                               insert_commit_data &, 
                                               std::size_t * = 0);
  template<typename NodePtrCompare> 
    static void insert_equal_lower_bound_check(const node_ptr &, 
                                               const node_ptr &, 
                                               NodePtrCompare, 
                                               insert_commit_data &, 
                                               std::size_t * = 0);
  static void insert_commit(const node_ptr &, const node_ptr &, 
                            const insert_commit_data &);
  static void set_child(const node_ptr &, const node_ptr &, const node_ptr &, 
                        const bool);
  static void rotate_left_no_parent_fix(const node_ptr &, const node_ptr &);
  static void rotate_left(const node_ptr &, const node_ptr &, 
                          const node_ptr &, const node_ptr &);
  static void rotate_right_no_parent_fix(const node_ptr &, const node_ptr &);
  static void rotate_right(const node_ptr &, const node_ptr &, 
                           const node_ptr &, const node_ptr &);
  // private static functions
  static void subtree_to_vine(node_ptr, std::size_t &);
  static void compress_subtree(node_ptr, std::size_t);
  static void vine_to_subtree(const node_ptr &, std::size_t);
  static node_ptr get_root(const node_ptr &);
  template<typename Cloner, typename Disposer> 
    static node_ptr 
    clone_subtree(const const_node_ptr &, const node_ptr &, Cloner, Disposer, 
                  node_ptr &, node_ptr &);
  template<typename Disposer> static void dispose_subtree(node_ptr, Disposer);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static node_ptr 
    lower_bound_loop(node_ptr, node_ptr, const KeyType &, KeyNodePtrCompare);
  template<typename KeyType, typename KeyNodePtrCompare> 
    static node_ptr 
    upper_bound_loop(node_ptr, node_ptr, const KeyType &, KeyNodePtrCompare);
  template<typename Checker> 
    static void check_subtree(const const_node_ptr &, Checker, 
                              typename Checker::return_type &);
};

Description

Это реализация двоичного дерева поиска. Узел в дереве поиска имеет ссылки на своих детей и родителей. Это позволяет пройти все дерево от заданного узла, делая реализацию итератора указателем на узел. В верхней части дерева узел используется специально. Родительский указатель этого узла указывает на корень дерева. Его левый указатель указывает на самый левый узел в дереве и правый указатель на самый правый. Этот узел используется для представления конечного пользователя. +--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Корень дерева................>| | | | |+------+---+ |


#160;	#160;	#160;
#160;	#160;	#160;
#160;	#160;	#160;

+-----+ +-----+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +–+------+–+ +–+-----+–+ |


#160;	#160;	#160;	#160;	#160;

| ++ + -+ + ++ -++ | | | | | | | | | | | | | | | | | | | | | | | | | | | |+ +----+----/mdash>

bstree_algorithmsсконфигурирован с классом NodeTraits, который инкапсулирует информацию о узле, которым нужно манипулировать. NodeTraits должен поддерживать следующий интерфейс:

Типдефы:

<node>: Тип узла, который формирует двоичное дерево поиска

<node_ptr>: Указатель на узел

<const_node_ptr>: Указатель на узел const

Статические функции:

<static node_ptr get_parent(const_node_ptr n);>

<static void set_parent(node_ptr n, node_ptr parent);>

<static node_ptr get_left(const_node_ptr n);>

<static void set_left(node_ptr n, node_ptr left);>

<static node_ptr get_right(const_node_ptr n);>

<static void set_right(node_ptr n, node_ptr right);>

`bstree_algorithms` public static functions

<
```
staticnode_ptrbegin_node(constconst_node_ptr&header);
```
>
Требуется: «заголовок» — это заголовок узла дерева.
Эффекты: Возвращает первый узел дерева, заголовок, если дерево пустое.
Сложность:
Бросает: Ничего.
<
```
staticnode_ptrend_node(constconst_node_ptr&header);
```
>
Требует: «заголовок» — это заголовок узла дерева.
Эффекты: Возвращает заголовок дерева.
Сложность: Постоянное время.
Бросает: Ничего.
<
```
staticnode_ptrroot_node(constconst_node_ptr&header);
```
>
Требуется: «заголовок» — это заголовок узла дерева.
Эффекты: Возвращает корень дерева, если таковой имеется, заголовок иначе
Сложность:
Бросает: Ничего.
<
```
staticboolunique(constconst_node_ptr&node);
```
>
Требуется: «узел» — это узел дерева или узел, инициализированный init(...)
Эффекты: Возвращается истинно, если узел инициализируется init() или init_node().
Сложность:
Бросает: Ничего.
<
```
staticnode_ptrget_header(constconst_node_ptr&node);
```
>
Требуется: «узел» — это узел дерева или узел заголовка.
Эффекты: Возвращает заголовок дерева.
Сложность: Логарифмическая.
Бросает: Ничего.
<
```
staticvoidswap_nodes(constnode_ptr&node1,constnode_ptr&node2);
```
>
Требуется: узел 1 и узел 2 не могут быть узлами заголовка двух деревьев.
Эффекты: Два узла. После этого функциональный узел 1 будет вставлен в положение узел 2 перед функцией. Узел 2 будет вставлен в положение, которое узел 1 имел перед функцией.
Сложность: Логарифмическая.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты упорядочения контейнеров, если узел 1 и узел 2 не эквивалентны в соответствии с правилами упорядочения.
Экспериментальная функция
<
```
staticvoidswap_nodes(constnode_ptr&node1,constnode_ptr&header1,
                      constnode_ptr&node2,constnode_ptr&header2);
```
>
Требуется: Узел 1 и узел 2 не могут быть узлами заголовка двух деревьев с заголовком 1 и заголовком 2.
Эффекты: Два узла. После этого функциональный узел 1 будет вставлен в положение узел 2 перед функцией. Узел 2 будет вставлен в положение, которое узел 1 имел перед функцией.
Сложность: Постоянная.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты упорядочения контейнеров, если узел 1 и узел 2 не эквивалентны в соответствии с правилами упорядочения.
Экспериментальная функция
<
```
staticvoidreplace_node(constnode_ptr&node_to_be_replaced,
                        constnode_ptr&new_node);
```
>
Требуется: узел_to_be_ должен быть вставлен в дерево, а новый_узел не должен быть вставлен в дерево.
Эффекты: Заменить узел_to_be_заменить в его положении на дереве новым_узлом. Дерево не нуждается в перебалансировке
Сложность: Логарифмическая.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты упорядочивания контейнеров, если новый узел не эквивалентен замещённому в соответствии с правилами упорядочивания узлу_to_be_. Эта функция быстрее, чем стирание и вставка узла, так как не требуется перебалансировки и сравнения. Экспериментальная функция
<
```
staticvoidreplace_node(constnode_ptr&node_to_be_replaced,
                        constnode_ptr&header,constnode_ptr&new_node);
```
>
Требуется: узел_to_be_replaced должен быть вставлен в дерево с заголовком "header" и новый_node не должен быть вставлен в дерево.
Эффекты: Заменить узел_to_be_заменить в его положении на дереве новым_узлом. Дерево не нуждается в перебалансировке
Сложность: Постоянная.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты упорядочивания контейнеров, если новый узел не эквивалентен замещённому в соответствии с правилами упорядочивания узлу_to_be_. Эта функция быстрее, чем стирание и вставка узла, поскольку не требуется перебалансировки или сравнения. Экспериментальная функция
<
```
staticnode_ptrnext_node(constnode_ptr&node);
```
>
Требуется: «узел» — это узел от дерева, за исключением заголовка.
Эффекты: Возвращает следующий узел дерева.
Сложность: Среднее постоянное время.
Бросок: Ничего.
<
```
staticnode_ptrprev_node(constnode_ptr&node);
```
>
Требуется: «узел» — это узел от дерева, за исключением самого левого узла.
Эффекты: Возвращает предыдущий узел дерева.
Сложность: Среднее постоянное время.
Бросает: Ничего.
<
```
staticnode_ptrminimum(node_ptrnode);
```
>
Требуется: «узел» — это узел дерева, но не заголовок.
Эффекты: Возвращает минимальный узел поддеревья, начиная с p.
Сложность: Логарифмический к размеру поддеревья.
Бросок: Ничего.
<
```
staticnode_ptrmaximum(node_ptrnode);
```
>
Требует: «узел» — это узел дерева, но не заголовок.
Эффекты: Возвращает максимальный узел поддеревья, начиная с p.
Сложность: Логарифмический размер поддеревья.
Бросает: Ничего.
<
```
staticvoidinit(constnode_ptr&node);
```
>
Требуется: «узел» не должен быть частью какого-либо дерева.
Эффекты: После функции уникальный (узел) == истинно.
Сложность: Постоянная.
Бросает: Ничего.
Узлы: Если узел вставлен в дерево, эта функция развращает дерево.
<
```
staticboolinited(constconst_node_ptr&node);
```
>
Эффекты: Возвращается истинно, если узел находится в том же состоянии, как если бы его называли init(node)
Сложность: Постоянная.
Бросает: Ничего.
<
```
staticvoidinit_header(constnode_ptr&header);
```
>
Требуется: Узел не должен быть частью какого-либо дерева.
Эффекты: Инициирует заголовок, чтобы представить пустое дерево. Уникальный (заголовок) == истинно.
Сложность: Постоянная.
Броски: Ничего.
Узлы: Если узел вставлен в дерево, эта функция развращает дерево.
<
```
template<typenameDisposer>
 staticvoidclear_and_dispose(constnode_ptr&header,Disposerdisposer);
```
>
Требуется: Диспозитор должен быть функцией объекта, принимающей параметр node_ptr, и не должен бросать.
Эффекты: Позволяет дереву-мишени вызывать<void disposer::operator()(const node_ptr &)>каждый узел дерева, кроме заголовка.
Сложность: Линейный к числу элемента дерева-источника плюс. количество элементов дерева-мишени при вызове этой функции.
Бросок: Если клонер-функтор бросит. Если это происходит, узлы-мишени удаляются.
<
```
staticnode_ptrunlink_leftmost_without_rebalance(constnode_ptr&header);
```
>
Требуется: Заголовок — это заголовок дерева.
Эффекты: Отключает самый левый узел от дерева и обновляет ссылку заголовка на новый самый левый узел.
Сложность: Средняя сложность — это постоянное время.
Бросает: Ничего.
Примечания: Эта функция ломает дерево, и дерево может использоваться только для дополнительных вызовов unlink_leftmost_without_rebalance. Эта функция обычно используется для достижения постепенного контролируемого разрушения дерева.
<
```
staticstd::size_tsize(constconst_node_ptr&header);
```
>
Требуется: Узел — это узел дерева, но это не заголовок.
Эффекты: Возвращает число узлов поддеревья.
Сложность: Линейное время.
Бросает: Ничего.
<
```
staticvoidswap_tree(constnode_ptr&header1,constnode_ptr&header2);
```
>
Требуется: узлы заголовка1 и заголовка2 должны быть узлами заголовка двух деревьев.
Эффекты: Смахивает двумя деревьями. После этого заголовок 1 функции будет содержать ссылки на второе дерево, а заголовок 2 будет иметь ссылки на первое дерево.
Сложность: Постоянная.
Броски: Ничего.
<
```
staticboolis_header(constconst_node_ptr&p);
```
>
Требуется: p — узел дерева.
Эффекты: Возвращается истинно, если p - заголовок дерева.
Сложность: Постоянная.
Бросает: Ничего.
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticnode_ptr
 find(constconst_node_ptr&header,constKeyType&key,
      KeyNodePtrComparecomp);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который эквивалентен «ключу» согласно «комп» или «заголовку», если этот элемент не существует.
Сложность: Логарифмическая.
Броски: Если "комп" бросит.
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticstd::pair<node_ptr,node_ptr>
 bounded_range(constconst_node_ptr&header,constKeyType&lower_key,
               constKeyType&upper_key,KeyNodePtrComparecomp,
               boolleft_closed,boolright_closed);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare может сравнить KeyType с node_ptrs дерева. Нижний ключ не должен быть больше верхнего ключа в соответствии с компом. Если "нижний_ключ" == "верхний_ключ", ('left_closed' | | 'right_closed') должно быть истинным.
: Возвращает пару со следующими критериями:
первый = нижний_связанный (нижний_ключ), если левый_закрытый, верхний_связанный (нижний_ключ) в противном случае
второй = верхний_связанный (верхний_ключ), если правый_закрытый, нижний_связанный (верхний_ключ) в противном случае
Сложность: Логарифмический.
Бросает: Если "комп" бросает.
Примечание: Эта функция может быть более эффективной, чем вызов верхнего_bound и нижнего_bound для нижнего_key и верхнего_key.
Примечание: Экспериментальная функция, интерфейс может измениться.
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticstd::size_t
 count(constconst_node_ptr&header,constKeyType&key,
       KeyNodePtrComparecomp);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает число элементов с ключом, эквивалентным «ключу» по «комп».
Сложность: Логарифмическая.
Бросает: Если "комп" бросит.
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticstd::pair<node_ptr,node_ptr>
 equal_range(constconst_node_ptr&header,constKeyType&key,
             KeyNodePtrComparecomp);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает пару node_ptr, делимитирующую диапазон, содержащий все элементы, которые эквивалентны "ключу" в соответствии с "комп" или пустой диапазон, который указывает положение, в котором эти элементы были бы, если нет эквивалентных элементов.
Сложность: Логарифмический.
Бросок: Если "комп" бросит.
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticstd::pair<node_ptr,node_ptr>
 lower_bound_range(constconst_node_ptr&header,constKeyType&key,
                   KeyNodePtrComparecomp);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает пару node_ptr, делимитирующую диапазон, содержащий первый элемент, который эквивалентен "ключу" в соответствии с "комп" или пустой диапазон, который указывает положение, в котором этот элемент будет, если нет эквивалентных элементов.
Сложность: Логарифмический.
Бросок: Если "комп" бросит.
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticnode_ptr
 lower_bound(constconst_node_ptr&header,constKeyType&key,
             KeyNodePtrComparecomp);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который не меньше «ключа» согласно «комп» или «заголовку», если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если "комп" бросит.
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticnode_ptr
 upper_bound(constconst_node_ptr&header,constKeyType&key,
             KeyNodePtrComparecomp);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который больше «ключа» по «комп» или «заголовку», если этот элемент не существует.
Сложность: Логарифмический.
Бросает: Если "комп" бросит.
<
```
staticvoidinsert_unique_commit(constnode_ptr&header,
                                constnode_ptr&new_value,
                                constinsert_commit_data&commit_data);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. "commit_data" должно быть получено из предыдущего вызова "insert_unique_check". Никакие объекты не должны были быть вставлены или удалены из набора между «insert_unique_check», который заполнил «commit_data» и призывом «insert_commit»
: Вставляет новый_узел в набор, используя информацию, полученную из "commit_data", которую заполнил предыдущий "insert_check".
Сложность:
Бросок: Ничего.
Примечания: Эта функция имеет смысл только в том случае, если ранее была выполнена «insert_unique_check» для заполнения «commit_data». Не следует вставлять или стирать значение между вызовами «insert_check» и «insert_commit».
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticstd::pair<node_ptr,bool>
 insert_unique_check(constconst_node_ptr&header,constKeyType&key,
                     KeyNodePtrComparecomp,
                     insert_commit_data&commit_data);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. Узел PtrCompare сравнивает KeyType with node_ptr.
Эффекты: Проверяет, есть ли эквивалентный узел для «ключа» в дереве в соответствии с «комп» и получает необходимую информацию для реализации вставки узла постоянного времени, если нет эквивалентного узла.
Возвращение: При наличии эквивалентного значения возвращает пару, содержащую узел_ptr, к уже существующему узлу и ложному. Если нет эквивалентного ключа, он может быть вставлен в булевой ключ возвращаемой пары и заполняет «commit_data», который предназначен для использования с функцией «insert_commit» для достижения функции вставки в постоянное время.
Сложность: Средняя сложность в лучшем случае логарифмическая.
Броски: Если "комп" бросит.
Примечания: Эта функция используется для повышения производительности при строительстве узла дорого и пользователь не хочет иметь два эквивалентных узла в дереве: если есть эквивалентное значение, построенный объект должен быть отброшен. Часто часть узла, которая используется для наложения заказа, намного дешевле в конструировании, чем узел, и эта функция предлагает возможность использовать эту часть для проверки того, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить узел и использовать «insert_commit» для вставки узла в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
«commit_data» остается действительным для последующего «insert_unique_commit» только в том случае, если из набора больше не вставлены и не стерты объекты.
<
```
template<typenameKeyType,typenameKeyNodePtrCompare>
 staticstd::pair<node_ptr,bool>
 insert_unique_check(constconst_node_ptr&header,constnode_ptr&hint,
                     constKeyType&key,KeyNodePtrComparecomp,
                     insert_commit_data&commit_data);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает KeyType with a node_ptr. "hint" is node from the "header"'s tree.
Эффекты: Проверяет, есть ли эквивалентный узел для «ключа» в дереве в соответствии с «компом», используя «наконечник» в качестве подсказки, где он должен быть вставлен, и получает необходимую информацию для реализации вставки узла постоянного времени, если нет эквивалентного узла. Если «подсказка» является верхней_связанной, функция имеет постоянную временную сложность (два сравнения в худшем случае).
Возврат: При наличии эквивалентного значения возвращает пару, содержащую узел_ptr, к уже существующему узлу и ложному. Если нет эквивалентного ключа, можно вставить возвраты, верные в булевой паре, и заполнить «commit_data», который предназначен для использования с функцией «insert_commit» для достижения функции вставки в постоянное время.
: Средняя сложность в лучшем случае логарифмическая, но это амортизированное постоянное время, если новый_узел должен быть вставлен непосредственно перед «подсказкой»
Бросок:
Примечания: Эта функция используется для повышения производительности при строительстве узла дорого и пользователь не хочет иметь два эквивалентных узла в дереве: если есть эквивалентное значение, построенный объект должен быть отброшен. Часто часть узла, которая используется для наложения заказа, намного дешевле в конструировании, чем узел, и эта функция предлагает возможность использовать эту часть для проверки того, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить узел и использовать «insert_commit» для вставки узла в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
«commit_data» остается действительным для последующего «insert_unique_commit» только в том случае, если из набора больше не вставлены или не стерты объекты.
<
```
template<typenameNodePtrCompare>
 staticnode_ptr
 insert_equal(constnode_ptr&h,constnode_ptr&hint,
              constnode_ptr&new_node,NodePtrComparecomp);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs. «Хинт» — это узел из дерева «головы».
Эффекты: Вставляет новый_узел в дерево, используя «наконечник» в качестве подсказки, где он будет вставлен. Если «подсказка» находится на верхнем уровне, вставка занимает постоянное время (два сравнения в худшем случае).
Сложность: Логарифмический в целом, но это амортизированное постоянное время, если новый_узел вставлен непосредственно перед «задним ходом»
Бросает: Если "комп" бросит.
<
```
template<typenameNodePtrCompare>
 staticnode_ptr
 insert_equal_upper_bound(constnode_ptr&h,constnode_ptr&new_node,
                          NodePtrComparecomp);
```
>
Требуется: «h» должно быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs.
Эффекты: Вставляет новый узел в дерево перед верхней границей согласно "комп".
Сложность: Средняя сложность для вставочного элемента является самой логарифмической.
Броски: Если "комп" бросит.
<
```
template<typenameNodePtrCompare>
 staticnode_ptr
 insert_equal_lower_bound(constnode_ptr&h,constnode_ptr&new_node,
                          NodePtrComparecomp);
```
>
Требуется: "h" должно быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs.
Эффекты: Вставляет новый узел в дерево перед нижней границей в соответствии с "комп".
Сложность: Средняя сложность для вставочного элемента является наиболее логарифмической.
Броски: Если "комп" бросит.
<
```
staticnode_ptr
insert_before(constnode_ptr&header,constnode_ptr&pos,
             constnode_ptr&new_node);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. "pos" должен быть действительным итератором или узлом заголовка (конца). "pos" должен быть итератором, указывающим на преемника "new_node" после вставки в соответствии с порядком уже вставленных узлов. Эта функция не проверяет «по» и это предварительное условие должно быть гарантировано абонентом.
Эффекты: Вставляет новый узел в дерево до "по".
Сложность: Постоянное время.
Бросает: Ничего.
Примечание: Если «pos» не является преемником вновь вставленных инвариантов дерева «new_node», они могут быть сломаны.
<
```
staticvoidpush_back(constnode_ptr&header,constnode_ptr&new_node);
```
>
Требуется: «заголовок» должен быть узлом заголовка дерева. "new_node" должен быть, согласно используемому порядку, не меньше, чем наибольший вставленный ключ.
Эффекты: Вставляет новый узел в дерево до "по".
Сложность: Постоянное время.
Бросает: Ничего.
Примечание: Если "new_node" меньше, чем наибольшие инварианты вставленного ключевого дерева, то они разбиваются. Эта функция немного быстрее, чем использование «insert_before».
<
```
staticvoidpush_front(constnode_ptr&header,constnode_ptr&new_node);
```
>
Требуется: "заголовок" должен быть узлом заголовка дерева. "new_node" должен быть, согласно используемому порядку, не больше, чем самый низкий вставленный ключ.
: Вставляет новый узел в дерево до "по".
Сложность: Постоянное время.
Бросает: Ничего.
Примечание: Если "new_node" больше, чем инварианты наименьшего вставленного ключевого дерева, то они разбиваются. Эта функция немного быстрее, чем использование «insert_before».
<
```
staticstd::size_tdepth(const_node_ptrnode);
```
>
Требуется: «узел» не может быть узлом заголовка.
Эффекты: Вычисляет глубину узла: глубина узла — это длина (число краев) пути от корня до этого узла. (Корневой узел находится на глубине 0.)
Сложность: Логарифмическое число узлов в дереве
Бросает: Ничего.
<
```
template<typenameCloner,typenameDisposer>
 staticvoidclone(constconst_node_ptr&source_header,
                   constnode_ptr&target_header,Clonercloner,
                   Disposerdisposer);
```
>
Требуется: «клонером» должен быть функциональный объект, принимающий узел_ptr и возвращающий ему новый клонированный узел. Диспозитор должен взять узел_ptr и не должен бросать.
Эффекты: Первое опустошает дерево-мишень<void disposer::operator()(const node_ptr &)>для каждого узла дерева, кроме заголовка. 1161
Затем дублирует все дерево, на которое указывает «source_header», клонируя каждый узел источника<node_ptr Cloner::operator()(const node_ptr &)>, чтобы получить узлы целевого дерева. Если «клонер» бросает, клонированные узлы-мишени утилизируются с помощью<void disposer(const node_ptr &)>.
Сложность: Линейный к числу элемента дерева-источника плюс число элементов дерева-мишени при вызове этой функции.
Бросок: Если клонер-функтор бросит. Если это происходит, узлы-мишени удаляются.
<
```
staticvoiderase(constnode_ptr&header,constnode_ptr&z);
```
>
Требуется: Заголовок должен быть заголовком дерева, z узла этого дерева и z ! = заголовок.
Эффекты: Стирает узел «z» с дерева заголовком «header».
Сложность: Амортизированное постоянное время.
Бросок: Ничего.
<
```
template<typenameNodePtrCompare>
 staticbooltransfer_unique(constnode_ptr&header1,NodePtrComparecomp,
                             constnode_ptr&header2,constnode_ptr&z);
```
>
Требуется: заголовок 1 и заголовок 2 должны быть заголовками деревьев tree1 и tree2 соответственно, z незаголовочного узла tree1. NodePtrCompare - функция сравнения дерева1..
Эффекты: Переносит узел «z» с дерева1 на дерево2, если дерево1 не содержит узел, эквивалентный z.
Возврат: Правда, если узел был переадресован, ложно иначе.
Сложность: Логарифмический.
Броски: Если сравнение падает.
<
```
template<typenameNodePtrCompare>
 staticvoidtransfer_equal(constnode_ptr&header1,NodePtrComparecomp,
                            constnode_ptr&header2,constnode_ptr&z);
```
>
Требуется: заголовок 1 и заголовок 2 должны быть заголовками деревьев tree1 и tree2 соответственно, z незаголовочного узла tree1. NodePtrCompare - функция сравнения дерева1..
Эффекты: Перенос узла «z» с дерева1 на дерево2.
Сложность: Логарифмический.
Бросок: Если сравнение падает.
<
```
staticvoidunlink(constnode_ptr&node);
```
>
Требуется: Узел — это узел дерева, но не заголовок.
Эффекты: Развязывает узел и перебалансирует дерево.
Сложность: Средняя сложность — это постоянное время.
Броски: Ничего.
<
```
staticvoidrebalance(constnode_ptr&header);
```
>
Требуется: Заголовок должен быть заголовком дерева.
Эффекты:
Бросает: Ничего.
Сложность: Линейный.
<
```
staticnode_ptrrebalance_subtree(constnode_ptr&old_root);
```
>
Требуется: Old_root — это узел дерева. Она не будет нулевой.
Эффекты: Уравновешивает поддеревья, укорененные в старом корне.
Возвращение: Новый корень дерева.
Бросает: Ничего.
Сложность: Линейный.
<
```
template<typenameChecker>
 staticvoidcheck(constconst_node_ptr&header,Checkerchecker,
                   typenameChecker::return_type&checker_return);
```
>
Эффекты: Утверждает целостность контейнера с дополнительными проверками, предоставляемыми пользователем.
Требует: Заголовок должен быть заголовком дерева.
Сложность: Линейное время.
Примечание: Метод может не иметь эффекта при отключении утверждений (например, с NDEBUG). Экспериментальная функция интерфейса может измениться в будущих версиях.

`bstree_algorithms` protected static functions

template<typenameNodePtrCompare>
 staticbooltransfer_unique(constnode_ptr&header1,NodePtrComparecomp,
                             constnode_ptr&header2,constnode_ptr&z,
                             data_for_rebalance&info);

template<typenameNodePtrCompare>
 staticvoidtransfer_equal(constnode_ptr&header1,NodePtrComparecomp,
                            constnode_ptr&header2,constnode_ptr&z,
                            data_for_rebalance&info);

staticvoiderase(constnode_ptr&header,constnode_ptr&z,
                 data_for_rebalance&info);

<
```
staticstd::size_tsubtree_size(constconst_node_ptr&subtree);
```
>
Требует: Узел — это узел дерева, но это не заголовок.
Эффекты: Возвращает количество узлов поддеревья.
Сложность: Линейное время.
Бросок: Ничего.
<
```
staticboolis_left_child(constnode_ptr&p);
```
>
Требуется: p - узел дерева.
Эффекты: Возвращается верно, если p — левый ребенок.
Сложность: Постоянная.
Броски: Ничего.
<
```
staticboolis_right_child(constnode_ptr&p);
```
>
Требует: p — узел дерева.
Эффекты: Возвращается истинным, если р - правильный ребенок.
Сложность: Постоянная.
Броски: Ничего.

staticvoidinsert_before_check(constnode_ptr&header,constnode_ptr&pos,
                               insert_commit_data&commit_data);

staticvoidpush_back_check(constnode_ptr&header,
                           insert_commit_data&commit_data);

staticvoidpush_front_check(constnode_ptr&header,
                            insert_commit_data&commit_data);

template<typenameNodePtrCompare>
 staticvoidinsert_equal_check(constnode_ptr&header,
                                constnode_ptr&hint,
                                constnode_ptr&new_node,
                                NodePtrComparecomp,
                                insert_commit_data&commit_data);

template<typenameNodePtrCompare>
 staticvoidinsert_equal_upper_bound_check(constnode_ptr&h,
                                            constnode_ptr&new_node,
                                            NodePtrComparecomp,
                                            insert_commit_data&commit_data,
                                            std::size_t*pdepth=0);

template<typenameNodePtrCompare>
 staticvoidinsert_equal_lower_bound_check(constnode_ptr&h,
                                            constnode_ptr&new_node,
                                            NodePtrComparecomp,
                                            insert_commit_data&commit_data,
                                            std::size_t*pdepth=0);

staticvoidinsert_commit(constnode_ptr&header,constnode_ptr&new_node,
                         constinsert_commit_data&commit_data);

staticvoidset_child(constnode_ptr&header,constnode_ptr&new_child,
                     constnode_ptr&new_parent,constboollink_left);

staticvoidrotate_left_no_parent_fix(constnode_ptr&p,
                                     constnode_ptr&p_right);

staticvoidrotate_left(constnode_ptr&p,constnode_ptr&p_right,
                       constnode_ptr&p_parent,constnode_ptr&header);

staticvoidrotate_right_no_parent_fix(constnode_ptr&p,
                                      constnode_ptr&p_left);

staticvoidrotate_right(constnode_ptr&p,constnode_ptr&p_left,
                        constnode_ptr&p_parent,constnode_ptr&header);

`bstree_algorithms` private static functions

staticvoidsubtree_to_vine(node_ptrvine_tail,std::size_t&size);

staticvoidcompress_subtree(node_ptrscanner,std::size_tcount);

staticvoidvine_to_subtree(constnode_ptr&super_root,std::size_tcount);

<
```
staticnode_ptrget_root(constnode_ptr&node);
```
>
Требуется: "n" должно быть узлом, вставленным в дерево.
Эффекты: Возвращает указатель на заголовочный узел дерева.
Сложность: Логарифмический.
Броски: Ничего.

template<typenameCloner,typenameDisposer>
 staticnode_ptr
 clone_subtree(constconst_node_ptr&source_parent,
               constnode_ptr&target_parent,Clonercloner,
               Disposerdisposer,node_ptr&leftmost_out,
               node_ptr&rightmost_out);

template<typenameDisposer>
 staticvoiddispose_subtree(node_ptrx,Disposerdisposer);

template<typenameKeyType,typenameKeyNodePtrCompare>
 staticnode_ptr
 lower_bound_loop(node_ptrx,node_ptry,constKeyType&key,
                  KeyNodePtrComparecomp);

template<typenameKeyType,typenameKeyNodePtrCompare>
 staticnode_ptr
 upper_bound_loop(node_ptrx,node_ptry,constKeyType&key,
                  KeyNodePtrComparecomp);

template<typenameChecker>
 staticvoidcheck_subtree(constconst_node_ptr&node,Checkerchecker,
                           typenameChecker::return_type&check_return);

Статья Class template bstree_algorithms раздела The Boost C++ Libraries BoostBook Documentation Subset Reference может быть полезна для разработчиков на c++ и boost.

Class template bstree_algorithms

Boost , The Boost C++ Libraries BoostBook Documentation Subset , Reference

Boost C++ Libraries

Class template bstree_algorithms

Synopsis

Description

bstree_algorithms public static functions

bstree_algorithms protected static functions

bstree_algorithms private static functions

`bstree_algorithms` public static functions

`bstree_algorithms` protected static functions

`bstree_algorithms` private static functions