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

Class template rbtree

boost::intrusive::rbtree

Synopsis

// In header: <boost/intrusive/rbtree.hpp>
template<typename T, class... Options> 
class rbtree {
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        node_algorithms;       
  typedef implementation_defined::insert_commit_data     insert_commit_data;    
  // construct/copy/destruct
  rbtree();
  explicit rbtree(const key_compare &, const value_traits & = value_traits());
  template<typename Iterator> 
    rbtree(bool, Iterator, Iterator, const key_compare & = key_compare(), 
           const value_traits & = value_traits());
  rbtree(rbtree &&);
  rbtree & operator=(rbtree &&);
  ~rbtree();
  // 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(rbtree &);
  template<typename Cloner, typename Disposer> 
    void clone_from(const rbtree &, Cloner, Disposer);
  template<typename Cloner, typename Disposer> 
    void clone_from(rbtree &&, Cloner, Disposer);
  template<typename Cloner, typename Disposer> 
    void clone_from(rbtree &&, 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 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 &);
  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 &);
  iterator insert_unique_commit(reference, const insert_commit_data &);
  template<typename Iterator> void insert_unique(Iterator, Iterator);
  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);
  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);
  template<typename T, class... Options2> 
    void merge_unique(rbtree< T, Options2...> &);
  template<typename T, class... Options2> 
    void merge_equal(rbtree< T, Options2...> &);
  // public static functions
  static rbtree & container_from_end_iterator(iterator);
  static const rbtree & container_from_end_iterator(const_iterator);
  static rbtree & container_from_iterator(iterator);
  static const rbtree & 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;
};

Description

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

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

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

`rbtree` public construct/copy/destruct

```
rbtree;
```
: Построение пустого контейнера.
:Константа.
Броски: Если значение_черты::узел_черты::узел-конструктор бросает (это не происходит с предопределенными Boost.Intrusive крючками) или копи-конструктор ключевого_сравненного объекта бросает. Базовая гарантия.

explicit>key_compare,value_traitsvalue_traits;
: Эффекты
:Константа.
Броски :Броски конструктора узлов::node_traits::node.Intrusive крюки) или конструктор копий бросков объекта ключа_compare. Базовая гарантия.

templatetypename>rbtreebool unique,Iterator b, Iterator e, const &value_traits;2>

: Отклонение итератора должно давать значение типа value_type. cmp должна быть функцией сравнения, которая вызывает строгое слабое упорядочивание.

: Конструирует пустой контейнер и вставляет элементы из [b, e].

: Сложность: Линейность в N, если [b, e] уже отсортирована с использованием comp и в противном случае N * log N, где N - расстояние между первым и последним.

Броски: Если значение_черты::node_traits::node конструктор бросает (это не происходит с предопределенным Boost). Навязчивые крючки или конструктор/оператор() копий бросков объекта key_compare. Базовая гарантия.

rbtree(rbtree && x);
Последствия: доделать

rbtree &оператор=(rbtree && x);
: доделать

~rbtree();
Последствия: Отделяет все элементы от этого. Объекты в наборе не удаляются (т.е. не называются деструкторы), но узлы по параметру шаблона value_traits перезапускаются и, таким образом, могут быть повторно использованы.

Комплексность: Линейные элементы, содержащиеся в *это.

Броски: Ничего.

rbtree public member functions

iteratorbegin;
: Возвращает итератор, указывающий на начало контейнера.
Сложность: Константа.
Броски: Ничего.

const_iteratorbegin()const;
:Возвращает const_iterator, указывающий на начало контейнера.
:Константа.
Броски: Ничего.

const_iteratorcbegin()const;
: Возвращает const_iterator, указывающий на начало контейнера.
: Constant.
Броски: Ничего.

iteratorend;
: Возвращает итератор, указывающий на конец контейнера.
Сложность: Константа.
Броски: Ничего.

const_iteratorend()const;
: Возвращает const_iterator, указывающий на конец контейнера.
:Константа.
Броски: Ничего.

const_iteratorcend()const;
: Возвращает const_iterator, указывающий на конец контейнера.
: Constant.
Броски: Ничего.

reverse_iteratorrbegin;
: Возвращает обратный_iterator, указывающий на начало обратного контейнера.
Сложность: Константа.
Броски: Ничего.

const_reverse_iterator rbegin()const;
: Возвращает const_reverse_iterator, указывающий на начало обратного контейнера.

: Constant.
Броски: Ничего.

const_reverse_iteratorcrbegin()const;
: Возвращает const_reverse_iterator, указывающий на начало обратного контейнера.
: Constant.
Броски: Ничего.

reverse_iteratorrend;
: Возвращает обратный_iterator, указывающий на конец обратного контейнера.
Сложность: Константа.
Броски: Ничего.

const_reverse_iteratorrend()const;
: Возвращает const_reverse_iterator, указывающий на конец обратного контейнера.
: Constant.
Броски: Ничего.

const_reverse_iteratorcrend()const;
: Возвращает конст_reverse_iterator, указывающий на конец обратного контейнера.
: Constant.
Броски: Ничего.

iteratorroot;
: Возвращает итератор, указывающий на корневой узел контейнера или конец(), если он не присутствует.
: Сложность: Константа.
Броски: Ничего.

const_iteratorrootconst;
: Возвращает конст_iterator, указывающий на корневой узел контейнера или кенд(), если его нет.
: Constant.
Броски: Ничего.
const_iterator crootconst;
: Возвращает конст_iterator, указывающий на корневой узел контейнера или кенд(), если его нет.
: Constant.
Броски: Ничего.

key_comparekey_comp()const;
:Возвращает ключ_compare объект, используемый контейнером.
:Константа.
Броски: Если бросит key_compare копи-конструктор.

value_comparevalue_comp()const;
: Возвращает значение_compare объект, используемый контейнером.
: Constant.
Броски: Если value_compare копи-конструктор бросает.

boolempty()const;
: Эффекты: Возвращается верно, если контейнер пуст.
:Константа.
Броски: Ничего.

size_typesizeconst;
: Возвращает количество элементов, хранящихся в контейнере.
: Сложность: Линейность к элементам, содержащимся в *это, если опция постоянного размера отключена. Постоянное время иначе.
Броски: Ничего.

voidswap(rbtree& other;
: Эффекты: Изменить содержимое двух контейнеров.
:Константа.
Броски: Если сравнительный своп функтора бросает вызов.

templatetypename Cloner, typename Disposer> voidclone_from(const rbtree , Cloner disposer);
: Disposer::operator()(pointer) не должен бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.

Последствия: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src вызывающего Клонера::оператор()(const_reference) и вставляет их на *это. Копии предиката из исходного контейнера.

Если клонер бросает, все клонированные элементы несвязаны и расположены, вызывая Диспозитор::оператор()(указатель).

Сложность: Линейный стертый плюс вставленные элементы.

Броски: Если клонер бросает или предикат копирования, задание бросает. Базовая гарантия.

templatetypename Cloner,typename Disposer> void clone_from(rbtree && src, Cloner disposer;;
: Disposer::operator()(pointer) не следует бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.

Эффекты: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src вызывающего Клонера::оператор()(ссылка) и вставляет их на *это. Копии предиката из исходного контейнера.

Если клонированный элемент бросает, все клонированные элементы являются несвязанными и расположены, вызывая Disposer::operator()(pointer).

Комплексность: Линейный стертый плюс вставленные элементы.

Броски: Если клонер бросает или предикат копирует присвоение бросков. Основная гарантия.

Примечание : Данная версия может модифицировать исходный контейнер, полезный для реализации семантики перемещения.

templatetypename Cloner,typename Disposer> voidclone_from(rbtree && src, Cloner disposer;;
: Disposer::operator()(pointer) не следует бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.

Эффекты: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src вызывающего Клонера::оператор()(ссылка) и вставляет их на *это. Копии предиката из исходного контейнера.

Если клонированный элемент бросает, все клонированные элементы являются несвязанными и расположены, вызывая Disposer::operator()(pointer).

Комплексность: Линейный стертый плюс вставленные элементы.

Броски: Если клонер бросает или предикат копирует присвоение бросков. Основная гарантия.

Примечание : Данная версия может модифицировать исходный контейнер, полезный для реализации семантики перемещения.

iteratorinert_equal(ссылка значение;
Требуется : значение должно быть lvalue
: Ввод значения в контейнер перед верхней границей.
Средняя сложность для вставочного элемента является наиболее логарифмической.
Броски: Если выполняется внутренняя функция key_compare ordering. Сильная гарантия.
Примечание: Не влияет на действительность итераторов и ссылок. Копировальными конструкторами не называются.

iteratorinsert_equal(const_iterator,ссылка значение;
: Значение должно быть lvalue, а "hint" должен быть действительным итератором.
Последствия: Вставьте x в контейнер, используя "hint" как подсказку, куда он будет вставлен. Если «подсказка» является верхним_связанным, вставка занимает постоянное время (два сравнения в худшем случае)

Сложность: Логарифмическая в целом, но это амортизированное постоянное время, если t вставлен непосредственно перед подсказкой.

Броски: Если внутренняя клавиша_сравните функцию упорядочивания бросает. Сильная гарантия.

Примечание : Не влияет на действительность итераторов и ссылок. Копировальными конструкторами не называются.

templatetypenameIterator> voidinsert_equal,Iterator e;
: Требуется, чтобы итератор с отсылкой к типу значения_type.
: Вставляет каждый элемент диапазона в контейнер перед верхней границей ключа каждого элемента.
: Вставьте диапазон в общем O(N* log(N)), где N - размер диапазона. Однако он является линейным в N, если диапазон уже отсортирован по значению_comp().
Броски: Ничего.
Примечание: Не влияет на валидность итераторов и ссылок. Копировальными конструкторами не называются.

std::iterator, boolinert_unique(ссылка значение ;
: Значение должно быть lvalue

: Эффекты Средняя сложность для вставки элемента является наиболее логарифмической.
: Ничего.
Примечание: Не влияет на валидность итераторов и ссылок. Копировальными конструкторами не называются.

iteratorinert_unique(const_iterator,referencevalue;
: Значение должно быть lvalue, а "hint" должен быть действительным итератором
: Пытается вставить x в контейнер, используя "hint" в качестве подсказки к тому, где он будет вставлен.
: Сложность: Логарифмическая в целом, если t вставлено непосредственно перед подсказкой.
: Ничто.
Примечание: Не влияет на валидность итераторов и ссылок. Копировальными конструкторами не называются.

template<typename KeyType, typename KeyTypeKeyCompare> pair< iterator, bool > const const & KeyTypeKeyCompare, insert_commit_data &&;
: Comp должен быть функцией сравнения, которая вызывает такой же строгий слабый порядок, как и key_compare. Разница заключается в том, что комп сравнивает произвольный ключ с содержащимися значениями.

Последствия: Проверяет, можно ли вставить значение в контейнер, используя предоставленный пользователем ключ вместо самого значения.

Возврат : При наличии эквивалентного значения возвращает пару, содержащую итератор, к уже имеющемуся значению и ложному. Если значение может быть вставлено, возвращает истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».

Комплексность: Средняя сложность является наиболее логарифмической.

Броски: Если функция упорядочивания бросает. Сильная гарантия.

Примечания: Эта функция используется для повышения производительности при строительстве значения_типа дорого: при наличии эквивалентного значения построенный объект должен быть отброшен. Много раз, часть узла, которая используется, чтобы наложить заказ, намного дешевле построить, чем значение_тип, и эта функция предлагает возможность использовать эту часть, чтобы проверить, будет ли вставка успешной.

Если проверка успешна, пользователь может построить значение_тип и использовать «вставить_коммит» для вставки объекта в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).

"commit_data" остается действительным для последующего "insert_commit" только в том случае, если больше объектов не вставлено или стерто из контейнера.

template<typename KeyType, typename KeyTypeKeyCompare> pair< , bool > insert_unique_check (const_iterator подсказка, const & KeyTypeKeyCompare, insert_commit_data &&;
: Comp должен быть функцией сравнения, которая вызывает такую же строгую слабую упорядоченность, как и key_compare. Разница заключается в том, что комп сравнивает произвольный ключ с содержащимися значениями.
Эффекты: Проверяет, можно ли вставить значение в контейнер, используя предоставленный пользователем ключ вместо самого значения, используя «наконечник» в качестве подсказки к тому, где оно будет вставлено.
Возврат : Если есть эквивалентное значение возвращает пару, содержащую итератор, к уже существующему значению и ложному. Если значение может быть вставлено, возвращает истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».
Комплексность: Логарифмическое в целом, но это амортизированное постоянное время, если t вставлено непосредственно перед подсказкой.
Броски: Если функция упорядочивания бросает. Сильная гарантия.
Примечания: Эта функция используется для повышения производительности при строительстве значения_типа дорого: при наличии эквивалентного значения построенный объект должен быть отброшен. Много раз, часть конструкции, которая используется для наложения заказа, намного дешевле, чем значение_тип, и эта функция предлагает возможность использовать этот ключ, чтобы проверить, будет ли вставка успешной.

Если проверка будет успешной, пользователь может построить значение_тип и использовать «вставить_коммит» для вставки объекта в постоянное время. Это может придать вставке полную сложность с постоянным временем: check(O(1)) + commit(O(1)).

"commit_data" остается действительным для последующего "insert_commit" только в том случае, если из контейнера не вставлено или стерто больше объектов.

std::iterator, bool > inert_unique_checkkey_type & insert_commit_data & commit_data;;
: Проверка, может ли значение быть вставлено в контейнер, с использованием предоставленного пользователем ключа вместо самого значения.

Возврат пары, содержащей итератор, к уже имеющемуся значению и ложному. Если значение может быть вставлено, возвращает истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».

Комплексность: Средняя сложность является наиболее логарифмической.

Броски: Если функция упорядочивания бросает. Сильная гарантия.

std::iterator, bool inert_unique_check(const_type &&insert_commit_data; commit_data;
Возвращает пару, содержащую итератор, к уже имеющемуся значению и ложному.

Возвращает пару, содержащую итератор, к уже имеющемуся значению и ложному. Если значение может быть вставлено, возвращает истинное значение в возвращенной паре boolean и заполняет «commit_data», которое предназначено для использования с функцией «insert_commit».

Комплексность: Логарифмическое в целом, но это амортизированное постоянное время, если t вставлено непосредственно перед подсказкой.

Броски: Если функция упорядочивания бросает. Сильная гарантия.

iteratorinsert_unique_commit(referencevalue, const insert_commit_data & commit_data);
: значение должно быть lvalue of type value_type. commit_data должны быть получены из предыдущего вызова на «insert_check». Никакие объекты не должны были вставляться или стираться из контейнера между «insert_check», который заполнил «commit_data» и вызовом «insert_commit».

: Вставляется значение в контейнере с использованием информации, полученной из «commit_check», которую заполнил предыдущий «insert_check».

Сложность: Постоянное время.

: Ничто.

Примечания: Эта функция имеет смысл только в том случае, если ранее была выполнена «insert_check» для заполнения «commit_data». Не следует вставлять или стирать значение между вызовами «insert_check» и «insert_commit».

templatetypenameIterator>voidInsert_unique(Iterator e);
: Требуется, чтобы итератор с отсылкой на тип значения_type.
: Пытается вставить каждый элемент диапазона в контейнер.
: Вставьте диапазон в общем O(N* log(N)), где N - размер диапазона. Однако он является линейным в N, если диапазон уже отсортирован по значению_comp().
Броски: Ничего.
Примечание: Не влияет на валидность итераторов и ссылок. Копировальными конструкторами не называются.

iteratorinert_beforeconst_iterator pos,referencevalue;
: Значение должно быть lvalue, "pos" должен быть действительным итератором (или концом) и должен быть сукцессатором значения после вставки в соответствии с предикатом
: Сложность: Постоянное время.
: Ничто.
Примечание: Если "pos" не является преемником инварианта упорядочивания контейнера "value" будет нарушено. Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.

voidpush_back(ссылказначение;
: Значение должно быть lvalue, и оно должно быть не меньше наибольшего вставленного ключа
: Эффекты
Комплексность: Постоянное время.
:Ничего.
Примечание: Если значение меньше наибольшего вставленного инварианта упорядочивания ключа будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.

voidpush_front(ссылка значение;
: Значение должно быть lvalue, и оно должно быть не больше минимального вставленного ключа
: Эффекты: Вставка x в контейнер в первом положении.
: Постоянное время.
: Ничего.
Примечание: Если значение больше минимального вставленного инварианта упорядочивания ключа будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
iterator erase(const_iterator i;
: Стирает элемент, на который указывает i.
: Средняя сложность для элемента стирания является постоянным временем.
:Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.

iterator eraseconst_iterator b,const_iterator e;
: Стирает диапазон, указанный на конце b.
: Средняя сложность для диапазона стирания составляет самое большее O(log(size()+N)), где N - число элементов в диапазоне.
: Ничто.
: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.

size_type erasekey_typeключ
: Стирает все элементы с заданным значением.
: Количество стертых элементов.
: O(log(size() + N)
: Ничего.
: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.

template<typename KeyType, typename KeyTypeKeyCompare> size_typeerase & KeyTypeKeyCompare;
: Требуется : ключ такой, что *это означает !comp(ключ, nk), с nk ключом (ключ, nk), с nk ключом_типом значения_типа, вставленным в .
: Стирает все элементы с заданным ключом. Согласно сравнительным функторам "комп".

: Количество стертых элементов.

Сложность: O(log(size() + N).

Броски: Ничего.

Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.

templatetypename>erase_and_dispose,const_iterator i,
: Disposer::оператор(): Стирает элемент, на который указывает i. Disposer::оператор(): Средняя сложность для стираемого элемента составляет постоянное время.
: Ничто.
: Инвалидирует итераторы в стертые элементы.

templatetypenameerase_and_dispose,const_iterator e,const_iterator e,
: Требуется : Диспозитор::оператор() : Эффекты : Диспозитор::оператор(): Средняя сложность для диапазона стирания составляет максимум O(log(size()+34), где N - число элементов в диапазоне.

:Note: Инвалидирует итераторы в стертые элементы.

templatetypename Disposer> size_typeerase_and_disposekey_type & Key, Disposer disposer;
: Disposer::operator()(pointer):37>
: Стирает все элементы с заданным значением. Диспетчер::оператор()(указатель) вызывается для удаленных элементов.

: Количество стертых элементов.

: O(log(size() + N).

Броски: Ничего.

Примечание: Недействительность итераторов (но не ссылок) на стертые элементы. Деструкторы не называются.

template KeyType, typename KeyTypeKeyCompare,erase_и_disposeKeyTypeKeyCompare,KeyTypeKeyComparecompare,Disposer disposer,
Ключ, обозначающий !comp(ключ, nk) и !comp(ключ, nk) с указанием !comp(ключ, nk) и nk ключ_тип значения_типа, вставленный в this.
Эффекты: Стирает все элементы с заданным ключом. по сравнению с функтором «комп». Диспозитор::оператор()(указатель) вызывается для удаленных элементов.

: Количество стертых элементов.

: O(log(size() + N)

: Броски: Ничего.

Примечание: Инвалидирует итераторы на стертые элементы.

voidclear;
: Эффекты: Стирает все элементы.
Комплексность: Линейное количество элементов на контейнере. Если это безопасный режим или авто-разъединить значение_тип. Постоянное время в противном случае.

Броски: Ничего.

Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.

templatetypename Disposer> voidclear_and_dispose( disposer);
Эффекты: Уничтожает все элементы, вызывающие disposer(p) для каждого узла, который должен быть удален. Комплексность: Средняя сложность для максимум O(log(size() + N)), где N - количество элементов в контейнере.

Броски: Ничего.

Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Звонки N раз для удаления функтора.

size_type count(key_type;const;
: Возвращает число содержащихся элементов с заданным значением
: Логарифмическая к числу содержащихся элементов плюс линейная к числу объектов с заданным значением.
Броски: Если key_compare бросает.

template<typename KeyType, typename KeyTypeKeyCompare>Счет&Ключ,Конст;
Ключ Ключ с комп(nk, ключ) и !comp(комп, ключ), подразумевающий !comp(ключ, ключ) и nk ключ_тип значения_типа, вставленный в >это.
:Логарифмический к числу элементов, содержащихся плюс линейный к числу объектов с данным ключом.
Броски : Если комп бросает.
iterator lower_bound(constkey_type;;
: Возвращает итератор к первому элементу, ключ которого не меньше k или конца() если этот элемент не существует.
: Logarithmic.
Броски: Если key_compare бросает.

template<typename KeyType, typename KeyTypeKeyCompare> iterator lower_bound( &KeyTypeKeyCompare);
Возвращает итератор к первому элементу, ключ которого не меньше k или конца() если этот элемент не существует.

: Logarithmic.

Броски: Если key_compare бросает.
const_iterator lower_bound(key_type &const;
Возвращает итератор к первому элементу, ключ которого не меньше k или конца() если этот элемент не существует.
: Logarithmic.
Броски: Если key_compare бросает.

template<typename KeyType, typename KeyTypeKeyCompare> const_iteratorlower_bound(const ,KeyTypeKeyComparecompare)const;
: Возвращает итератор к первому элементу, ключ которого не меньше k или конца() если этот элемент не существует.

: Logarithmic.

Броски: Если key_compare бросает.

iterator upper_bound(constkey_type;;
: Возвращает итератор к первому элементу, чей ключ больше k или конца() если этот элемент не существует.
: Logarithmic.
Броски: Если key_compare бросает.

template<typename KeyType, typename KeyTypeKeyCompare> iterator upper_boundconst &,KeyTypeKeyCompare;
Требуется : ключ такой, что *это вставляется в *это.
Комплексность:Броски: Если comp бросает.
const_iterator upper_bound(key_type &const;
: Возвращает итератор к первому элементу, чей ключ больше k или конца() если этот элемент не существует.
: Logarithmic.
Броски: Если key_compare бросает.

template<typename KeyType, typename KeyTypeKeyCompare>constconst &,constcompare;
: Ключ является таким значением, что *это вставляется в *это.
Комплексность:Броски: Если comp бросает.
iterator find(const key_type & key);
Effects: Найден итератор к первому элементу, ключ которого k или конец(), если этот элемент не существует.

Сложность: Логарифмический.

Броски: Если key_compare бросает.

template<typename KeyType, typename KeyTypeKeyCompare>iteratorconst &,;
Требуется : ключ таков, что *это означает !comp(ключ, nk), а nk - ключ_тип значения_типа, вставленный в .
КомплексностьБроски: Если комп бросает.

const_iteratorfindconst &const;
ПоследствияПолучает итератор к первому элементу, ключ которого k или конец() если этот элемент не существует.
:Логарифмический.
Броски:Если key_compare бросает.

template<typename KeyType, typename KeyTypeKeyCompare> const & , const;const;
: Ключ является таким значением, что *это означает !comp(ключ, nk), а nk - ключ_тип значения_типа, вставленный в .

Комплексность: Броски : Если comp бросает.

std:: iterator, iterator > equal_range(const key_type &;
: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, где эти элементы были бы, если у них нет элементов с ключом k.

Сложность : Логарифмический.

Броски : Если key_compare бросает.

template<typename KeyType, typename KeyTypeKeyCompare>std,iteratorEqual_rangeconst &,KeyTypeKeyCompare,;
: Ключ является таким значением, что *это означает !comp(ключ, nk), с !comp(ключ, nk), с !comp(ключ, nk), с !comp(ключ, nk), с !comp(ключ, nk), с !comp(ключ, nk), с !comp(ключ, nk), с nk ключ_тип значения_тип вставлен в Влияние : Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, где эти элементы были бы, если у них нет элементов с ключом k.
Сложность : Логарифмический. Броски : Если комп бросает.
std::const_iterator, const_iterator equal_rangekey_type &const;const;; Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k. : Logarithmic. : Броски: Если key_compare бросает.
template<typename KeyType, typename KeyTypeKeyCompare> , const_iterator (&KeyTypeKeyCompare,const;const;
:Ключ :Ключ означает !comp(ключ, nk), с !comp(ключ, nk), с nk ключом_типа значения_типа, вставленного в .
Комплексность :Если comp бросает.

std::iterator bounded_rangebounded_range&key_type & top_key left_closed, bool right_closed;: lower_key должен быть ложным>59>
Если lower_key эквивалентен upper_key &&!key_comp()(lower_key, upper_key)], то ('left_closed' | |right_closed').

: Возвращает пару со следующими критериями:

first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) else

second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) if right_closed, lower_bound(upper_key) if right_50>: Logarithmic.

Броски: Если key_compareброски.

ПримечаниеПримечаниеПримечание: Экспериментальная функция интерфейса может измениться в будущих выпусках.

template<typename KeyType, typename KeyTypeKeyCompare>pair,bounded_range, lower_key, top_key, left_closed, boolleft_closed, boolleft_closed,: lower_key является значением, таким, что upper_key, nk>, если правый_closed верен, по отношению к !comp(nk, upper_key, nk) если правый_closed верен, по отношению к !comp(nk, upper_key, nk) если правый_closed верен, по отношению к !comp(nk, upper_key, nk : Возвращает пару со следующими критериями: first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) в противном случае Сложность: Logarithmic. : Если comp бросает. NoteNote: Экспериментальная функция интерфейса может измениться в будущих выпусках.
std::const_iterator, bounded_rangebounded_range lower_key, lower_key & top_key left_closed, bool right_closed; const: lower_key должен быть ложным>61> Если lower_key эквивалентен upper_key &&!key_comp() : Возвращает пару со следующими критериями: first = low_bound(lower_key) if left_closed, upper_bound(lower_key) else second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) if right_closed, lower_bound(upper_key) if right_52>: Logarithmic. Броски: Если key_compareброски. Примечание: Эта функция может быть более эффективной, чем вызов upper_bound и lower_bound для low_value и upper_value. : Экспериментальная функция, интерфейс может измениться в будущих выпусках. template<typename KeyType, typename KeyTypeKeyCompare>pair,bounded_range, low_key, top_key, left_closed, bool left_closed, bool right_closed, const: lower_key является таким значением, что upper_key, nk>, если правый_closed верен, по отношению к !comp(upper_key, upper_key) истинно, по отношению к !comp(nk, upper_key, nk) истинно, по отношению к !comp(nk, upper_key не предшествует lower_key по : Возвращает пару со следующими критериями: first = low_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) if else : Logarithmic. Brows: If comp throws. Note: Эта функция может быть более эффективной, чем вызов upper_bound и lower_bound для low_key и upper_key. Note: Экспериментальная функция интерфейса может измениться в будущих выпусках. iterator iterator_to(ссылказначение); Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено. Последствия: Возврат: действительный итератор i, принадлежащий набору, который указывает на значение Сложность:Константа. Броски: Ничего. const_iteratoriterator_to(const_referencevalue)const; : Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено. Последствия: Возврат: действительный const_iterator i, принадлежащий набору, который указывает на значение Комплексность: Константа. Броски: Ничего. pointerunlink_leftmost_without_rebalance; : Отключает левый узел от контейнера. : Средняя сложность составляет постоянное время. : Ничего. Примечания: Эта функция разбивает контейнер и контейнер можно использовать только для большего количества вызовов unlink_leftmost_without_rebalance. Эта функция обычно используется для достижения поэтапного контролируемого разрушения контейнера. voidreplace_node(iterator replace_this, reference with_this;:Requires: replace_this должен быть действительным итератором *this и с_this не должен быть вставлен ни в один контейнер.: Заменить_this в его положении в контейнере с_this. Контейнер не нуждается в перебалансировке. : Constant. Броски: Ничего. Примечание: Эта функция будет нарушать инварианты упорядочивания контейнера, если с_это не эквивалентно *заменить_это в соответствии с правилами упорядочивания. Эта функция быстрее, чем стирание и вставка узла, поскольку не требуется перебалансировки или сравнения. voidremove_node; : удаляет "значение" из контейнера. : Ничего.: Сложность: Логарифмическое время. Примечание: Если пользователь называет эту функцию контейнером с постоянным размером времени или константным сравнительным функтором, будет выпущена ошибка компиляции. templatetypename T,class... Options2merge_unique<T...>&Попытки извлечь каждый элемент из источника и вставить его в объект сравнения *это. Если в ключе есть элемент, эквивалентный ключу элемента из источника, то этот элемент не извлекается из источника. Посткондиция: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам * этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в * это, а не в источник. Броски : Ничего, если объект сравнения не бросает. Сложность : N log(a.size() + N) (N имеет значение source.size()) templatetypenameclass... Options2merge_equal,T...>>>; : Извлекает каждый элемент в источнике и вставляет его в объект сравнения *это. Последние элементы источника относятся к тем же элементам, но как к членам *это. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в * это, а не в источник. Броски : Ничего, если объект сравнения не бросает. Сложность : N log(a.size() + N) (N имеет значение source.size())
rbtree public static functions static rbtree container_from_end_iterator; : end_iterator должен быть действительным конечным итератором контейнера. : Возвращает конст-ссылку на контейнер, ассоциированный с конечным итератором : Ничто. Комплексность: Константа. static const rbtree (const_iterator end_iterator) :Предусловие : end_iterator должен быть действительным конечным итератором контейнера.Броски: Ничего. Комплексность:Константа. static rbtree container_from_iterator; Предпосылка Возвращает обратную ссылку на контейнер, связанный с итератором :2>:Ничего. Комплексность: Логарифмический. статическийrbtreeот_iterator(const_iterator it) ПредпосылкаПоследствия:Возвращает обратную ссылку на контейнер, связанный с итератором :Ничего. Комплексность: Логарифмическое. static iterators_iterator_to(ссылказначение); Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено. : Возврат: действительный итератор i, принадлежащий набору, который указывает на значение Сложность: Константа. Броски: Ничего. Примечание: Эта статическая функция доступна только в том случае, если свойства не имеют состояния. static const_iterators_iterator_to(const_referencevalue); Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено. : Возврат: действительный итератор i, принадлежащий набору, который указывает на значение Сложность: Константа. Броски: Ничего. Примечание: Эта статическая функция доступна только в том случае, если свойства не имеют состояния. static void(ссылка значение; : Значение не должно быть в контейнере. : init_node ставит крюк значения в известное состояние по умолчанию. : Ничто. : Постоянное время.Примечание: Эта функция ставит крючок в известное состояние по умолчанию, используемое авто_unlink и безопасными крючками.

Class template rbtree

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

Boost C++ Libraries

Class template rbtree

Synopsis

Description

`rbtree` public construct/copy/destruct

`rbtree` public member functions

`rbtree` public static functions

Class template rbtree

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

Boost C++ Libraries

Class template rbtree

Synopsis

Description

rbtree public construct/copy/destruct

rbtree public member functions

rbtree public static functions

`rbtree` public construct/copy/destruct

`rbtree` public member functions

`rbtree` public static functions