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

Class template bstree

boost::intrusive::bstree

Synopsis

// In header: <boost/intrusive/bstree.hpp>
template<typename T, class... Options> 
class bstree : public bstbase< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder >
{
public:
  // types
  typedef implementation_defined              value_traits;          
  typedef implementation_defined              pointer;               
  typedef implementation_defined              const_pointer;         
  typedef implementation_defined              value_type;            
  typedef implementation_defined              key_type;              
  typedef implementation_defined              key_of_value;          
  typedef implementation_defined              reference;             
  typedef implementation_defined              const_reference;       
  typedef implementation_defined              difference_type;       
  typedef implementation_defined              size_type;             
  typedef implementation_defined              value_compare;         
  typedef implementation_defined              key_compare;           
  typedef implementation_defined              iterator;              
  typedef implementation_defined              const_iterator;        
  typedef implementation_defined              reverse_iterator;      
  typedef implementation_defined              const_reverse_iterator;
  typedef implementation_defined              node_traits;           
  typedef implementation_defined              node;                  
  typedef implementation_defined              node_ptr;              
  typedef implementation_defined              const_node_ptr;        
  typedef implementation_defined              node_algorithms;       
  typedef node_algorithms::insert_commit_data insert_commit_data;    
  // construct/copy/destruct
  bstree();
  explicit bstree(const key_compare &, const value_traits & = value_traits());
  template<typename Iterator> 
    bstree(bool, Iterator, Iterator, const key_compare & = key_compare(), 
           const value_traits & = value_traits());
  bstree(bstree &&);
  bstree & operator=(bstree &&);
  ~bstree();
  // public member functions
  iterator begin();
  const_iterator begin() const;
  const_iterator cbegin() const;
  iterator end();
  const_iterator end() const;
  const_iterator cend() const;
  reverse_iterator rbegin();
  const_reverse_iterator rbegin() const;
  const_reverse_iterator crbegin() const;
  reverse_iterator rend();
  const_reverse_iterator rend() const;
  const_reverse_iterator crend() const;
  iterator root();
  const_iterator root() const;
  const_iterator croot() const;
  key_compare key_comp() const;
  value_compare value_comp() const;
  bool empty() const;
  size_type size() const;
  void swap(bstree &);
  template<typename Cloner, typename Disposer> 
    void clone_from(const bstree &, Cloner, Disposer);
  template<typename Cloner, typename Disposer> 
    void clone_from(bstree &&, Cloner, Disposer);
  iterator insert_equal(reference);
  iterator insert_equal(const_iterator, reference);
  template<typename Iterator> void insert_equal(Iterator, Iterator);
  std::pair< iterator, bool > insert_unique(reference);
  iterator insert_unique(const_iterator, reference);
  template<typename Iterator> void insert_unique(Iterator, Iterator);
  std::pair< iterator, bool > 
  insert_unique_check(const key_type &, insert_commit_data &);
  std::pair< iterator, bool > 
  insert_unique_check(const_iterator, const key_type &, insert_commit_data &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< iterator, bool > 
    insert_unique_check(const KeyType &, KeyTypeKeyCompare, 
                        insert_commit_data &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< iterator, bool > 
    insert_unique_check(const_iterator, const KeyType &, KeyTypeKeyCompare, 
                        insert_commit_data &);
  iterator insert_unique_commit(reference, const insert_commit_data &);
  iterator insert_before(const_iterator, reference);
  void push_back(reference);
  void push_front(reference);
  iterator erase(const_iterator);
  iterator erase(const_iterator, const_iterator);
  size_type erase(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    size_type erase(const KeyType &, KeyTypeKeyCompare);
  template<typename Disposer> 
    iterator erase_and_dispose(const_iterator, Disposer);
  template<typename Disposer> 
    size_type erase_and_dispose(const key_type &, Disposer);
  template<typename Disposer> 
    iterator erase_and_dispose(const_iterator, const_iterator, Disposer);
  template<typename KeyType, typename KeyTypeKeyCompare, typename Disposer> 
    size_type erase_and_dispose(const KeyType &, KeyTypeKeyCompare, Disposer);
  void clear();
  template<typename Disposer> void clear_and_dispose(Disposer);
  size_type count(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    size_type count(const KeyType &, KeyTypeKeyCompare) const;
  iterator lower_bound(const key_type &);
  const_iterator lower_bound(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    iterator lower_bound(const KeyType &, KeyTypeKeyCompare);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    const_iterator lower_bound(const KeyType &, KeyTypeKeyCompare) const;
  iterator upper_bound(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    iterator upper_bound(const KeyType &, KeyTypeKeyCompare);
  const_iterator upper_bound(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    const_iterator upper_bound(const KeyType &, KeyTypeKeyCompare) const;
  iterator find(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    iterator find(const KeyType &, KeyTypeKeyCompare);
  const_iterator find(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    const_iterator find(const KeyType &, KeyTypeKeyCompare) const;
  std::pair< iterator, iterator > equal_range(const key_type &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< iterator, iterator > 
    equal_range(const KeyType &, KeyTypeKeyCompare);
  std::pair< const_iterator, const_iterator > 
  equal_range(const key_type &) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< const_iterator, const_iterator > 
    equal_range(const KeyType &, KeyTypeKeyCompare) const;
  std::pair< iterator, iterator > 
  bounded_range(const key_type &, const key_type &, bool, bool);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< iterator, iterator > 
    bounded_range(const KeyType &, const KeyType &, KeyTypeKeyCompare, bool, 
                  bool);
  std::pair< const_iterator, const_iterator > 
  bounded_range(const key_type &, const key_type &, bool, bool) const;
  template<typename KeyType, typename KeyTypeKeyCompare> 
    std::pair< const_iterator, const_iterator > 
    bounded_range(const KeyType &, const KeyType &, KeyTypeKeyCompare, bool, 
                  bool) const;
  iterator iterator_to(reference);
  const_iterator iterator_to(const_reference) const;
  pointer unlink_leftmost_without_rebalance();
  void replace_node(iterator, reference);
  void rebalance();
  iterator rebalance_subtree(iterator);
  template<typename T, class... Options2> 
    void merge_unique(bstree< T, Options2...> &);
   while(it! = itend);
  template<typename T, class... Options2> 
    void merge_equal(bstree< T, Options2...> &);
   while(it! = itend);
  template<typename ExtraChecker> void check(ExtraChecker) const;
  void check() const;
  // public static functions
  static bstree & container_from_end_iterator(iterator);
  static const bstree & container_from_end_iterator(const_iterator);
  static bstree & container_from_iterator(iterator);
  static const bstree & container_from_iterator(const_iterator);
  static iterator s_iterator_to(reference);
  static const_iterator s_iterator_to(const_reference);
  static void init_node(reference);
  static void remove_node(reference);
  // public data members
  static const bool constant_time_size;
  static const bool stateful_value_traits;
};

Description

Шаблон bstree - это несбалансированный интрузивный контейнер дерева поиска. Гарантия «без броска» действует только в том случае, если объект key_compare не бросает.

Гарантия сложности сохраняется только в том случае, если дерево сбалансировано, а логарифмическая сложность увеличивается до линейной, если дерево полностью не сбалансировано.

Параметр шаблона<T>- это тип, которым должен управлять контейнер. Пользователь может указать дополнительные опции и, если опции не предусмотрены, используются опции по умолчанию.

Контейнер поддерживает следующие варианты:<base_hook<>/member_hook<>/value_traits<>>,<constant_time_size<>>,<size_type<>>и<compare<>>.

`bstree` public construct/copy/destruct

<
```
bstree();
```
>
Эффекты: Постройте пустой контейнер.
Сложность: Постоянная.
Бросок: Если value_traits::node_traits::node constructor throws (это не происходит с заранее заданными Boost.Intrusive крючками) или копи-конструктор key_compare object throws. Базовая гарантия.
<
```
explicitbstree(constkey_compare&cmp,
               constvalue_traits&v_traits=value_traits());
```
>
Эффекты: Постраивает пустой контейнер с заданными сравнениями и чертами.
Сложность: Постоянная.
Бросает: Если value_traits::node_traits::node constructor throws (это не происходит с заранее заданными Boost.Intrusive крючками) или копи-конструктор key_compare object throws. Базовая гарантия.
<
```
template<typenameIterator>
 bstree(boolunique,Iteratorb,Iteratore,
        constkey_compare&cmp=key_compare(),
        constvalue_traits&v_traits=value_traits());
```
>
Требуется: Отклоняющий итератор должен давать значение l типа value_type. cmp должна быть функцией сравнения, которая вызывает строгий слабый порядок.
Эффекты: Конструирует пустой контейнер и вставляет элементы из [b, e]
Сложность: Линейный в N, если [b, e] уже отсортирован с использованием comp и иначе N * log N, где N — расстояние между первым и последним.
Бросает: Если value_traits::node_traits::node constructor throws (это не происходит с предопределенным Boost). Навязчивые крючки или конструктор/оператор() копирования бросков объекта key_compare. Базовая гарантия.
<
```
bstree(bstree&&x);
```
>
Эффекты: делать
<
```
bstree&operator=(bstree&&x);
```
>
Эффекты: делать
<
```
~bstree();
```
>
Эффекты: Отделяет от этого все элементы. Объекты в наборе не удаляются (т.е. не называются деструкторы), но узлы по шаблонному параметру<value_traits>перезапускаются и, таким образом, могут быть повторно использованы.
Сложность: Линейные к элементам, содержащимся в *это.
Броски: Ничего.

`bstree` public member functions

<
```
iteratorbegin();
```
>
Эффекты: Возвращает итератор, указывающий на начало контейнера.
Сложность: Постоянная.
Броски: Ничего.
<
```
const_iteratorbegin()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на начало контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorcbegin()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на начало контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
iteratorend();
```
>
Эффекты: Возвращает итератор, указывающий на конец контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorend()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на конец контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorcend()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на конец контейнера.
Сложность: Постоянная.
Броски: Ничего.
<
```
reverse_iteratorrbegin();
```
>
Эффекты: Возвращает обратный_iterator, указывающий на начало обратного контейнера.
Сложность: Константа.
Бросает: Ничего.
<
```
const_reverse_iteratorrbegin()const;
```
>
Эффекты: Возвращает const_reverse_iterator, указывающий на начало обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
<
```
const_reverse_iteratorcrbegin()const;
```
>
Эффекты: Возвращает const_reverse_iterator, указывающий на начало обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
<
```
reverse_iteratorrend();
```
>
Эффекты: Возвращает обратный_iterator, указывающий на конец обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
<
```
const_reverse_iteratorrend()const;
```
>
Эффекты: Возвращает const_reverse_iterator, указывающий на конец обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
<
```
const_reverse_iteratorcrend()const;
```
>
Эффекты: Возвращает const_reverse_iterator, указывающий на конец обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
<
```
iteratorroot();
```
>
Эффекты: Возвращает итератор, указывающий на корневой узел контейнера или конец(), если он не присутствует.
Сложность: Постоянная.
Броски: Ничего.
<
```
const_iteratorroot()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на корневой узел контейнера или кенд(), если он отсутствует.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorcroot()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на корневой узел контейнера или кенд(), если он отсутствует.
Сложность: Постоянная.
Бросает: Ничего.
<
```
key_comparekey_comp()const;
```
>
Эффекты: Возвращает объект key_compare, используемый контейнером.
Сложность: Постоянная.
Броски: Если бросит key_compare копи-конструктор.
<
```
value_comparevalue_comp()const;
```
>
Эффекты: Возвращает значение_сравнительный объект, используемый контейнером.
Сложность: Постоянная.
Бросает: Если value_compare копи-конструктор бросает.
<
```
boolempty()const;
```
>
Эффекты: Возвращается, если контейнер пуст.
Сложность: Постоянная.
Броски: Ничего.
<
```
size_typesize()const;
```
>
Эффекты: Возвращает количество элементов, хранящихся в контейнере.
Сложность: Линейный к элементам, содержащимся в *это, если опция постоянного размера отключена. Постоянное время иначе.
Бросает: Ничего.
<
```
voidswap(bstree&other);
```
>
: Изменить содержимое двух контейнеров.
Сложность: Постоянная.
Броски: Если сравнительный своп функтора бросает вызов.
<
```
template<typenameCloner,typenameDisposer>
 voidclone_from(constbstree&src,Clonercloner,Disposerdisposer);
```
>
Требуется: Диспетчер::оператор()(указатель) не должен бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.
Эффекты: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src, вызывающего Клонера::оператор()(const_reference) и вставляет их на *это. Копирует предикат из исходного контейнера.
Если клонер бросает, все клонированные элементы несвязаны и расположены, вызывая Диспозитор::оператор()(указатель).
Сложность: Линейный стертый плюс вставленные элементы.
Бросок: Если клонер бросает или предикат копирования, задание бросает. Базовая гарантия.
<
```
template<typenameCloner,typenameDisposer>
 voidclone_from(bstree&&src,Clonercloner,Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.
Эффекты: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src, вызывающего Клонера::оператор()(ссылка) и вставляет их на *это. Копирует предикат из исходного контейнера.
Если клонер бросает, все клонированные элементы несвязаны и расположены, вызывая Диспозитор::оператор()(указатель).
Сложность: Линейный стертый плюс вставленные элементы.
Бросок: Если клонер бросает или предикат копирования, задание бросает. Основная гарантия.
Примечание: Эта версия может модифицировать исходный контейнер, полезный для реализации семантики перемещения.
<
```
iteratorinsert_equal(referencevalue);
```
>
Требуется: Значение должно быть lvalue
Эффекты: Вставляет значение в контейнер перед верхней границей.
Сложность: Средняя сложность для вставочного элемента является самой логарифмической.
Броски: Если выполняется внутренняя функция key_compare ordering. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
iteratorinsert_equal(const_iteratorhint,referencevalue);
```
>
Требуется: Значение должно быть значением l, а «наконечник» должен быть действительным итератором.
Эффекты: Вставляет х в контейнер, используя «наконечник» в качестве подсказки, где он будет вставлен. Если «подсказка» находится в верхнем узле, вставка занимает постоянное время (два сравнения в худшем случае)
Сложность: Логарифмический вообще, но это амортизированное постоянное время, если t вставлено непосредственно перед намёком.
Бросок: Если выполняется внутренняя функция key_compare ordering. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
template<typenameIterator>voidinsert_equal(Iteratorb,Iteratore);
```
>
Требуется: Ссылочный итератор должен давать значение l типа value_type.
Эффекты: Вставляет каждый элемент диапазона в контейнер перед верхней границей ключа каждого элемента.
Сложность: Диапазон вставки, как правило, O(N * log(N)), где N - размер диапазона. Однако она линейна в N, если диапазон уже отсортирован по значению_comp().
Бросок: Ничего.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
std::pair<iterator,bool>insert_unique(referencevalue);
```
>
Требуется: Значение должно быть значением l
Эффекты: Вставляет значение в контейнер, если оно еще не присутствует.
Сложность: Средняя сложность для вставочного элемента является самой логарифмической.
Броски: Ничего.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
iteratorinsert_unique(const_iteratorhint,referencevalue);
```
>
Требуется: Значение должно быть значением l, а «наконечник» должен быть действительным итератором
Эффекты: Пытается вставить x в контейнер, используя «наконечник» в качестве подсказки, где он будет вставлен.
Сложность: Логарифмический в целом, но это амортизированное постоянное время (два сравнения в худшем случае), если t вставлено непосредственно перед подсказкой.
Бросает: Ничего.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
template<typenameIterator>voidinsert_unique(Iteratorb,Iteratore);
```
>
Требуется: Ссылочный итератор должен давать значение l типа value_type.
Эффекты: Пытается вставить каждый элемент диапазона в контейнер.
Сложность: Диапазон вставки, как правило, O(N * log(N)), где N - размер диапазона. Однако он является линейным в N, если диапазон уже отсортирован по значению_comp().
Бросок: Ничего.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
std::pair<iterator,bool>
insert_unique_check(constkey_type&key,insert_commit_data&commit_data);
```
>
Эффекты: Проверяет, можно ли вставить значение в контейнер, используя предоставленный пользователем ключ вместо самого значения.
Возвращение: Если существует эквивалентное значение, то пара, содержащая итератор, возвращается к уже существующей стоимости и ложна. Если значение может быть вставлено, возвращается истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Сложность: Средняя сложность в лучшем случае логарифмическая.
Броски: Если выполняется функция заказа. Сильная гарантия.
<
```
std::pair<iterator,bool>
insert_unique_check(const_iteratorhint,constkey_type&key,
                   insert_commit_data&commit_data);
```
>
Эффекты: Проверяет, может ли значение быть вставлено в контейнер, используя предоставленный пользователем ключ вместо самого значения, используя «подсказку» в качестве подсказки к тому, где оно будет вставлено.
Возвращение: Если существует эквивалентное значение, то пара, содержащая итератор, возвращается к уже существующей стоимости и ложна. Если значение может быть вставлено, возвращается истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Сложность: Логарифмический в целом, но это амортизированное постоянное время, если t вставляется непосредственно перед подсказкой.
Бросок: Если выполняется функция заказа. Сильная гарантия.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<iterator,bool>
 insert_unique_check(constKeyType&key,KeyTypeKeyComparecomp,
                     insert_commit_data&commit_data);
```
>
Требуется: Comp должен быть функцией сравнения, которая вызывает ту же строгую слабую упорядоченность, что и key_compare. Разница в том, что комп сравнивает произвольный ключ с содержащимися значениями.
Эффекты: Проверяет, можно ли вставить значение в контейнер, используя предоставленный пользователем ключ вместо самого значения.
Возвращение: Если существует эквивалентное значение, то пара, содержащая итератор, возвращается к уже существующей стоимости и ложна. Если значение может быть вставлено, возвращается истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Сложность: Средняя сложность в лучшем случае логарифмическая.
Броски: Если выполняется функция заказа. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при построении стоимостного типа: при наличии эквивалентного значения построенный объект должен быть отброшен. Часто часть узла, которая используется для наложения заказа, намного дешевле в конструировании, чем значение_тип, и эта функция предлагает возможность использовать эту часть для проверки того, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить значение_тип и использовать «insert_commit» для вставки объекта в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
"commit_data" остается в силе для последующего "insert_commit" только в том случае, если из контейнера не вставлено или стерто больше объектов.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<iterator,bool>
 insert_unique_check(const_iteratorhint,constKeyType&key,
                     KeyTypeKeyComparecomp,
                     insert_commit_data&commit_data);
```
>
Требуется: Comp должен быть функцией сравнения, которая вызывает ту же строгую слабую упорядоченность, что и key_compare. Разница в том, что комп сравнивает произвольный ключ с содержащимися значениями.
Эффекты: Проверяет, может ли значение быть вставлено в контейнер, используя предоставленный пользователем ключ вместо самого значения, используя «подсказку» в качестве подсказки к тому, где оно будет вставлено.
Возвращение: Если существует эквивалентное значение, то пара, содержащая итератор, возвращается к уже существующей стоимости и ложна. Если значение может быть вставлено, возвращается истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Сложность: Логарифмическое вообще, но это амортизированное постоянное время, если t вставлено непосредственно перед намёком.
Бросает: Если выполняется функция заказа. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при построении стоимостного типа: при наличии эквивалентного значения построенный объект должен быть отброшен. Часто часть конструкции, которая используется для наложения заказа, намного дешевле в конструировании, чем значение_тип, и эта функция предлагает возможность использовать этот ключ, чтобы проверить, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить значение_тип и использовать «insert_commit» для вставки объекта в постоянное время. Это может придать полную сложность с постоянным временем для вставки: check(O(1)) + commit(O(1)).
"commit_data" остается в силе для последующего "insert_commit" только в том случае, если из контейнера не вставлено или стерто больше объектов.
<
```
iteratorinsert_unique_commit(referencevalue,
                             constinsert_commit_data&commit_data);
```
>
Требуется: Значение должно быть значением типа value_type. commit_data должны быть получены из предыдущего вызова на «insert_check». Никакие объекты не должны были вставляться или стираться из контейнера между «insert_check», который заполнил «commit_data», и призывом «insert_commit».
: Вставляет значение в контейнер, используя информацию, полученную из «commit_data», которую заполнил предыдущий «insert_check».
Возвращение: Итератор вновь вставленного объекта.
Сложность: Постоянное время.
Бросает: Ничего.
Примечания: Эта функция имеет смысл только в том случае, если ранее была выполнена «insert_check» для заполнения «commit_data». Не следует вставлять или стирать значение между вызовами «insert_check» и «insert_commit».
<
```
iteratorinsert_before(const_iteratorpos,referencevalue);
```
>
Требуется: Значение должно быть значением l, "pos" должно быть действительным итератором (или концом) и должно быть датчиком значения после вставки в соответствии с предикатом
: Вставляет х в контейнер перед "по".
Сложность:
Бросок: Ничего.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если «pos» не является преемником инварианта упорядочивания контейнера «value», он будет нарушен. Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
<
```
voidpush_back(referencevalue);
```
>
Требуется: Значение должно быть lvalue, и оно должно быть не меньше, чем наибольший вставленный ключ
Эффекты: Вставляет х в контейнер в последнем положении.
Сложность:
Бросает: Ничего.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если значение меньше наибольшего инварианта упорядочивания вставленного ключа, оно будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только по соображениям производительности продвинутыми пользователями.
<
```
voidpush_front(referencevalue);
```
>
Требуется: Значение должно быть значением l, и оно не должно быть больше минимального вставленного ключа
Эффекты: Вставьте x в контейнер в первом положении.
Сложность: Постоянное время.
Бросает: Ничего.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если значение больше минимального инварианта вставленного ключевого контейнера будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
<
```
iteratorerase(const_iteratori);
```
>
Эффекты: Стирает элемент, на который указывает i.
Сложность: Средняя сложность для элемента стирания — постоянное время.
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
iteratorerase(const_iteratorb,const_iteratore);
```
>
Эффекты: Уничтожает диапазон, указанный на b-конце e.
Сложность: Средняя сложность для диапазона стирания составляет максимум O(log(size()+N)), где N - число элементов в диапазоне.
Бросок: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
size_typeerase(constkey_type&key);
```
>
Эффекты: Стирает все элементы с заданным значением.
Возврат: Число стертых элементов.
Сложность: O(log(size() + N).
Бросает: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 size_typeerase(constKeyType&key,KeyTypeKeyComparecomp);
```
>
Требуется: ключ является значением, таким, что<*this>разделено относительно comp(nk, key) и !comp(key, nk), с comp(nk, key), подразумевающим !comp(key, nk), с nk ключ_тип значения_type вставлен в<*this>.
Эффекты: Стирает все элементы заданным ключом. согласно сравнительным функторам «комп.»
Возвращение: Количество стертых элементов.
Сложность: O(log(size() + N).
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
template<typenameDisposer>
 iteratorerase_and_dispose(const_iteratori,Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать.
Эффекты: Стирает элемент, на который указывает i. Утилизатор::оператор()(указатель) вызывается для удаленного элемента.
Сложность: Средняя сложность для элемента стирания — постоянное время.
Броски: Ничего.
Примечание: Инвалидирует итераторы на стертые элементы.
<
```
template<typenameDisposer>
 size_typeerase_and_dispose(constkey_type&key,Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать.
Эффекты: Стирает все элементы с заданным значением. Диспозитор::оператор()(указатель) вызывается для удаленных элементов.
Возвращение: Число стертых элементов.
Сложность: O(log(size() + N.]
Бросает: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
template<typenameDisposer>
 iteratorerase_and_dispose(const_iteratorb,const_iteratore,
                            Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать.
Эффекты: Уничтожает диапазон, указанный на b-конце e. Утилизатор::оператор()(указатель) вызывается для удаленных элементов.
Сложность: Средняя сложность для диапазона стирания составляет максимум O(log(size() + N)), где N - число элементов в диапазоне.
Броски: Ничего.
Примечание: Инвалидирует итераторы на стертые элементы.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare,typenameDisposer>
 size_typeerase_and_dispose(constKeyType&key,KeyTypeKeyComparecomp,
                             Disposerdisposer);
```
>
Требуется: Ключ — это такое значение, что<*this>разбивается по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk) и nk ключ_тип значения_типа, вставленный в<*this>.
Требует: Диспетчер::оператор()(указатель) не должен бросать.
Эффекты: Стирает все элементы заданным ключом. По данным сравнения функтор «комп». Диспозитор::оператор()(указатель) вызывается для удаленных элементов.
Возвращение: Число стертых элементов.
Сложность: O(log(size() + N).
Бросает: Ничего.
Примечание: Инвалидирует итераторы на стертые элементы.
<
```
voidclear();
```
>
Эффекты: Стирает все элементы.
Сложность: Линейный по количеству элементов на контейнере. Если это безопасный режим или авто-разъединить значение_тип. Постоянное время иначе.
Бросает: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
template<typenameDisposer>voidclear_and_dispose(Disposerdisposer);
```
>
Эффекты: Стирает все элементы, вызывающие диспергатор (p), чтобы каждый узел был стерт.Сложность: Средняя сложность составляет максимум O(log(size()+N)), где N - количество элементов в контейнере.
Бросок: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Звонки N раз для удаления функтора.
<
```
size_typecount(constkey_type&key)const;
```
>
Эффекты: Возвращает число содержащихся элементов с заданным значением
Сложность: Логарифмическое к числу содержащихся элементов плюс линейное к числу объектов с заданным значением.
Броски: Если<key_compare>бросок.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 size_typecount(constKeyType&key,KeyTypeKeyComparecomp)const;
```
>
Требуется: Ключ - это значение, такое, что<*this>разделено относительно comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk), а nk - ключ_тип значения_type, вставленный в<*this>.
Эффекты: Возвращает число содержащихся элементов с заданным ключом
Сложность: Логарифмическое к числу содержащихся элементов плюс линейное к числу объектов с заданным ключом.
Бросок: Если<comp>бросит.
<
```
iteratorlower_bound(constkey_type&key);
```
>
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше k или конца (), если этот элемент не существует.
Сложность: Логарифмический.
Бросает: Если<key_compare>бросит.
<
```
const_iteratorlower_bound(constkey_type&key)const;
```
>
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше k или конца (), если этот элемент не существует.
Сложность: Логарифмический.
Бросает: Если<key_compare>бросит.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 iteratorlower_bound(constKeyType&key,KeyTypeKeyComparecomp);
```
>
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше k или конца (), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Если<key_compare>бросок.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 const_iterator
 lower_bound(constKeyType&key,KeyTypeKeyComparecomp)const;
```
>
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше k или конца(), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если<key_compare>бросит
<
```
iteratorupper_bound(constkey_type&key);
```
>
Эффекты: Возвращает итератор к первому элементу, ключ которого больше k или конца(), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если<key_compare>бросит
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 iteratorupper_bound(constKeyType&key,KeyTypeKeyComparecomp);
```
>
Требуется: Ключ является значением, таким, что<*this>разделен относительно !comp(ключ, nk), с nk ключ_тип значения_тип вставлен в<*this>.
Эффекты: Возвращает итератор к первому элементу, чей ключ больше k согласно comp или end(), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если бросит<comp>.
<
```
const_iteratorupper_bound(constkey_type&key)const;
```
>
Эффекты: Возвращает итератор к первому элементу, ключ которого больше k или конца(), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Если<key_compare>бросок.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 const_iterator
 upper_bound(constKeyType&key,KeyTypeKeyComparecomp)const;
```
>
Требуется: Ключ — это такое значение, что<*this>разбивается на !comp(ключ, nk), при этом nk ключ_тип значения_тип вставляется в<*this>.
Эффекты: Возвращает итератор к первому элементу, чей ключ больше k согласно comp или end(), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Если<comp>бросок.
<
```
iteratorfind(constkey_type&key);
```
>
Эффекты: Найден итератор к первому элементу, ключ которого k или конец(), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если<key_compare>бросит.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 iteratorfind(constKeyType&key,KeyTypeKeyComparecomp);
```
>
Требуется: ключ является значением, таким, что<*this>разбивается по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk), а nk ключ_тип значения_type вставляется в<*this>.
Эффекты: Найден итератор к первому элементу, ключ которого k или конец(), если этот элемент не существует.
Сложность: Логарифмическая.
Броски: Если<comp>бросит.
<
```
const_iteratorfind(constkey_type&key)const;
```
>
Эффекты: Найден итератор к первому элементу, ключ которого k или конец(), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если<key_compare>бросит.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 const_iteratorfind(constKeyType&key,KeyTypeKeyComparecomp)const;
```
>
Требуется: Ключ является значением, таким, что<*this>разбивается по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk), а nk ключ_тип значения_type вставляется в<*this>.
: Найден итератор к первому элементу, ключ которого k или конец(), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Если<comp>бросок.
<
```
std::pair<iterator,iterator>equal_range(constkey_type&key);
```
>
Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Бросок: Если<key_compare>бросит.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<iterator,iterator>
 equal_range(constKeyType&key,KeyTypeKeyComparecomp);
```
>
Требуется: Ключ - это значение, такое, что<*this>разделено по отношению к comp(nk, key) и !comp(key, nk), с comp(nk, key), подразумевающим !comp(key, nk), с nk ключ_тип значения_type вставлен в<*this>.
Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Броски: Если<comp>бросит.
<
```
std::pair<const_iterator,const_iterator>
equal_range(constkey_type&key)const;
```
>
Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Бросок: Если<key_compare>бросок.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<const_iterator,const_iterator>
 equal_range(constKeyType&key,KeyTypeKeyComparecomp)const;
```
>
Требуется: Ключ - это значение, такое, что<*this>разделено по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk), причем nk ключ_тип значения_type вставлен в<*this>.
Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Броски: Если<comp>бросок.
<
```
std::pair<iterator,iterator>
bounded_range(constkey_type&lower_key,constkey_type&upper_value,
             boolleft_closed,boolright_closed);
```
>
Требует:<upper_key>не должен предшествовать<lower_key>в соответствии с key_compare. [key_comp()(upper_key, lower_key) должен быть ложным]
Если<lower_key>эквивалентен<upper_key>[!key_comp()(upper_key, lower_key) && !key_comp()(lower_key, upper_key)] тогда ('left_closed' | | 'right_closed') должен быть ложным.
Эффекты: Возвращает пару со следующими критериями:
первый = нижний_связанный (нижний_ключ), если левый_закрытый, верхний_связанный (нижний_ключ) в противном случае
второй = верхний_связанный (верхний_ключ), если правый_закрытый, нижний_связанный (верхний_ключ) в противном случае
: Логарифмический.
Бросок: Если<key_compare>бросает
Примечание: Эта функция может быть более эффективной, чем вызов верхнего и нижнего пределов для нижнего и верхнего значений.
Примечание: Экспериментальная функция, интерфейс может измениться в будущих выпусках.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<iterator,iterator>
 bounded_range(constKeyType&lower_key,constKeyType&upper_key,
               KeyTypeKeyComparecomp,boolleft_closed,boolright_closed);
```
>
Требует:<lower_key>является значением, таким, что<*this>разделено по отношению к comp(nk, lower_key), если Left_closed является истинным, по отношению к !comp(lower_key, nk) в противном случае.
<upper_key>не должен предшествовать<lower_key>в соответствии с Comp [comp(upper_key, lower_key) должно быть ложным]
Если<lower_key>эквивалентен<upper_key>[!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] тогда ['left_closed' | | 'right_closed'] должно быть ложным.
Эффекты: Возвращает пару со следующими критериями:
первый = нижний_bound(lower_key, comp) если левый_замкнут, верхний_bound(lower_key, comp) в противном случае
второй = верхний_bound(upper_key, comp) если правый_замкнут, нижний_bound(upper_key, comp) в противном случае
: Логарифмический.
Броски: Если<comp>бросает.
Примечание: Эта функция может быть более эффективной, чем вызов top_bound и lower_bound для low_key и upper_key.
Примечание: Экспериментальная функция, интерфейс может измениться в будущих выпусках.
<
```
std::pair<const_iterator,const_iterator>
bounded_range(constkey_type&lower_key,constkey_type&upper_key,
             boolleft_closed,boolright_closed)const;
```
>
Требует:<upper_key>не должен предшествовать<lower_key>согласно key_compare. [key_comp()(upper_key, lower_key) должен быть ложным]
Если<lower_key>эквивалентно<upper_key>[!key_comp()(upper_key, lower_key) && !key_comp()(lower_key, upper_key)], то ['left_closed' | | 'right_closed') должно быть ложным
: Возвращает пару со следующими критериями:
первый = нижний_bound(lower_key) если левый_замкнут, верхний_bound(lower_key) иначе
второй = верхний_bound(upper_key) если правый_замкнут, нижний_bound(upper_key) иначе
: Логарифмический.
Броски: Если<key_compare>бросает.
Примечание: Эта функция может быть более эффективной, чем вызов верхнего и нижнего пределов для нижнего и верхнего значений.
Примечание: Экспериментальная функция, интерфейс может измениться в будущих выпусках.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<const_iterator,const_iterator>
 bounded_range(constKeyType&lower_key,constKeyType&upper_key,
               KeyTypeKeyComparecomp,boolleft_closed,boolright_closed)const;
```
>
Требует:<lower_key>является значением, таким, что<*this>разделено относительно !comp(lower_key, nk) в противном случае.
<upper_key>является значением, таким, что<*this>разделено относительно !comp(upper_key, nk) в отношении !comp(upper_key, upper_key) в противном случае.
<upper_key>не должен предшествовать<lower_key>согласно .com [comp(upper_key, lower_key) должен быть ложным]
<lower_key>Если<lower_key>эквивалентен<upper_key>[!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] тогда ['left_closed' | | '1880'Эффекты[1884 Возвращает пару со следующими критериями:
первый = нижний_bound(lower_key, comp) если левый_закрытый, верхний_bound(lower_key, comp) в противном случае
второй = верхний_bound(upper_key, comp) если правый_закрытый, нижний_bound(upper_key, comp) в противном случае
: Логарифмический.
Броски: Если<comp>бросает.
Примечание: Эта функция может быть более эффективной, чем вызов top_bound и lower_bound для low_key и upper_key.
Примечание: Экспериментальная функция, интерфейс может измениться в будущих выпусках.
<
```
iteratoriterator_to(referencevalue);
```
>
Требует: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.
Эффекты: Возврат: действительный итератор i, относящийся к набору, который указывает на значение
Сложность: Констант.
Броски: Ничего.
<
```
const_iteratoriterator_to(const_referencevalue)const;
```
>
Требует: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.
Эффекты: Возврат: действительный const_iterator i, принадлежащий набору, который указывает на значение
Сложность: Констант.
Бросает: Ничего.
<
```
pointerunlink_leftmost_without_rebalance();
```
>
Эффекты: Развязывает самый левый узел контейнера.
Сложность: Средняя сложность — это постоянное время.
Броски: Ничего.
Примечания: Эта функция разрушает контейнер, и контейнер может использоваться только для дополнительных вызовов unlink_leftmost_without_rebalance. Эта функция обычно используется для достижения поэтапного контролируемого разрушения контейнера.
<
```
voidreplace_node(iteratorreplace_this,referencewith_this);
```
>
Требуется: Заменить_это должен быть действительный итератор *это и с_это не должно быть вставлено в любой контейнер.
Эффекты: Заменяет замену_this в своем положении в контейнере с_this. Контейнер не нужно перебалансировать.
Сложность: Констант.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты заказа контейнера, если с_это не эквивалентно *заменить_это в соответствии с правилами заказа. Эта функция быстрее, чем стирание и вставка узла, поскольку не требуется перебалансировки или сравнения.
<
```
voidrebalance();
```
>
Эффекты: Перебалансирует дерево.
Бросает: Ничего.
Сложность: Линейный.
<
```
iteratorrebalance_subtree(iteratorroot);
```
>
Требуется: Old_root — это узел дерева.
Эффекты: Уравновешивает поддеревья, укорененные в old_root.
Возвращение: Новый корень дерева.
Бросает: Ничего.
Сложность: Линейный к элементам в поддереве.
<
```
template<typenameT,class...Options2>
 voidmerge_unique(bstree<T,Options2...>&);
```
>
Требуется: Варианты контейнера «источник» могут отличаться только функцией сравнения от *этого.
Эффекты: Попытки извлечь каждый элемент из источника и вставить его в объект сравнения *это. Если в элементе есть ключ, эквивалентный ключу элемента из источника, то этот элемент не извлекается из источника.
Посткондиционер: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в это, а не в источник.
Броски: Ничего, если объект сравнения не бросит.
Сложность: N log(a.size() + N) (N имеет значение source.size())
<
```
while(it!=itend);
```
>
<
```
template<typenameT,class...Options2>
 voidmerge_equal(bstree<T,Options2...>&);
```
>
Требуется: Варианты контейнера «источник» могут отличаться только функцией сравнения от *этого.
Эффекты: Извлекает каждый элемент в источнике и вставляет его в объект сравнения *это.
Посткондиция: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в это, а не в источник.
Бросок: Ничего, если объект сравнения не бросит.
Сложность: N log(a.size() + N) (N имеет значение source.size())
<
```
while(it!=itend);
```
>
<
```
template<typenameExtraChecker>voidcheck(ExtraCheckerextra_checker)const;
```
>
Эффекты: Утверждает целостность контейнера с дополнительными проверками, предоставляемыми пользователем.
Сложность: Линейное время.
Примечание: Метод может не иметь эффекта при отключении утверждений (например, с NDEBUG). Экспериментальная функция интерфейса может измениться в будущих версиях.
<
```
voidcheck()const;
```
>
Эффекты: Утверждает целостность контейнера.
Сложность: Линейное время.
Примечание: Метод не имеет эффекта, когда утверждения выключены (например, с NDEBUG). Экспериментальная функция интерфейса может измениться в будущих версиях.

`bstree` public static functions

<
```
staticbstree&container_from_end_iterator(iteratorend_iterator);
```
>
Предварительное условие: end_iterator должен быть действительным конечным итератором контейнера.
Эффекты: Возвращает конст-ссылку на контейнер, связанный с конечным итератором
Бросает: Ничего.
Сложность: Постоянная.
<
```
staticconstbstree&container_from_end_iterator(const_iteratorend_iterator);
```
>
Предварительное условие: end_iterator должен быть действительным конечным const_iterator контейнера.
Эффекты: Возвращает ссылку на контейнер, связанный с итератором
Бросает: Ничего.
Сложность: Постоянная.
<
```
staticbstree&container_from_iterator(iteratorit);
```
>
Предварительное условие: он должен быть действительным итератором контейнера.
Эффекты: Возвращает ссылку на контейнер, связанный с итератором
Бросает: Ничего.
Сложность: Логарифмический.
<
```
staticconstbstree&container_from_iterator(const_iteratorit);
```
>
Предварительное условие: это должен быть действительный конечный конст_итер контейнера.
Эффекты: Возвращает конст-ссылку на контейнер, связанный с конечным итератором
Бросает: Ничего.
Сложность: Логарифмический.
<
```
staticiterators_iterator_to(referencevalue);
```
>
Требуется: Значение должно быть lvalue и должно быть в наборе соответствующего типа. Иначе поведение не определено.
Эффекты: Возврат: действительный итератор i, относящийся к набору, который указывает на значение
Сложность: Постоянная.
Бросает: Ничего.
Примечание: Эта статическая функция доступна только в том случае, если значенияне имеют состояния.
<
```
staticconst_iterators_iterator_to(const_referencevalue);
```
>
Требуется: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.
Эффекты: Возврат: действительный const_iterator i, принадлежащий множеству, которое указывает на значение
Сложность: Постоянная.
Бросает: Ничего.
Примечание: Эта статическая функция доступна только в том случае, если значенияне имеют состояния.
<
```
staticvoidinit_node(referencevalue);
```
>
Требуется: Стоимость не должна находиться в контейнере.
Эффекты: Init_node ставит крючок значения в известное состояние по умолчанию.
Броски: Ничего.
Сложность: Постоянное время.
Примечание: Эта функция помещает крюк в известное состояние по умолчанию, используемое auto_unlink и безопасными крючками.
<
```
staticvoidremove_node(referencevalue);
```
>
Эффекты: удаляет «значение» из контейнера.
Броски: Ничего.
Сложность: Логарифмическое время.
Примечание: Эта статическая функция может использоваться только в непостоянных контейнерах с размером времени, которые имеют функторы сравнения без состояния.
Если пользователь называет эту функцию контейнером с постоянным размером времени или функтором сравнения состояния, будет выпущена ошибка компиляции.

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

Class template bstree

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

Boost C++ Libraries

Class template bstree

Synopsis

Description

bstree public construct/copy/destruct

bstree public member functions

bstree public static functions

`bstree` public construct/copy/destruct

`bstree` public member functions

`bstree` public static functions