treap_set();

Эффекты: Постройте пустой контейнер.

Сложность: Постоянная.

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

explicittreap_set(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_set(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_set(treap_set&&x);

Эффекты: делать

treap_set&operator=(treap_set&&x);

Эффекты: делать

~treap_set();

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

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

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

iteratorbegin();

Эффекты: Возвращает итератор, указывающий на начало контейнера.

Сложность: Постоянная.

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

const_iteratorbegin()const;

Эффекты: Возвращает const_iterator, указывающий на начало контейнера.

Сложность: Постоянная.

Бросает: Ничего.

const_iteratorcbegin()const;

Эффекты: Возвращает const_iterator, указывающий на начало контейнера.

Сложность: Постоянная.

Бросает: Ничего.

iteratorend();

Эффекты: Возвращает итератор, указывающий на конец контейнера.

Сложность: Постоянная.

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

const_iteratorend()const;

Эффекты: Возвращает const_iterator, указывающий на конец контейнера.

Сложность: Постоянная.

Бросает: Ничего.

const_iteratorcend()const;

Эффекты: Возвращает const_iterator, указывающий на конец контейнера.

Сложность: Постоянная.

Бросает: Ничего.

reverse_iteratorrbegin();

Эффекты: Возвращает обратный_iterator, указывающий на начало обратного контейнера.

Сложность: Константа.

Бросает: Ничего.

const_reverse_iteratorrbegin()const;

Эффекты: Возвращает const_reverse_iterator, указывающий на начало обратного контейнера.

Сложность: Постоянная.

Бросает: Ничего.

const_reverse_iteratorcrbegin()const;

Эффекты: Возвращает const_reverse_iterator, указывающий на начало обратного контейнера.

Сложность: Постоянная.

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

reverse_iteratorrend();

Эффекты: Возвращает обратный_iterator, указывающий на конец обратного контейнера.

Сложность: Постоянная.

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

const_reverse_iteratorrend()const;

Эффекты: Возвращает const_reverse_iterator, указывающий на конец обратного контейнера.

Сложность: Постоянная.

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

const_reverse_iteratorcrend()const;

Эффекты: Возвращает const_reverse_iterator, указывающий на конец обратного контейнера.

Сложность: Постоянная.

Бросает: Ничего.

iteratorroot();

Эффекты: Возвращает итератор, указывающий на корневой узел контейнера или конец(), если он не присутствует.

Сложность: Постоянная.

Бросает: Ничего.

const_iteratorroot()const;

Эффекты: Возвращает const_iterator, указывающий на корневой узел контейнера или кенд(), если он отсутствует.

Сложность: Постоянная.

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

const_iteratorcroot()const;

Эффекты: Возвращает const_iterator, указывающий на корневой узел контейнера или кенд(), если он отсутствует.

Сложность: Постоянная.

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

key_comparekey_comp()const;

Эффекты: Возвращает ключевой_сравнительный объект, используемый контейнером.

Сложность: Постоянная.

Бросает: Если бросит key_compare копи-конструктор.

value_comparevalue_comp()const;

Эффекты: Возвращает значение_сравнительный объект, используемый контейнером.

Сложность: Постоянная.

Бросает: Если value_compare копи-конструктор бросает.

boolempty()const;

Эффекты: Возвращается, если контейнер пуст.

Сложность: Постоянная.

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

size_typesize()const;

Эффекты: Возвращает количество элементов, хранящихся в контейнере.

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

Бросает: Ничего.

voidswap(treap_set&other);

Эффекты: Изменяет содержание двух кранов.

Сложность: Постоянная.

Бросает: Если сравнительный своп функтора бросает вызов.

template<typenameCloner,typenameDisposer>
 voidclone_from(consttreap_set&src,Clonercloner,Disposerdisposer);

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

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

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

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

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

template<typenameCloner,typenameDisposer>
 voidclone_from(treap_set&&src,Clonercloner,Disposerdisposer);

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

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

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

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

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

iteratortop();

Эффекты: Возвращает итератор, указывающий на объект с наивысшим приоритетом.

Сложность: Постоянная.

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

const_iteratortop()const;

Эффекты: Возвращает const_iterator, указывающий на объект с наивысшим приоритетом трэпа.

Сложность: Постоянная.

Бросает: Ничего.

const_iteratorctop()const;

Эффекты: Возвращает const_iterator, указывающий на объект с наивысшим приоритетом.

Сложность: Постоянная.

Бросает: Ничего.

reverse_iteratorrtop();

Эффекты: Возвращает reverse_iterator, указывающий на объект с наивысшим приоритетом.

Сложность: Постоянная.

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

const_reverse_iteratorrtop()const;

Эффекты: Возвращает const_reverse_iterator, указывая на наивысший приоритетный объект обратного рывка.

Сложность: Постоянная.

Бросает: Ничего.

const_reverse_iteratorcrtop()const;

Эффекты: Возвращает const_reverse_iterator, указывающий на объект с наивысшим приоритетом реверсивного трапа.

Сложность: Постоянная.

Бросает: Ничего.

priority_comparepriority_comp()const;

Эффекты: Возвращает const_reverse_iterator, указывающий на объект с наивысшим приоритетом.

Сложность: Постоянная.

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

std::pair<iterator,bool>insert(referencevalue);

Требуется: значение должно быть lvalue

Эффекты: Вставляет значение в контейнер, если оно еще не присутствует.

Сложность: Средняя сложность вставочного элемента в большинстве случаев логарифмическая.

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

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

iteratorinsert(const_iteratorhint,referencevalue);

Требуется: Значение должно быть lvalue, а «наконечник» должен быть действительным итератором

Эффекты: Пытается вставить x в контейнер, используя «наконечник» в качестве подсказки, где он будет вставлен.

Сложность: Логарифмический вообще, но это амортизированное постоянное время (два сравнения в худшем случае), если t вставлено непосредственно перед подсказкой.

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

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

std::pair<iterator,bool>
insert_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_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<iterator,bool>
 insert_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_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" только в том случае, если из контейнера не вставлено или стерто больше объектов.

template<typenameIterator>voidinsert(Iteratorb,Iteratore);

Требуется: Ссылочный итератор должен давать значение l типа value_type.

Эффекты: Пытается вставить каждый элемент диапазона в контейнер.

Сложность: Диапазон вставки, как правило, O(N * log(N)), где N - размер диапазона. Однако он является линейным в N, если диапазон уже отсортирован по key_comp().

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

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

iteratorinsert_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);

Требуется: Значение должно быть значением l, и оно не должно быть больше минимального вставленного ключа

Эффекты: Вставьте 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.]

Бросает: если забрасывает внутренняя функция priority_compare. Эквивалентная гарантияпри (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).

Броски: Если функция priority_compare бросает, то слабая гарантия и куча инвариантов нарушаются. Самое безопасное — очистить или уничтожить контейнер.

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

template<typenameKeyType,typenameKeyTypeKeyCompare,typenameDisposer>
 size_typeerase_and_dispose(constKeyType&key,KeyTypeKeyComparecomp,
                             Disposerdisposer);

Требует: Диспетчер::оператор()(указатель) не должен бросать.

: Стирает все элементы заданным ключом. По данным сравнения функтор «комп». Диспозитор::оператор()(указатель) вызывается для удаленных элементов.

Возвращение: Число стертых элементов.

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

Броски: Если функция priority_compare бросает, то слабая гарантия и куча инвариантов нарушаются. Самое безопасное — очистить или уничтожить контейнер.

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

voidclear();

Эффекты: Стирает все элементы.

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

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

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

template<typenameDisposer>voidclear_and_dispose(Disposerdisposer);

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

Бросает: Ничего.

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

size_typecount(constkey_type&key)const;

Эффекты: Возвращает число содержащихся элементов с заданным значением

Сложность: Логарифмическое к числу содержащихся элементов плюс линейное к числу объектов с заданным значением.

Бросок: Если<key_compare>бросит

template<typenameKeyType,typenameKeyTypeKeyCompare>
 size_typecount(constKeyType&key,KeyTypeKeyComparecomp)const;

Требуется: Ключ является таким значением, что<*this>разбивается по отношению к comp(nk, key) и !comp(key, nk), причем comp(nk, key) подразумевает !comp(key, nk), а nk ключ_тип значения_type вставляется в<*this>.

Эффекты: Возвращает число содержащихся элементов с заданным ключом

Сложность: Логарифмическое к числу содержащихся элементов плюс линейное к числу объектов с заданным ключом.

Бросок: Если<comp>бросит.

iteratorlower_bound(constkey_type&key);

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

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

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

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 — ключ_тип значения_типа, вставленный в<*this>.

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

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

Бросок: Если<comp>бросок.

std::pair<iterator,iterator>equal_range(constkey_type&key);

Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.

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

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

template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<iterator,iterator>
 equal_range(constKeyType&key,KeyTypeKeyComparecomp);

Требуется: Ключ - это значение, такое, что<*this>разделено по отношению к comp(nk, key) и !comp(key, nk), с comp(nk, key), подразумевающим !comp(key, nk), с nk ключ_тип значения_type вставлен в<*this>.

Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.

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

Броски: Если<comp>бросок.

std::pair<const_iterator,const_iterator>
equal_range(constkey_type&key)const;

Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.

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

Бросает: Если<key_compare>бросит

template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<const_iterator,const_iterator>
 equal_range(constKeyType&key,KeyTypeKeyComparecomp)const;

Требуется: Ключ - это значение, такое, что<*this>разделено по отношению к comp(nk, key) и !comp(key, nk), с comp(nk, key), подразумевающим !comp(key, nk), с nk ключ_тип значения_type вставлен в<*this>.

Эффекты: Найден диапазон, содержащий все элементы, ключ которых k или пустой диапазон, который указывает положение, в котором эти элементы были бы, если бы у них не было элементов с ключом k.

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

Бросает: Если<comp>бросит

std::pair<iterator,iterator>
bounded_range(constkey_type&lower_key,constkey_type&upper_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') должен быть ложным.

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

первый = нижний_связанный (нижний_ключ), если левый_закрытый, верхний_связанный (нижний_ключ) в противном случае

второй = верхний_связанный (верхний_ключ), если правый_закрытый, нижний_связанный (верхний_ключ) в противном случае

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

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

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

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

template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<iterator,iterator>
 bounded_range(constKeyType&lower_key,constKeyType&upper_key,
               KeyTypeKeyComparecomp,boolleft_closed,boolright_closed);

Требует:<lower_key>является значением, таким, что<*this>разделен по отношению к comp(nk, lower_key) если левый_замкнутый является истинным, по отношению к !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) в противном случае

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

Броски: Если

Примечание: Эта функция может быть более эффективной, чем вызов верхнего_bound и нижнего_bound для нижнего_key и верхнего_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') должен быть ложным.

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

первый = нижний_связанный (нижний_ключ), если левый_закрытый, верхний_связанный (нижний_ключ) в противном случае

второй = верхний_связанный (верхний_ключ), если правый_закрытый, нижний_связанный (верхний_ключ) в противном случае

: Логарифмический.

Броски: Если<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, 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.

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

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);

Эффекты: Удаление «значения» из контейнера.

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

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

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

Если пользователь называет эту функцию контейнером с постоянным размером времени или функтором сравнения состояния, будет выпущена ошибка компиляции.

template<class...Options2>voidmerge(treap_set<T,Options2...>&source);

Требуется: Варианты контейнера "источник" могут отличаться только функцией сравнения от *этого.

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

Посткондиционер: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в это, а не в источник.

Бросок: Ничего, если объект сравнения не бросит.

Сложность: N log(a.size() + N) (N имеет значение source.size())

template<class...Options2>
 voidmerge(treap_multiset<T,Options2...>&source);

Требуется: Варианты контейнера "источник" могут отличаться только функцией сравнения от *этого.

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

Посткондиционер: Указатели и ссылки на переданные элементы источника относятся к тем же элементам, но как к членам этого. Итераторы, относящиеся к переданным элементам, будут продолжать ссылаться на их элементы, но теперь они ведут себя как итераторы в это, а не в источник.

Бросок: Ничего, если объект сравнения не бросит.

Сложность: N log(a.size() + N) (N имеет значение source.size())

statictreap_set&container_from_end_iterator(iteratorend_iterator);

Предварительное условие: end_iterator должен быть действительным конечным итератором контейнера.

Эффекты: Возвращает ссылку на контейнер, связанный с конечным итератором

Бросает: Ничего.

Сложность: Постоянная.

staticconsttreap_set&
container_from_end_iterator(const_iteratorend_iterator);

Предварительное условие: end_iterator должен быть действительным конечным итератором контейнера.

Эффекты: Возвращает ссылку const на контейнер, связанный с конечным итератором

Бросает: Ничего.

Сложность: Постоянная.

statictreap_set&container_from_iterator(iteratorit);

Предварительное условие: он должен быть действительным итератором контейнера.

Эффекты: Возвращает ссылку на контейнер, связанный с итератором

Бросает: Ничего.

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

staticconsttreap_set&container_from_iterator(const_iteratorit);

Предварительное условие: он должен быть действительным итератором контейнера.

Эффекты: Возвращает ссылку на контейнер, связанный с итератором

Бросает: Ничего.

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

staticiterators_iterator_to(referencevalue);

Требуется: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.

Эффекты: Возвращение: a действительный итератор i, относящийся к набору, который указывает на значение

Сложность:

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

Примечание: Эта статическая функция доступна только в том случае, если значенияне имеют состояния.

staticconst_iterators_iterator_to(const_referencevalue);

Требуется: Значение должно быть lvalue и должно быть в наборе соответствующего типа. В противном случае поведение не определено.

Эффекты: Возврат: действительный итератор i, относящийся к набору, который указывает на значение

Сложность: Постоянная.

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

Примечание: Эта статическая функция доступна только в том случае, если значенияне имеют состояния.

staticvoidinit_node(referencevalue);

Требуется: Стоимость не должна находиться в контейнере.

Эффекты: Init_node ставит крючок значения в известное состояние по умолчанию.

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

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

Примечание: Эта функция помещает крюк в известное состояние по умолчанию, используемое auto_unlink и безопасными крючками.