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

Class template sg_multiset

boost::intrusive::sg_multiset

Synopsis

// In header: <boost/intrusive/sg_set.hpp>
template<typename T, class... Options> 
class sg_multiset {
public:
  // types
  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::value_traits           value_traits;          
  typedef implementation_defined::pointer                pointer;               
  typedef implementation_defined::const_pointer          const_pointer;         
  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::insert_commit_data     insert_commit_data;    
  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;       
  // construct/copy/destruct
  sg_multiset();
  explicit sg_multiset(const key_compare &, 
                       const value_traits & = value_traits());
  template<typename Iterator> 
    sg_multiset(Iterator, Iterator, const key_compare & = key_compare(), 
                const value_traits & = value_traits());
  sg_multiset(sg_multiset &&);
  sg_multiset & operator=(sg_multiset &&);
  ~sg_multiset();
  // 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(sg_multiset &);
  template<typename Cloner, typename Disposer> 
    void clone_from(const sg_multiset &, Cloner, Disposer);
  template<typename Cloner, typename Disposer> 
    void clone_from(sg_multiset &&, Cloner, Disposer);
  iterator insert(reference);
  iterator insert(const_iterator, reference);
  template<typename Iterator> void insert(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);
  void rebalance();
  iterator rebalance_subtree(iterator);
  float balance_factor() const;
  void balance_factor(float);
  template<class... Options2> void merge(sg_multiset< T, Options2...> &);
  template<class... Options2> void merge(sg_set< T, Options2...> &);
  // public static functions
  static sg_multiset & container_from_end_iterator(iterator);
  static const sg_multiset & container_from_end_iterator(const_iterator);
  static sg_multiset & container_from_iterator(iterator);
  static const sg_multiset & 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

Шаблон классаsg_multisetявляется навязчивым контейнером, который имитирует большую часть интерфейса std::sg_multiset, как описано в стандарте C++.

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

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

`sg_multiset` public construct/copy/destruct

```
sg_multiset;
```
Эффекты: Конструирует пустой контейнер.
Сложность: Постоянная.
Бросает: Если value_traits::node_traits::node constructor throws (это не происходит с заранее заданными Boost.Intrusive крючками) или копи-конструктор key_compare object throws. Базовая гарантия.
```
эксплицитноsg_multisetconstkey_compare&cmp,constvalue_traits&v_traits=value_traits];
```
Эффекты: Постраивает пустой контейнер с заданными сравнениями и чертами.
Сложность: Постоянная.
Бросок: Если value_traits::node_traits::node constructor throws (это не происходит с заранее заданными Boost.Intrusive крючками) или копи-конструктор key_compare object throws. Базовая гарантия.
```
шаблон<итератор>итераторитератор,итераторe,const&cmp=ключ_compareключ_comparev_traits=значение_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. Базовая гарантия.
```
sg_multisetsg_multiset&&x];
```
:-do

sg_multiset&оператор=sg_multiset&&x];

:-do

```
~sg_multiset;
```
: Отделяет от этого все элементы. Объекты в наборе не удаляются (т.е. не называются деструкторы), но узлы в соответствии с параметром шаблоназначение_чертыперезапускаются и, таким образом, могут быть повторно использованы.
Сложность: Линейные к элементам, содержащимся в *это.
Броски: Ничего.

`sg_multiset` public member functions

```
итераторначинают;
```
: Возвращает итератор, указывающий на начало контейнера.
Сложность: Постоянная.
Бросает: Ничего.
```
const_iteratorначинаютконст;
```
Эффекты: Возвращает const_iterator, указывающий на начало контейнера.
Сложность: Постоянная.
Бросает: Ничего.
```
const_iteratorcbeginconst;
```
: Возвращает const_iterator, указывающий на начало контейнера.
Сложность: Постоянная.
Броски: Ничего.
```
итераторконец;
```
эффекты: Возвращает итератор, указывающий на конец контейнера.
Сложность: Постоянная.
Броски: Ничего.
```
const_iteratorendconst;
```
Эффекты: Возвращает const_iterator, указывающий на конец контейнера.
Сложность: Постоянная.
Бросает: Ничего.
```
const_iteratorcendconst;
```
Эффекты: Возвращает const_iterator, указывающий на конец контейнера.
Сложность: Постоянная.
Броски: Ничего.
```
reverse_iteratorrbegin;
```
: Возвращает обратный_iterator, указывающий на начало обратного контейнера.
Сложность: Постоянная.
Бросает: Ничего.
```
const_reverse_iteratorrbeginconst;
```
Эффекты: Возвращает const_reverse_iterator, указывающий на начало обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
```
const_reverse_iteratorcrbeginconst;
```
Эффекты: Возвращает const_reverse_iterator, указывающий на начало обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
```
reverse_iteratorrend;
```
: Возвращает обратный_iterator, указывающий на конец обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
```
const_reverse_iteratorrendconst;
```
Эффекты: Возвращает const_reverse_iterator, указывающий на конец обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
```
const_reverse_iteratorcrendconst;
```
: Возвращает const_reverse_iterator, указывающий на конец обратного контейнера.
Сложность: Постоянная.
Броски: Ничего.
```
итераторкорень;
```
эффекты: Возвращает итератор, указывающий на корневой узел контейнера или конец(), если он не присутствует.
Сложность: Постоянная.
Броски: Ничего.
```
const_iteratorrootconst;
```
Эффекты: Возвращает const_iterator, указывающий на корневой узел контейнера или кенд(), если он отсутствует.
Сложность: Постоянная.
Броски: Ничего.
```
const_iteratorcrootconst;
```
Эффекты: Возвращает const_iterator, указывающий на корневой узел контейнера или кенд(), если он отсутствует.
Сложность: Постоянная.
Броски: Ничего.
```
key_comparekey_compconst;
```
Эффекты: Возвращает объект key_compare, используемый контейнером.
Сложность: Постоянная.
Броски: Если бросит key_compare копи-конструктор.
```
value_comparevalue_compconst;
```
Эффекты: Возвращает объект value_compare, используемый контейнером.
Сложность: Константа.
Броски: Если value_compare копи-конструктор бросает.
```
boolemptyconst;
```
Эффекты: Возвращается, если контейнер пуст.
Сложность: Постоянная.
Броски: Ничего.
```
size_typesizeconst;
```
Эффекты: Возвращает количество элементов, хранящихся в контейнере.
Сложность: Линейный к элементам, содержащимся в *это, если опция постоянного размера отключена. Постоянное время иначе.
Бросает: Ничего.
```
voidswapsg_multiset&other;
```
Эффекты: Изменяет содержимое двух контейнеров.
Сложность: Постоянная.
Бросает: Если сравнительный своп функтора бросает вызов.
```
шаблон<имя типа,имя типа>voidклонconstsg_multiset&src,клонерклонер;
```
Требует: Диспетчер::оператор()(указатель) не должен бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.
Эффекты: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src, вызывающего Клонера::оператор()(const_reference) и вставляет их на *это. Копирует предикат из исходного контейнера.
Если клонер бросает, все клонированные элементы несвязаны и расположены, вызывая Диспозитор::оператор()(указатель).
Сложность: Линейный стертый плюс вставленные элементы.
Бросок: Если клонер бросает или предикат копирования, задание бросает. Базовая гарантия. Дополнительные примечания: он также копирует альфа-фактор из исходного контейнера.
```
шаблон<имя типаклонvoidклон_отsg_multiset&&src,Клонерклонер,;
```
Требует: Диспетчер::оператор()(указатель) не должен бросать. Клонер должен уступить узлам, эквивалентным исходным узлам.
Эффекты: Стирает все элементы из *этого вызывающего Диспозитора::оператор()(указатель), клонирует все элементы из src, вызывающего Клонера::оператор()(ссылка) и вставляет их на *это. Копирует предикат из исходного контейнера.
Если клонер бросает, все клонированные элементы несвязаны и расположены, вызывая Диспозитор::оператор()(указатель).
Сложность: Линейный стертый плюс вставленные элементы.
Бросок: Если клонер бросает или предикат копирования, задание бросает. Основная гарантия.
Примечание: Эта версия может модифицировать исходный контейнер, полезный для реализации семантики перемещения. Дополнительные примечания: он также копирует альфа-фактор из исходного контейнера.
```
итераторвставкаэталонноезначение;
```
Требует: значение должно быть lvalue
Эффекты: Вставляет значение в контейнер перед верхней границей.
Сложность: Средняя сложность для вставочного элемента является наиболее логарифмической.
Броски: Если выполняется внутренняя функция key_compare ordering. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
```
итераторвставкаconst_iteratorподсказка,ссылказначение;
```
Требует: Значение должно быть значением l, а «наконечник» должен быть действительным итератором.
Эффекты: Вставляет х в контейнер, используя «наконечник» в качестве подсказки, где он будет вставлен. Если «подсказка» находится в верхнем узле, вставка занимает постоянное время (два сравнения в худшем случае)
Сложность: Логарифмическое вообще, но это амортизированное постоянное время, если t вставлено непосредственно перед намёком.
Бросает: Если выполняется внутренняя функция key_compare ordering. Сильная гарантия.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
```
шаблон<имя типаИтератор>пустотавставкаИтераторb,Итераторe;
```
Требует: Ссылочный итератор должен давать значение l типа value_type.
Эффекты: Вставляет каждый элемент диапазона в контейнер перед верхней границей ключа каждого элемента.
Сложность: Диапазон вставки, как правило, O(N * log(N)), где N - размер диапазона. Однако он является линейным в N, если диапазон уже отсортирован по значению_comp().
Броски: Ничего.
Примечание: Не влияет на достоверность итераторов и ссылок. Копировальными конструкторами не называются.
```
итераторвставить_доconst_iteratorpos,эталонноезначение;
```
Требует: Значение должно быть значением l, "pos" должно быть действительным итератором (или концом) и должно быть датчиком значения после вставки в соответствии с предикатом
: Вставляет х в контейнер перед "пос".
Сложность: Постоянное время.
Бросок: Ничего.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если «pos» не является преемником инварианта упорядочивания контейнера «value», он будет нарушен. Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
```
voidpush_backэталонноезначение;
```
Требует: Значение должно быть lvalue, и оно должно быть не меньше, чем наибольший вставленный ключ
Эффекты: Вставляет х в контейнер в последнем положении.
Сложность: Постоянное время.
Бросок: Ничего.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если значение меньше наибольшего инварианта упорядочивания вставленного ключа, оно будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
```
voidpush_frontэталонноезначение;
```
Требует: Значение должно быть lvalue, и оно не должно быть больше минимального вставленного ключа
Эффекты: Вставьте x в контейнер в первом положении.
Сложность: Постоянное время.
Бросает: Ничего.
Примечание: Эта функция не проверяет предварительные условия, поэтому, если значение больше минимального инварианта вставленного ключевого контейнера будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.
```
итераторстираниеconst_iteratori;
```
Эффекты: Стирает элемент, на который указывает i.
Сложность: Средняя сложность для элемента стирания — постоянное время.
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
```
итераторстираниеconst_iteratorb,const_iteratore;
```
Эффекты: Уничтожает диапазон, указанный на b-конце e.
Сложность: Средняя сложность для диапазона стирания составляет максимум O(log(size() + N)), где N - число элементов в диапазоне.
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
```
size_typeeraseconstkey_type&key;
```
Эффекты: Стирает все элементы с заданным значением.
Возврат: Число стертых элементов.
Сложность: O(log(size() + N.]
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
```
шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>размер_typeстираниеconst&ключ,KeyTypeKeyCompare;
```
Требует: Ключ - это такое значение, что*эторазделено по отношению к comp(nk, key) и !comp(key, nk), с Comp(nk, key), подразумевающим !comp(key, nk), с nk ключ_тип значения_type вставлен в*это.
Эффекты: Стирает все элементы заданным ключом. по сравнению с функтором «комп».
Возвращение: Количество стертых элементов.
Сложность: O(log(size() + N.]
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
```
шаблон<наименование типаДиспетчер>итераторerase_and_disposeconst_iteratori,диспетчер;
```
Требует: Диспетчер:
Эффекты: Стирает элемент, на который указывает i. Утилизатор::оператор()(указатель) вызывается для удаленного элемента.
Сложность: Средняя сложность для элемента стирания — постоянное время.
Броски: Ничего.
Примечание: Инвалидирует итераторы на стертые элементы.
```
шаблон<итераторитераторerase_and_disposeconst_iteratorb,const_iteratore,диспетчер;
```
Требует: Диспетчер:
Эффекты: Уничтожает диапазон, указанный на b-конце e. Утилизатор::оператор()(указатель) вызывается для удаленных элементов.
Сложность: Средняя сложность для диапазона стирания составляет максимум O(log(size() + N)), где N - число элементов в диапазоне.
Броски: Ничего.
Примечание: Инвалидирует итераторы на стертые элементы.
```
шаблон<имя типаразмер_типстирать_и_утилизироватьключ_тип&ключ,утилизатор;;
```
Требует: Диспетчер:
Эффекты: Стирает все элементы с заданным значением. Диспозитор::оператор()(указатель) вызывается для удаленных элементов.
Возвращение: Число стертых элементов.
Сложность: O(log(size() + N).
Бросает: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
```
шаблон<имя типаимя типаKeyTypeKeyCompare,имя типаимя типа>размер_типутилизация_и_утилизацияконст&ключ,KeyTypeKeyCompare,утилизаторутилизатор;
```
требует[1768 Ключ - это такое значение, что*эторазделено по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk) и nk ключ_тип значения_типа, вставленный в*это.
Требует: Диспетчер::оператор()(указатель) не должен бросать
: Стирает все элементы заданным ключом. по сравнению с функтором «комп». Диспозитор::оператор()(указатель) вызывается для удаленных элементов.
Возвращение: Число стертых элементов.
Сложность: O(log(size() + N.)
Броски: Ничего.
Примечание: Инвалидирует итераторы на стертые элементы.
```
voidClear;
```
Эффекты: Стирает все элементы.
Сложность: Линейный по количеству элементов на контейнере. Если это безопасный режим или авто-разъединить значение_тип. Постоянное время иначе.
Бросает: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Деструкторы не называются.
```
шаблон<имя типаДиспетчер>пустота
```
: Стирает все элементы, вызывающие диспергатор (p), для каждого узла, который должен быть удален.Сложность: Средняя сложность составляет максимум O(log(size()+N)), где N - количество элементов в контейнере.
Броски: Ничего.
Примечание: Инвалидирует итераторы (но не ссылки) на стертые элементы. Звонки N раз для удаления функтора.
```
size_typecountconstkey_type&key]const;
```
Эффекты: Возвращает число содержащихся элементов с заданным значением
Сложность: Логарифмическое к числу содержащихся элементов плюс линейное к числу объектов с заданным значением.
Броски: Еслиkey_compareбросок.
```
шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>размер_типграфconst&ключ,KeyTypeKeyCompareconstconst
```
ТребуетКлюч - это такое значение, что*эторазделено по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk), и nk ключ_тип значения_типа вставлен в*это.
: Возвращает количество содержащихся элементов с заданным ключом
Сложность: Логарифмическое к числу содержащихся элементов плюс линейное к числу объектов с заданным ключом.
Броски: Есликомпбросок.
```
итераторнижний_связанныйконстключ_тип&ключ;
```
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше k или конца (), если этот элемент не существует.
Сложность: Логарифмический.
Бросает: Еслиkey_compareбросок.
```
шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>итераторнижний_boundconstKeyType&ключ,KeyTypeKeyComparecomp);
```
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше k или конца (), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Еслиключ_сравнитебросок.
```
const_iteratorlower_boundconstkey_type&ключ]const;
```
Эффекты: Возвращает итератор к первому элементу, ключ которого не меньше k или конца(), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Еслиключ_сравнитебросок.
```
шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>const_iteratorниже_boundconstKeyTypeKeyCompareconst
```
ЭффектыВозвращает итератор к первому элементу, ключ которого не меньше k или конца(), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Еслиключ_сравнитебросок.
```
итераторверхний_связанныйконстключ_тип&ключ;
```
Эффекты: Возвращает итератор к первому элементу, ключ которого больше k или конца(), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Еслиключ_сравнитебросок.
```
шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>итераторВерхний_boundconst&ключ,KeyTypeKeyComparecomp);
```
Требует: Ключ — это такое значение, что*эторазбито на !comp(ключ, nk), при этом nk ключ_тип значения_типа вставлен в*это.
Эффекты: Возвращает итератор к первому элементу, чей ключ больше k согласно comp или end(), если этот элемент не существует.
Сложность: Логарифмический.
Бросает: Еслибрось.
```
const_iteratorupper_boundconstkey_type&ключ]const;
```
Эффекты: Возвращает итератор к первому элементу, ключ которого больше k или конца(), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Еслиключ_сравнитебросок.
```
шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>const_iteratorверхний_boundconst&ключKeyTypeKeyCompareconst
```
Требует: Ключ - это такое значение, что*эторазделено относительно !comp(ключ, nk), при этом nk ключ_тип значения_типа вставлен в*это.
Эффекты: Возвращает итератор к первому элементу, чей ключ больше k согласно comp или end(), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Еслибросок.
```
итераторнайдитеconstkey_type&key;
```
Эффекты: Найден итератор первого элемента, ключом которого является k или конец(), если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Еслиkey_compareбросок.

шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>итераторнайдитеconst&ключ,]требует: Ключ является значением, таким, что*эторазделено по отношению к comp(nk, key) и !comp(key, nk), с Comp(nk, key), подразумевающим !comp(key, nk), и nk ключ_тип значения_type вставлен в*это.

Эффекты: Найден итератор к первому элементу, ключ которого k или конец(), если этот элемент не существует.

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

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

```
const_iteratorfindconstkey_type&key]const;
```
Эффекты: Найден итератор к первому элементу, ключ которого k или конец(), если этот элемент не существует.
Сложность: Логарифмическая.
Броски: Еслиключ_сравнитебросок.
```
шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>const_iteratorнайтиconstKeyType&ключ,KeyTypeKeyComparecomp)const;
```
Требует: Ключ - это такое значение, что*эторазделено по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk), и nk ключ_тип значения_типа вставлен в*это
Эффекты: Найден итератор к первому элементу, ключ которого k или конец(), если этот элемент не существует.
Сложность: Логарифмический.
Броски: Еслибросок.
```
std::пара<итератор,итератор>равный_диапазонконстключ_тип&ключ;
```
: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Бросок: Еслиключ_сравнитебросок.
```
шаблон<имя типаKeyTypeимя типаKeyTypeKeyCompare>std::пара<итератор,итератор>равный_диапазонконст&ключ,ключKeyTypeKeyComparecomp);
```
Требует: Ключ является значением, таким, что*эторазделено по отношению к comp(nk, key) и !comp(key, nk), с Comp(nk, key), подразумевающим !comp(key, nk), с nk ключ_тип значения_type вставлен в*это.
Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Бросок: Еслиброски.

```
std::pair<const_iterator,const_iterator>equal_rangeconst&const
```
Эффекты
Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Бросает: Еслиключ_сравнитебросок.
```
шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>std::пара<const_iterator,const_iterator>equal_rangeconst&ключ,ключKeyTypeKeyComparecomp)const;
```
Требует: Ключ - это такое значение, что*эторазделено по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk), причем nk ключ_тип значения_тип вставлен в*это.
Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.
Сложность: Логарифмический.
Броски: Еслибросок.

std::итераторитераторключ_тип&ключ_тип&верхний_ключлевый_замкнутый,булправый_замкнутый]верхний_ключдолжен быть ложнымнижний_ключЕслинижний_ключэквивалентенверхний_ключ[верхний_ключ] [верхний_ключ] &&!key_comp() [нижний_ключ, верхни
Эффекты: Возвращает пару со следующими критериями:
первый = нижний_bound(lower_key) если левый_замкнут, верхний_bound(lower_key) иначе
второй = верхний_bound(upper_key) если правый_замкнут, нижний_bound(upper_key) иначе
: Логарифмический.
Бросает: Еслиключ_сравнитебросок.
Примечание: Эта функция может быть более эффективной, чем вызов верхнего и нижнего пределов для нижнего и верхнего значений.
Примечание: Экспериментальная функция, интерфейс может измениться в будущих выпусках.

шаблон<имя типаKeyType>std<итератор>итераторитераторограниченный_диапазонконст&нижний_ключ&нижний_ключ&верхний_ключ&верхний_ключcomp,правый_замкнутый; [3054
верхний_ключявляется значением, таким, что*эторазделено относительно !comp(upper_key, nk), если право_закрыто истинно, в отношении comp(nk, 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) в противном случае
Сложность: Логарифмический.
Бросает: Есликомпбросает.
Примечание: Эта функция может быть более эффективной, чем вызов top_bound и lower_bound для low_key и upper_key.
Примечание: Экспериментальная функция, интерфейс может измениться в будущих выпусках.

std::const_iteratorconst_iterator>[31200]bounded_rangeconst&key_type&top_keyleft_close,boolright_closed]const
upper_keyне должен предшествоватьlow_key
Еслиlower_keyэквивалентенupper_key
Эффекты: Возвращает пару со следующими критериями:
первый = low_bound(lower_key) если левый_замкнут, upper_bound(lower_key) иначе
второй = upper_bound(upper_key) если правый_замкнут, lower_bound(upper_key) иначе
Сложность: Логарифмический.
Бросает: Еслиkey_comparethrows.
Примечание: Эта функция может быть более эффективной, чем вызов верхнего и нижнего пределов для нижнего и верхнего значений.
Примечание: Экспериментальная функция, интерфейс может измениться в будущих выпусках.

шаблон<имя типаKeyType,имя типаKeyTypeKeyCompare>std<const_iterator>[
Верхний ключявляется значением, таким, что* эторазделено по отношению к !comp(upper_key, nk), если право_закрыто истинно, по отношению к Comp(nk, верхний_key) иначе.
верхний_ключне должен предшествоватьнижний_ключв соответствии с компом [comp(upper_key, lower_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) в противном случае
: Логарифмический.
Броски: Еслиброски.
Примечание: Эта функция может быть более эффективной, чем вызов top_bound и lower_bound для low_key и upper_key.
Примечание: Экспериментальная функция, интерфейс может измениться в будущих выпусках.

итераторитератор_toэталонноезначение;
Требует: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.
Эффекты: Возвращение: а действительный итератор i, относящийся к набору, который указывает на значение
Сложность: Постоянная.
Бросает: Ничего.

const_iteratoriterator_toconst_referenceзначение]const;
Требует: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.
Эффекты: Возврат: действительный const_iterator i, принадлежащий множеству, которое указывает на значение
Сложность: Постоянная.
Броски: Ничего.

указательunlink_leftmost_without_rebalance;
Эффекты: Отсоединяет левый узел от контейнера.
Сложность: Средняя сложность — это постоянное время.
Бросок: Ничего.
Примечания: Эта функция разрушает контейнер, и контейнер может использоваться только для дополнительных вызовов unlink_leftmost_without_rebalance. Эта функция обычно используется для достижения поэтапного контролируемого разрушения контейнера.

пустотазамена_узлазамена_этого,ссылкана;
Требует: Заменить_это должен быть действительный итератор *это и с_это не должно быть вставлено в любой контейнер.
Эффекты: Заменяет замену_this в своем положении в контейнере с_this. Контейнер не нужно перебалансировать.
Сложность: Постоянная.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты заказа контейнера, если с_это не эквивалентно *заменить_это в соответствии с правилами заказа. Эта функция быстрее, чем стирание и вставка узла, поскольку не требуется перебалансировки или сравнения.

пустотаудаление_узлассылказначение;
Эффекты: удаление "значения" из контейнера.
Броски: Ничего.
Сложность: Логарифмическое время.
Примечание: Эта статическая функция может использоваться только в непостоянных контейнерах с размером времени, которые имеют функторы сравнения без состояния.
Если пользователь называет эту функцию контейнером с постоянным размером времени или функтором сравнения состояния, будет выпущена ошибка компиляции.

пустотаперебалансировка;
Эффекты: Уравновешивает дерево.
Броски: Ничего.
Сложность: Линейный.

итераторперебалансировка_поддержкаитераторкорень;
Требует: Old_root — это узел дерева.
Эффекты: Уравновешивает поддеревья, укорененные в old_root.
Возвращение: Новый корень дерева.
Броски: Ничего.
Сложность: Линейный к элементам в поддереве.

плавающийбаланс_факторконст;
Возвращение: Балансовый фактор (альфа), используемый в этом дереве
Бросает: Ничего.
Сложность: Постоянство.

voidbalance_factorfloatnew_alpha;
Требует: new_alpha должно быть значением между 0,5 и 1,0
Эффекты: Устанавливает новый балансовый фактор (альфа) и перебалансирует дерево, если новый балансовый фактор более строг (менее), чем старый.
Бросок: Ничего.
Сложность: Линейный к элементам в поддереве.

шаблон<класс...Варианты2>пустотасливаютсяsg_multiset<...>&источник;
Требует: Варианты контейнера "источник" могут отличаться только функцией сравнения от *этого.
Эффекты: Попытки извлечь каждый элемент из источника и вставить его в объект сравнения *это. Если в элементе есть ключ, эквивалентный ключу элемента из источника, то этот элемент не извлекается из источника.
Посткондиционер: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в это, а не в источник.
Бросок: Ничего, если объект сравнения не бросит.
Сложность: N log(a.size() + N) (N имеет значение source.size())

шаблон<класс...Варианты2>пустотаслияниеsg_set<T,>&источник;
Требует: Варианты контейнера "источник" могут отличаться только функцией сравнения от *этого.
Эффекты: Попытки извлечь каждый элемент из источника и вставить его в объект сравнения *это. Если в элементе есть ключ, эквивалентный ключу элемента из источника, то этот элемент не извлекается из источника.
Посткондиционер: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в это, а не в источник.
Броски: Ничего, если объект сравнения не бросает.
Сложность: N log(a.size() + N) (N имеет значение source.size())




sg_multiset public static functions

статическийsg_multiset&контейнер_from_end_iteratorконечный_iterator;
Предварительное условие: end_iterator должен быть действительным конечным итератором контейнера.
Эффекты: Возвращает ссылку на контейнер, связанный с конечным итератором
Бросает: Ничего.
Сложность: Постоянная.

статическийconstsg_multiset&контейнер_from_end_iteratorconst_iterator;
Предварительное условие: end_iterator должен быть действительным конечным итератором контейнера.
Эффекты: Возвращает ссылку на контейнер, связанный с конечным итератором
Бросает: Ничего.
Сложность: Постоянная.

статическийsg_multiset&контейнер_от_iteratorитератор;
Предварительное условие: он должен быть действительным итератором контейнера.
Эффекты: Возвращает ссылку на контейнер, связанный с итератором
Бросает: Ничего.
Сложность: Логарифмический.

статическийconstsg_multiset&контейнер_from_iteratorconst_iterator
Предварительное условие: он должен быть действительным итератором контейнера.
Эффекты: Возвращает ссылку на контейнер, связанный с итератором
Бросает: Ничего.
Сложность: Логарифмический.

статическийитераторs_iterator_toэталонноезначение;
Требует: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.
Эффекты: Возврат: действительный итератор i, относящийся к набору, который указывает на значение
Сложность:
Бросок: Ничего.
Примечание: Эта статическая функция доступна только в том случае, если значенияне имеют состояния.

статическийconst_iterators_iterator_toconst_reference;
Требует: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.
Эффекты: Возврат: действительный итератор i, принадлежащий множеству, которое указывает на значение
Сложность: Постоянная.
Бросает: Ничего.
Примечание: Эта статическая функция доступна только в том случае, если значенияне имеют состояния.

статическийпустотныйinit_nodeэталонноезначение;
Требует: Стоимость не должна находиться в контейнере.
Эффекты: Init_node ставит крючок значения в известное состояние по умолчанию.
Броски: Ничего.
Сложность: Постоянное время.
Примечание: Эта функция помещает крюк в известное состояние по умолчанию, используемое auto_unlink и безопасными крючками.

Class template sg_multiset

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

Boost C++ Libraries

Class template sg_multiset

Synopsis

Description

sg_multiset public construct/copy/destruct

sg_multiset public member functions

sg_multiset public static functions

`sg_multiset` public construct/copy/destruct

`sg_multiset` public member functions

`sg_multiset` public static functions