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

Class template treap

boost::intrusive::treap

Synopsis

// In header: <boost/intrusive/treap.hpp>
template<typename T, class... Options> 
class treap {
public:
  // types
  typedef ValueTraits                                    value_traits;          
  typedef implementation_defined::pointer                pointer;               
  typedef implementation_defined::const_pointer          const_pointer;         
  typedef implementation_defined::value_type             value_type;            
  typedef implementation_defined::key_type               key_type;              
  typedef implementation_defined::key_of_value           key_of_value;          
  typedef implementation_defined::reference              reference;             
  typedef implementation_defined::const_reference        const_reference;       
  typedef implementation_defined::difference_type        difference_type;       
  typedef implementation_defined::size_type              size_type;             
  typedef implementation_defined::value_compare          value_compare;         
  typedef implementation_defined::key_compare            key_compare;           
  typedef implementation_defined::iterator               iterator;              
  typedef implementation_defined::const_iterator         const_iterator;        
  typedef implementation_defined::reverse_iterator       reverse_iterator;      
  typedef implementation_defined::const_reverse_iterator const_reverse_iterator;
  typedef implementation_defined::node_traits            node_traits;           
  typedef implementation_defined::node                   node;                  
  typedef implementation_defined::node_ptr               node_ptr;              
  typedef implementation_defined::const_node_ptr         const_node_ptr;        
  typedef implementation_defined                         node_algorithms;       
  typedef implementation_defined                         priority_compare;      
  typedef unspecified                                    key_node_prio_comp_t;  
  typedef node_algorithms::insert_commit_data            insert_commit_data;    
  // construct/copy/destruct
  treap();
  explicit treap(const key_compare &, 
                 const priority_compare & = priority_compare(), 
                 const value_traits & = value_traits());
  template<typename Iterator> 
    treap(bool, Iterator, Iterator, const key_compare & = key_compare(), 
          const priority_compare & = priority_compare(), 
          const value_traits & = value_traits());
  treap(treap &&);
  treap & operator=(treap &&);
  ~treap();
  // public member functions
  template<typename KeyPrioComp> 
    unspecified key_node_prio_comp(KeyPrioComp) const;
  iterator begin();
  const_iterator begin() const;
  const_iterator cbegin() const;
  iterator end();
  const_iterator end() const;
  const_iterator cend() const;
  iterator top();
  const_iterator top() const;
  const_iterator ctop() 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;
  reverse_iterator rtop();
  const_reverse_iterator rtop() const;
  const_reverse_iterator crtop() const;
  key_compare key_comp() const;
  value_compare value_comp() const;
  bool empty() const;
  size_type size() const;
  priority_compare priority_comp() const;
  void swap(treap &);
  template<typename Cloner, typename Disposer> 
    void clone_from(const treap &, Cloner, Disposer);
  template<typename Cloner, typename Disposer> 
    void clone_from(treap &&, 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, 
           typename KeyValuePrioCompare> 
    std::pair< iterator BOOST_INTRUSIVE_I bool > 
    insert_unique_check(const KeyType &, KeyTypeKeyCompare, 
                        KeyValuePrioCompare, insert_commit_data &);
  template<typename KeyType, typename KeyTypeKeyCompare, 
           typename KeyValuePrioCompare> 
    std::pair< iterator, bool > 
    insert_unique_check(const_iterator, const KeyType &, KeyTypeKeyCompare, 
                        KeyValuePrioCompare, 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> 
    iterator erase_and_dispose(const_iterator, const_iterator, Disposer);
  template<typename Disposer> 
    size_type erase_and_dispose(const key_type &, 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);
  template<typename T, class... Options2> 
    void merge_unique(sgtree< T, Options2...> &);
   while(it! = itend);
  template<typename T, class... Options2> 
    void merge_equal(sgtree< T, Options2...> &);
   while(it! = itend);
  template<typename ExtraChecker> void check(ExtraChecker) const;
  void check() const;
  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 &);
  template<typename KeyType, typename KeyTypeKeyCompare> 
    iterator lower_bound(const KeyType &, KeyTypeKeyCompare);
  const_iterator lower_bound(const key_type &) const;
  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 remove_node(reference);
  // public static functions
  static treap & container_from_end_iterator(iterator);
  static const treap & container_from_end_iterator(const_iterator);
  static treap & container_from_iterator(iterator);
  static const treap & container_from_iterator(const_iterator);
  static iterator s_iterator_to(reference);
  static const_iterator s_iterator_to(const_reference);
  static void init_node(reference);
  // public data members
  static const bool constant_time_size;
  static const bool stateful_value_traits;
  static const bool safemode_or_autounlink;
};

Description

Шаблон класса treap - это интрузивный контейнер, который используется для создания интрузивных наборов и многосетовых контейнеров. Гарантия отсутствия броска действует только в том случае, если объект key_compare и объект priority_compare не выбрасываются.

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

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

`treap` public construct/copy/destruct

<
```
treap();
```
>
Эффекты: Постройте пустой контейнер.
Сложность: Постоянная.
Бросает: Если value_traits::node_traits::node constructor throws (это не происходит с предопределенным Boost). Навязчивые крючки) или конструктор копий бросания объектов value_compare/priority_compare. Базовая гарантия.
<
```
explicittreap(constkey_compare&cmp,
              constpriority_compare&pcmp=priority_compare(),
              constvalue_traits&v_traits=value_traits());
```
>
Эффекты: Построить пустой контейнер.
Сложность: Постоянство.
Бросает: Если value_traits::node_traits::node constructor throws (это не происходит с предопределенным Boost). Навязчивые крючки) или конструктор копий бросания объектов value_compare/priority_compare. Базовая гарантия.
<
```
template<typenameIterator>
 treap(boolunique,Iteratorb,Iteratore,
       constkey_compare&cmp=key_compare(),
       constpriority_compare&pcmp=priority_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/priority_compare. Базовая гарантия.
<
```
treap(treap&&x);
```
>
Эффекты: делать
<
```
treap&operator=(treap&&x);
```
>
Эффекты: делать
<
```
~treap();
```
>
Эффекты: Отделяет от этого все элементы. Объекты в наборе не удаляются (т.е. не называются деструкторы), но узлы по шаблонному параметру<value_traits>перезапускаются и, таким образом, могут быть повторно использованы.
Сложность: Линейные элементы, содержащиеся в *это.
Бросает: Ничего.

`treap` public member functions

template<typenameKeyPrioComp>
 unspecifiedkey_node_prio_comp(KeyPrioCompkeypriocomp)const;

<
```
iteratorbegin();
```
>
Эффекты: Возвращает итератор, указывающий на начало контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorbegin()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на начало контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorcbegin()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на начало контейнера.
Сложность: Постоянная.
Броски: Ничего.
<
```
iteratorend();
```
>
Эффекты: Возвращает итератор, указывающий на конец контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorend()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на конец контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorcend()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на конец контейнера.
Сложность: Постоянная.
Бросает: Ничего.
<
```
iteratortop();
```
>
Эффекты: Возвращает итератор, указывающий на наиболее приоритетный объект крана.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratortop()const;
```
>
Эффекты: Возвращает const_iterator, указывающий на объект с наивысшим приоритетом трэпа..
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_iteratorctop()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, указывающий на корневой узел контейнера или кенд(), если он отсутствует.
Сложность: Постоянная.
Броски: Ничего.
<
```
reverse_iteratorrtop();
```
>
Эффекты: Возвращает обратный_итератор, указывающий на объект с наивысшим приоритетом обратного рывка.
Сложность: Постоянная.
Бросает: Ничего.
<
```
const_reverse_iteratorrtop()const;
```
>
Эффекты: Возвращает const_reverse_iterator, указывая на наивысший приоритетный объект обратного рывка.
Сложность: Константа.
Бросает: Ничего.
<
```
const_reverse_iteratorcrtop()const;
```
>
Эффекты: Возвращает const_reverse_iterator, указывающий на объект с наивысшим приоритетом обратного трапа.
Сложность: Постоянная.
Бросает: Ничего.
<
```
key_comparekey_comp()const;
```
>
Эффекты: Возвращает объект key_compare, используемый контейнером.
Сложность: Постоянная.
Броски: Если бросит key_compare копи-конструктор.
<
```
value_comparevalue_comp()const;
```
>
Эффекты: Возвращает объект value_compare, используемый контейнером.
Сложность: Постоянная.
Броски: Если value_compare копи-конструктор бросает.
<
```
boolempty()const;
```
>
Эффекты: Возвращается, если контейнер пуст.
Сложность: Постоянная.
Броски: Ничего.
<
```
size_typesize()const;
```
>
Эффекты: Возвращает количество элементов, хранящихся в контейнере.
Сложность: Линейный к элементам, содержащимся в *это, если опция постоянного размера отключена. Постоянное время иначе.
Бросает: Ничего.
<
```
priority_comparepriority_comp()const;
```
>
Эффекты: Возвращает объект Priority_compare, используемый контейнером.
Сложность: Постоянная.
Броски: Если Priority_compare копи-конструктор бросает.
<
```
voidswap(treap&other);
```
>
Эффекты: Смахивает содержимое двух кранов.
Сложность: Постоянная.
Броски: Если сравнительный своп функтора бросает вызов.
<
```
template<typenameCloner,typenameDisposer>
 voidclone_from(consttreap&src,Clonercloner,Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.
Эффекты: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src, вызывающего Клонера::оператор()(const_reference) и вставляет их на *это. Копирует предикат из исходного контейнера.
Если клонер бросает, все клонированные элементы несвязаны и расположены, вызывая Диспозитор::оператор()(указатель).
Сложность: Линейный стертый плюс вставленные элементы.
Бросок: Если клонер бросает или предикат копирования, задание бросает. Базовая гарантия.
<
```
template<typenameCloner,typenameDisposer>
 voidclone_from(treap&&src,Clonercloner,Disposerdisposer);
```
>
Требуется: Диспетчер::оператор()(поинт) не должен бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.
Эффекты: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src, вызывающего Клонера::оператор()(ссылка) и вставляет их на *это. Копирует предикат из исходного контейнера.
Если клонер бросает, все клонированные элементы несвязаны и расположены, вызывая Диспозитор::оператор()(указатель).
Сложность: Линейный стертый плюс вставленные элементы.
Бросок: Если клонер бросает или предикат копирования, задание бросает. Базовая гарантия.
<
```
iteratorinsert_equal(referencevalue);
```
>
Требуется: значение должно быть lvalue
Эффекты: Вставляет значение в контейнер перед верхней границей.
Сложность: Средняя сложность для вставочного элемента является самой логарифмической.
Броски: Если внутренние функции key_compare или priority_compare бросятся. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
iteratorinsert_equal(const_iteratorhint,referencevalue);
```
>
Требуется: Значение должно быть значением l, а «наконечник» должен быть действительным итератором.
Эффекты: Вставляет х в контейнер, используя «наконечник» в качестве подсказки, где он будет вставлен. Если «подсказка» находится в верхнем узле, вставка занимает постоянное время (два сравнения в худшем случае)
Сложность: Логарифмический вообще, но это амортизированное постоянное время, если t вставлено непосредственно перед намёком.
Бросок: Если внутренние функции key_compare или priority_compare бросятся. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
template<typenameIterator>voidinsert_equal(Iteratorb,Iteratore);
```
>
Требуется: Ссылочный итератор должен давать значение l типа value_type.
Эффекты: Вставляет каждый элемент диапазона в контейнер перед верхней границей ключа каждого элемента.
Сложность: Диапазон вставки, как правило, O(N * log(N)), где N - размер диапазона. Однако он является линейным в N, если диапазон уже отсортирован по key_comp().
Бросает: Если внутренние функции key_compare или priority_compare бросятся. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
std::pair<iterator,bool>insert_unique(referencevalue);
```
>
Требуется: Значение должно быть lvalue
Эффекты: Вставляет значение в контейнер, если оно еще не присутствует.
Сложность: Средняя сложность для вставочного элемента является наиболее логарифмической.
Броски: Если внутренние функции key_compare или priority_compare бросятся. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
iteratorinsert_unique(const_iteratorhint,referencevalue);
```
>
Требуется: Значение должно быть значением l, а «наконечник» должен быть действительным итератором
: Пытается вставить x в контейнер, используя «наконечник» в качестве подсказки, где он будет вставлен.
Сложность: Логарифмический вообще, но это амортизированное постоянное время (два сравнения в худшем случае), если t вставлено непосредственно перед намёком.
Бросок: Если внутренние функции key_compare или priority_compare бросятся. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
template<typenameIterator>voidinsert_unique(Iteratorb,Iteratore);
```
>
Требуется: Ссылочный итератор должен давать значение l типа value_type.
Эффекты: Пытается вставить каждый элемент диапазона в контейнер.
Сложность: Диапазон вставки, как правило, O(N * log(N)), где N - размер диапазона. Однако он является линейным в N, если диапазон уже отсортирован по key_comp().
Бросок: Если внутренние функции key_compare или priority_compare бросятся. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
<
```
std::pair<iterator,bool>
insert_unique_check(constkey_type&key,insert_commit_data&commit_data);
```
>
Эффекты: Проверяет, можно ли вставить значение в контейнер, используя предоставленный пользователем ключ вместо самого значения.
Возвращение: Если существует эквивалентное значение, то пара, содержащая итератор, возвращается к уже существующей стоимости и ложна. Если значение может быть вставлено, возвращается истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Сложность: Средняя сложность в лучшем случае логарифмическая.
Броски: Если функции сравнения или предиката бросают. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при построении стоимостного типа: при наличии эквивалентного значения построенный объект должен быть отброшен. Часто часть узла, которая используется для наложения заказа, намного дешевле в конструировании, чем значение_тип, и эта функция предлагает возможность использовать эту часть для проверки того, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить значение_тип и использовать «insert_commit» для вставки объекта в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
"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 вставлено непосредственно перед намёком.
Бросает: Если функции сравнения или предиката бросают. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при построении стоимостного типа: при наличии эквивалентного значения построенный объект должен быть отброшен. Часто часть конструкции, которая используется для наложения заказа, намного дешевле в конструировании, чем значение_тип, и эта функция предлагает возможность использовать этот ключ, чтобы проверить, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить значение_тип и использовать «insert_commit» для вставки объекта в постоянное время. Это может придать полную сложность с постоянным временем для вставки: check(O(1)) + commit(O(1)).
"commit_data" остается в силе для последующего "insert_commit" только в том случае, если из контейнера больше не вставляются и не стираются объекты.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare,
        typenameKeyValuePrioCompare>
 std::pair<iteratorBOOST_INTRUSIVE_Ibool>
 insert_unique_check(constKeyType&key,KeyTypeKeyComparecomp,
                     KeyValuePrioComparekey_value_pcomp,
                     insert_commit_data&commit_data);
```
>
Требуется: Comp должен быть функцией сравнения, которая вызывает ту же строгую слабую упорядоченность, что и key_compare. Ключ_значение_pcomp должен быть функцией сравнения, которая вызывает ту же строгую слабую упорядоченность, что и приоритет_compare. Разница в том, что key_value_pcomp и comp сравнивают произвольный ключ с содержащимися значениями.
Эффекты: Проверяет, можно ли вставить значение в контейнер, используя предоставленный пользователем ключ вместо самого значения.
Возвращение: Если существует эквивалентное значение, то пара, содержащая итератор, возвращается к уже существующей стоимости и ложна. Если значение может быть вставлено, возвращается истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Сложность: Средняя сложность в лучшем случае логарифмическая.
Броски: Если функция упорядочивания comp или key_value_pcomp бросится. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при построении стоимостного типа: при наличии эквивалентного значения построенный объект должен быть отброшен. Часто часть узла, которая используется для наложения заказа, намного дешевле в конструировании, чем значение_тип, и эта функция предлагает возможность использовать эту часть для проверки того, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить значение_тип и использовать «insert_commit» для вставки объекта в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
"commit_data" остается в силе для последующего "insert_commit" только в том случае, если из контейнера не вставлено или стерто больше объектов.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare,
        typenameKeyValuePrioCompare>
 std::pair<iterator,bool>
 insert_unique_check(const_iteratorhint,constKeyType&key,
                     KeyTypeKeyComparecomp,
                     KeyValuePrioComparekey_value_pcomp,
                     insert_commit_data&commit_data);
```
>
Требуется: Comp должен быть функцией сравнения, которая вызывает ту же строгую слабую упорядоченность, что и key_compare. Ключ_значение_pcomp должен быть функцией сравнения, которая вызывает ту же строгую слабую упорядоченность, что и приоритет_compare. Разница в том, что key_value_pcomp и comp сравнивают произвольный ключ с содержащимися значениями.
Эффекты: Проверяет, может ли значение быть вставлено в контейнер, используя предоставленный пользователем ключ вместо самого значения, используя «подсказку» в качестве подсказки к тому, где оно будет вставлено.
Возвращение: Если существует эквивалентное значение, то пара, содержащая итератор, возвращается к уже существующей стоимости и ложна. Если значение может быть вставлено, возвращается истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Сложность: Логарифмическое вообще, но это амортизированное постоянное время, если t вставлено непосредственно перед намёком.
Бросает: Если функция упорядочивания comp или key_value_pcomp бросится. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при построении стоимостного типа: при наличии эквивалентного значения построенный объект должен быть отброшен. Часто часть конструкции, которая используется для наложения заказа, намного дешевле в конструировании, чем значение_тип, и эта функция предлагает возможность использовать этот ключ, чтобы проверить, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить значение_тип и использовать «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».
: Вставляет значение в<avl_set>, используя информацию, полученную из «commit_data», которую заполнил предыдущий «insert_check».
Возвращение: Итератор вновь вставленного объекта.
Сложность: Постоянное время.
Бросает: Ничего
Примечания: Эта функция имеет смысл только в том случае, если ранее была выполнена «insert_check» для заполнения «commit_data». Не следует вставлять или стирать значение между вызовами «insert_check» и «insert_commit».
<
```
iteratorinsert_before(const_iteratorpos,referencevalue);
```
>
Требуется: Значение должно быть значением l, "pos" должно быть действительным итератором (или концом) и должно быть датчиком значения после вставки в соответствии с предикатом
: Вставляет х в контейнер перед "по".
Сложность: Постоянное время.
Бросок: Если выполняется внутренняя функция priority_compare. Сильная гарантия.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если «pos» не является преемником инварианта упорядочивания контейнера «value», он будет нарушен. Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
<
```
voidpush_back(referencevalue);
```
>
Требуется: Значение должно быть lvalue, и оно должно быть не меньше, чем наибольший вставленный ключ
Эффекты: Вставьте x в контейнер в последнем положении.
Сложность: Постоянное время.
Броски: Если выполняется внутренняя функция priority_compare. Сильная гарантия.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если значение меньше наибольшего инварианта упорядочивания вставленного ключа, оно будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
<
```
voidpush_front(referencevalue);
```
>
Требуется: Значение должно быть lvalue, и оно должно быть не больше минимального вставленного ключа
Эффекты: Вставьте x в контейнер в первом положении.
Сложность:
Бросок: Если выполняется внутренняя функция priority_compare. Сильная гарантия.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если значение больше минимального инварианта вставленного ключевого контейнера будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
<
```
iteratorerase(const_iteratori);
```
>
Эффекты: Стирает элемент, на который указывает i.
Сложность: Средняя сложность для элемента стирания — постоянное время.
Бросает: если бросит внутренняя функция priority_compare. Сильная гарантия.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
iteratorerase(const_iteratorb,const_iteratore);
```
>
Эффекты: Уничтожает диапазон, указанный на b-конце e.
Сложность: Средняя сложность для диапазона стирания составляет максимум O(log(size() + N)), где N — число элементов в диапазоне.
Броски: если бросит внутренняя функция priority_compare. Сильная гарантия.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
size_typeerase(constkey_type&key);
```
>
Эффекты: Стирает все элементы с заданным значением.
Возврат: Число стертых элементов.
Сложность: O(log(size() + N.]
Бросает: если бросит внутренняя функция priority_compare. Сильная гарантия.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 size_typeerase(constKeyType&key,KeyTypeKeyComparecomp);
```
>
Эффекты: Стирает все элементы заданным ключом. согласно сравнительным функторам «комп.»
Возвращение: Число стертых элементов.
Сложность: O(log(size() + N).
Бросает: если бросит внутренняя функция приоритет_сравнение. Эквивалентная гарантияпри (beg!= end) стирании (beg++);
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
template<typenameDisposer>
 iteratorerase_and_dispose(const_iteratori,Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать.
: Стирает элемент, на который указывает i. Утилизатор::оператор()(указатель) вызывается для удаленного элемента.
Сложность: Средняя сложность для элемента стирания — постоянное время.
Бросает: если бросит внутренняя функция priority_compare. Сильная гарантия.
Примечание: Инвалидирует итераторы на стертые элементы.
<
```
template<typenameDisposer>
 iteratorerase_and_dispose(const_iteratorb,const_iteratore,
                            Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать.
Эффекты: Уничтожает диапазон, указанный на b-конце e. Утилизатор::оператор()(указатель) вызывается для удаленных элементов.
Сложность: Средняя сложность для диапазона стирания составляет максимум O(log(size() + N)), где N — число элементов в диапазоне.
Бросает: если бросит внутренняя функция priority_compare. Сильная гарантия.
Примечание: Инвалидирует итераторы на стертые элементы.
<
```
template<typenameDisposer>
 size_typeerase_and_dispose(constkey_type&key,Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать.
Эффекты: Стирает все элементы с заданным значением. Диспозитор::оператор()(указатель) вызывается для удаленных элементов.
Возвращение: Число стертых элементов.
Сложность: O(log(size() + N).
Бросает: если функция приоритета_сравнение бросает, то слабая гарантия и куча инвариантов нарушаются. Самое безопасное — очистить или уничтожить контейнер.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare,typenameDisposer>
 size_typeerase_and_dispose(constKeyType&key,KeyTypeKeyComparecomp,
                             Disposerdisposer);
```
>
Требует: Диспетчер::оператор()(указатель) не должен бросать.
: Стирает все элементы заданным ключом. по сравнению с функтором «комп». Диспозитор::оператор()(указатель) вызывается для удаленных элементов.
Возвращение: Число стертых элементов.
Сложность: O(log(size() + N).
Броски: если функция приоритета_сравнение бросает, то слабая гарантия и куча инвариантов нарушаются. Самое безопасное — очистить или уничтожить контейнер.
Примечание: Инвалидирует итераторы на стертые элементы.
<
```
voidclear();
```
>
Эффекты: Стирает все элементы.
Сложность: Линейный по количеству элементов на контейнере. Если это безопасный режим или авто-разъединить значение_тип. Постоянное время иначе.
Бросок: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
<
```
template<typenameDisposer>voidclear_and_dispose(Disposerdisposer);
```
>
Эффекты: Стирает все элементы, вызывающие диспергатор (p), для каждого узла, который должен быть удален.Сложность: Средняя сложность составляет максимум O(log(size() + N)), где N - количество элементов в контейнере.
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Звонки N раз для удаления функтора.
<
```
template<typenameT,class...Options2>
 voidmerge_unique(sgtree<T,Options2...>&);
```
>
Требуется: Варианты контейнера "источник" могут отличаться только функцией сравнения от *этого.
Эффекты: Попытки извлечь каждый элемент из источника и вставить его в объект сравнения *это. Если в элементе есть ключ, эквивалентный ключу элемента из источника, то этот элемент не извлекается из источника.
Посткондиционер: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в это, а не в источник.
Бросок: Ничего, если объект сравнения не бросит.
Сложность: N log(a.size() + N) (N имеет значение source.size())
<
```
while(it!=itend);
```
>
<
```
template<typenameT,class...Options2>
 voidmerge_equal(sgtree<T,Options2...>&);
```
>
Требуется: Варианты контейнера "источник" могут отличаться только функцией сравнения от *этого.
Эффекты: Извлекает каждый элемент в источнике и вставляет его в объект сравнения *это.
Посткондиция: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в это, а не в источник.
Бросок: Ничего, если объект сравнения не бросит.
Сложность: N log(a.size() + N) (N имеет значение source.size())
<
```
while(it!=itend);
```
>
<
```
template<typenameExtraChecker>voidcheck(ExtraCheckerextra_checker)const;
```
>
Эффекты: Утверждает целостность контейнера с дополнительными проверками, предоставляемыми пользователем.
Сложность: Линейное время.
Примечание: Метод может не иметь эффекта при отключении утверждений (например, с NDEBUG). Экспериментальная функция интерфейса может измениться в будущих версиях.
<
```
voidcheck()const;
```
>
Эффекты: Утверждает целостность контейнера.
Сложность: Линейное время.
Примечание: Метод не имеет эффекта, когда утверждения выключены (например, с NDEBUG). Экспериментальная функция интерфейса может измениться в будущих версиях.
<
```
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>бросок.
<
```
template<typenameKeyType,typenameKeyTypeKeyCompare>
 iteratorlower_bound(constKeyType&key,KeyTypeKeyComparecomp);
```
>
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше k или конца (), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если<key_compare>бросит
<
```
const_iteratorlower_bound(constkey_type&key)const;
```
>
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше 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 ключ_тип значения_тип вставлен в<*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 вставляется в<*this>.
Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Броски: Если бросит (1933)
<
```
std::pair<iterator,iterator>
bounded_range(constkey_type&lower_key,constkey_type&upper_key,
             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') должен быть ложным.
Эффекты: Возвращает пару со следующими критериями:
первый = нижний_bound(lower_key) если левый_замкнут, верхний_bound(lower_key) иначе
второй = верхний_bound(upper_key) если правый_замкнут, нижний_bound(upper_key) иначе
: Логарифмический.
Броски: Если<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, low_key), если левое_closed истинно, по отношению к !comp(lower_key, nk) иначе.
<upper_key>является значением, таким, что<*this>разделено относительно !comp(upper_key, nk), если право_closed истинно, в отношении comp(nk, upper_key) иначе.
<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(nk, lower_key), если левое_закрыто истинно, по отношению к !comp(lower_key, nk) в противном случае.
<upper_key>является значением, таким, что<*this>разделен по отношению к !comp(upper_key, nk), если право_закрыто истинно, по отношению к comp(nk, upper_key) в противном случае.
<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>бросает.
Примечание: Эта функция может быть более эффективной, чем вызов верхнего_bound и нижнего_bound для нижнего_key и верхнего_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. Контейнер не нужно перебалансировать.
Сложность: Постоянная.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты заказа контейнера, если с_это не эквивалентно *заменить_это в соответствии с правилами заказа. Эта функция быстрее, чем стирание и вставка узла, поскольку не требуется перебалансировки или сравнения.
<
```
voidremove_node(referencevalue);
```
>
Эффекты: удаляет «значение» из контейнера.
Броски: Ничего.
Сложность: Логарифмическое время.
Примечание: Эта статическая функция может использоваться только в непостоянных контейнерах с размером времени, которые имеют функторы сравнения без состояния.
Если пользователь называет эту функцию контейнером с постоянным размером времени или функтором сравнения состояния, будет выпущена ошибка компиляции.

`treap` public static functions

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

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

Class template treap

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

Boost C++ Libraries

Class template treap

Synopsis

Description

treap public construct/copy/destruct

treap public member functions

treap public static functions

`treap` public construct/copy/destruct

`treap` public member functions

`treap` public static functions