splay_set();

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

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

Бросает: Если value_traits::node_traits::node constructor throws (это не происходит с заранее заданными Boost.Intrusive крючками) или копи-конструктор key_compare object throws. Базовая гарантия.

explicitsplay_set(constkey_compare&cmp,
                  constvalue_traits&v_traits=value_traits());

Эффекты: Постраивает пустой контейнер с заданными сравнениями и чертами.

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

Бросает: Если value_traits::node_traits::node constructor throws (это не происходит с заранее заданными Boost.Intrusive крючками) или копи-конструктор key_compare object throws. Базовая гарантия.

template<typenameIterator>
 splay_set(Iteratorb,Iteratore,constkey_compare&cmp=key_compare(),
           constvalue_traits&v_traits=value_traits());

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

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

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

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

splay_set(splay_set&&x);

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

splay_set&operator=(splay_set&&x);

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

~splay_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, используемый контейнером.

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

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

value_comparevalue_comp()const;

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

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

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

boolempty()const;

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

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

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

size_typesize()const;

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

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

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

voidswap(splay_set&other);

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

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

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

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

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

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

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

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

Бросок: Если клонер бросает или предикат копирования, задание бросает. Базовая гарантия. Дополнительные примечания: он также копирует альфа-фактор из исходного контейнера.

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

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

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

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

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

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

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

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

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

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

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

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

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

iteratorinsert(const_iteratorhint,referencevalue);

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

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

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

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

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

std::pair<iterator,bool>
insert_check(constkey_type&key,insert_commit_data&commit_data);

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

Возвращение: Если существует эквивалентное значение, то пара, содержащая итератор, возвращается к уже существующей стоимости и ложна. Если значение может быть вставлено, возвращается истинное значение в возвращенной паре boolean и заполняет «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 вставлено непосредственно перед намёком.

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

template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<iterator,bool>
 insert_check(constKeyType&key,KeyTypeKeyComparecomp,
              insert_commit_data&commit_data);

Требуется: Comp должен быть функцией сравнения, которая вызывает ту же строгую слабую упорядоченность, что и key_compare. Разница в том, что комп сравнивает произвольный ключ с содержащимися значениями.

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

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

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

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

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

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

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

template<typenameKeyType,typenameKeyTypeKeyCompare>
 std::pair<iterator,bool>
 insert_check(const_iteratorhint,constKeyType&key,
              KeyTypeKeyComparecomp,insert_commit_data&commit_data);

Требуется: Comp должен быть функцией сравнения, которая вызывает ту же строгую слабую упорядоченность, что и key_compare. Разница в том, что комп сравнивает произвольный ключ с содержащимися значениями.

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

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

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

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

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

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

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

template<typenameIterator>voidinsert(Iteratorb,Iteratore);

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

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

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

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

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

iteratorinsert_commit(referencevalue,
                      constinsert_commit_data&commit_data);

Требуется: Значение должно быть значением типа value_type. commit_data должны быть получены из предыдущего вызова на «insert_check». Никакие объекты не должны были быть вставлены или стерты из контейнера между «insert_check», который заполнил «commit_data» и призывом «insert_commit».

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

Возвращение: Итератор для вновь вставленного объекта.

Сложность:

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

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

iteratorinsert_before(const_iteratorpos,referencevalue);

Требуется: Значение должно быть значением l, "pos" должно быть действительным итератором (или концом) и должно быть датчиком значения после вставки в соответствии с предикатом

: Вставляет х в контейнер перед "по".

Сложность:

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

Примечание: Эта функция не проверяет предварительные условия, поэтому, если «pos» не является преемником инварианта упорядочивания контейнера «value», он будет нарушен. Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.

voidpush_back(referencevalue);

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

: Вставьте x в контейнер в последнем положении.

Сложность:

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

Примечание: Эта функция не проверяет предварительные условия, поэтому, если значение меньше наибольшего инварианта упорядочивания вставленного ключа, оно будет нарушено. Эта функция немного более эффективна, чем использование «insert_before». Это низкоуровневая функция, которая используется только для повышения производительности продвинутыми пользователями.

voidpush_front(referencevalue);

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

Эффекты: Вставьте x в контейнер в первом положении.

Сложность:

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

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

iteratorerase(const_iteratori);

Эффекты: Стирает элемент, на который указывает i.

Сложность: Средняя сложность для элемента стирания — постоянное время.

Бросает:

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

iteratorerase(const_iteratorb,const_iteratore);

Эффекты: Уничтожает диапазон, указанный на b-конце e.

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

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

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

size_typeerase(constkey_type&key);

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

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

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

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

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

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

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

Эффекты: Стирает все элементы заданным ключом. Согласно сравнительным функторам «комп.»

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

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

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

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

template<typenameDisposer>
 iteratorerase_and_dispose(const_iteratori,Disposerdisposer);

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

: Стирает элемент, на который указывает i. Утилизатор::оператор()(указатель) вызывается для удаленного элемента.

Сложность: Средняя сложность для элемента стирания — постоянное время.

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

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

template<typenameDisposer>
 iteratorerase_and_dispose(const_iteratorb,const_iteratore,
                            Disposerdisposer);

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

Эффекты: Уничтожает диапазон, указанный на b-конце e. Утилизатор::оператор()(указатель) вызывается для удаленных элементов.

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

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

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

template<typenameDisposer>
 size_typeerase_and_dispose(constkey_type&key,Disposerdisposer);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

voidclear();

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

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

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

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

template<typenameDisposer>voidclear_and_dispose(Disposerdisposer);

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

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

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

size_typecount(constkey_type&key)const;

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

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

Броски: Если<key_compare>бросит. Дополнительное примечание: функция const не выполняется

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>бросит. Дополнительное примечание: функция const не выполняется

size_typecount(constkey_type&key)const;

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

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

Броски: Если<key_compare>бросок. Дополнительное примечание: функция const не выполняется

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>бросит. Дополнительное примечание: функция const не выполняется

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>бросит. Дополнительное примечание: функция const не выполняется

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

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

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

Бросает: Если<key_compare>бросит. Дополнительное примечание: функция const не выполняется

iteratorupper_bound(constkey_type&key);

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

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

Броски: Если<key_compare>бросок. Дополнительное примечание: неконст-функция, игра выполняется для первого элемента равного диапазона «значения»

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

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

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

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

Бросок: Если<comp>бросок. Дополнительное примечание: неконст-функция, игра выполняется для первого элемента равного диапазона «ключа»

const_iteratorupper_bound(constkey_type&key)const;

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

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

Бросок: Если бросит<key_compare>. Дополнительное примечание: функция const не выполняется

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

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

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

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

Броски: Если<comp>бросок. Дополнительное примечание: функция const не выполняется

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>бросит. Дополнительное примечание: функция const не выполняется

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>бросит. Дополнительное примечание: функция const не выполняется

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() (верхний_key, нижний_key) должен быть ложным]

<lower_key>Если<lower_key>эквивалентен<upper_key>[!key_comp() (верхний_key, нижний_key) && !key_comp() (нижний_key, верхний_key)] тогда ['left_closed' | | 'right_closed') должен быть ложным.

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

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

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

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

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

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

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

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

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

<upper_key>является значением, таким, что<*this>разбивается по отношению к !comp(upper_key, nk), если право_closed истинно, по отношению к comp(nk, upper_key) иначе.

<upper_key>не должен предшествовать<lower_key>согласно comp [comp(upper_key, lower_key) должен быть ложным]

Если<lower_key>эквивалентен<upper_key>[!comp(upper_key, lower_key) && !comp(lower_key, upper_key)], то ('left_closed' | | 'right_closed') должен быть ложным.

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

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

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

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

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

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

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

std::pair<const_iterator,const_iterator>
bounded_range(constkey_type&lower_key,constkey_type&upper_key,
             boolleft_closed,boolright_closed)const;

Требует:<upper_key>не должен предшествовать<lower_key>в соответствии с key_compare. [key_comp()(upper_key, lower_key) должен быть ложным]

Если<lower_key>эквивалентен<upper_key>[!key_comp()(!upper_key, lower_key) && !key_comp()((lower_key, upper_key)] тогда ['left_closed' | | 'right_closed') должно быть ложным

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

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

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

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

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

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

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

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

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

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

<upper_key>не должен предшествовать<lower_key>согласно comp [comp(upper_key, lower_key) должен быть ложным]

Если<lower_key>эквивалентно<upper_key>[!comp(upper_key, lower_key) && !comp(lower_key, upper_key)], то ('left_closed' | | 'right_closed') должно быть ложным.

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

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

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

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

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

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

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

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

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

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

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

voidsplay_up(iteratori);

Требует: Я должен быть действительным итератором этого.

Эффекты: Перестраивает контейнер таким образом, что элемент, указанный i, помещается в качестве корня дерева, улучшая будущие поиски этого значения.

Сложность: Амортизированный логарифм.

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

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

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

Сложность: Амортизированный логарифм.

Возвращение: Итератор к новому корню дерева, конец (), если дерево пусто.

Бросает: Если сравнение бросает функтор.

iteratorsplay_down(constkey_type&key);

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

Сложность: Амортизированный логарифм.

Возвращение: Итератор к новому корню дерева, конец (), если дерево пусто.

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

voidrebalance();

Эффекты: Перебалансирует дерево.

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

Сложность: Линейный.

iteratorrebalance_subtree(iteratorroot);

Требуется: Old_root — это узел дерева.

Эффекты: Уравновешивает дерево, укорененное в старом корне.

Возвращение: Новый корень дерева

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

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

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

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

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

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

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

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

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

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

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

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

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

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

staticsplay_set&container_from_end_iterator(iteratorend_iterator);

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

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

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

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

staticconstsplay_set&
container_from_end_iterator(const_iteratorend_iterator);

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

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

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

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

staticsplay_set&container_from_iterator(iteratorit);

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

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

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

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

staticconstsplay_set&container_from_iterator(const_iteratorit);

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

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

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

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

staticiterators_iterator_to(referencevalue);

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

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

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

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

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

staticconst_iterators_iterator_to(const_referencevalue);

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

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

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

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

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

staticvoidinit_node(referencevalue);

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

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

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

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

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