- <
staticnode_ptrget_header(constconst_node_ptr&n);
>Требуется: «узел» — это узел дерева или заголовок узла.
Эффекты: Возвращает заголовок дерева.
Сложность: Логарифмический.
Бросает: Ничего.
- <
staticnode_ptrbegin_node(constconst_node_ptr&header);
>Требуется: «заголовок» — это заголовок узла дерева.
Эффекты: Возвращает первый узел дерева, заголовок, если дерево пустое.
Сложность: Постоянное время.
Бросок: Ничего.
- <
staticnode_ptrend_node(constconst_node_ptr&header);
>Требуется: «заголовок» — это заголовок узла дерева.
Эффекты: Возвращает заголовок дерева.
Сложность:
Бросает: Ничего.
- <
staticvoidswap_tree(constnode_ptr&header1,constnode_ptr&header2);
>Требуется: узлы заголовка1 и заголовка2 должны быть узлами заголовка двух деревьев.
Эффекты: Смахивает двумя деревьями. После этого заголовок 1 функции будет содержать ссылки на второе дерево, а заголовок 2 будет иметь ссылки на первое дерево.
Сложность: Постоянная.
Броски: Ничего.
- <
staticvoidswap_nodes(constnode_ptr&node1,constnode_ptr&node2);
>Требуется: узел 1 и узел 2 не могут быть узлами заголовка двух деревьев.
Эффекты: Два узла. После этого функциональный узел 1 будет вставлен в положение узел 2 перед функцией. Узел 2 будет вставлен в положение, которое узел 1 имел перед функцией.
Сложность: Логарифмическая.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты упорядочения контейнеров, если узел 1 и узел 2 не эквивалентны в соответствии с правилами упорядочения.
Экспериментальная функция
- <
staticvoidswap_nodes(constnode_ptr&node1,constnode_ptr&header1,
constnode_ptr&node2,constnode_ptr&header2);>Требуется: Узел 1 и узел 2 не могут быть узлами заголовка двух деревьев с заголовком 1 и заголовком 2.
: Два узла. После этого функциональный узел 1 будет вставлен в положение узел 2 перед функцией. Узел 2 будет вставлен в положение, которое узел 1 имел перед функцией.
Сложность: Константа.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты упорядочения контейнеров, если узел 1 и узел 2 не эквивалентны в соответствии с правилами упорядочения.
Экспериментальная функция
- <
staticvoidreplace_node(constnode_ptr&node_to_be_replaced,
constnode_ptr&new_node);>Требуется: заменённый узел должен быть вставлен в дерево, а новый узел не должен быть вставлен в дерево.
Эффекты: Заменить узел_to_be_заменить в его положении на дереве новым_узлом. Дерево не нуждается в перебалансировке
Сложность: Логарифмическая.
Бросает: Ничего.
Примечание: Эта функция будет нарушать инварианты упорядочивания контейнеров, если новый узел не эквивалентен замещённому в соответствии с правилами упорядочивания узлу_to_be_. Эта функция быстрее, чем стирание и вставка узла, так как не требуется перебалансировки и сравнения. Экспериментальная функция
- <
staticvoidreplace_node(constnode_ptr&node_to_be_replaced,
constnode_ptr&header,constnode_ptr&new_node);>Требуется: узел_to_be_replaced должен быть вставлен в дерево с заголовком "header" и новый_node не должен быть вставлен в дерево.
: Заменить узел_to_be_заменить в его положении на дереве новым_узлом. Дерево не нуждается в перебалансировке
Сложность: Постоянная.
Броски: Ничего.
Примечание: Эта функция будет нарушать инварианты упорядочивания контейнеров, если новый узел не эквивалентен замещённому в соответствии с правилами упорядочивания узлу_to_be_. Эта функция быстрее, чем стирание и вставка узла, поскольку не требуется перебалансировки или сравнения. Экспериментальная функция
- <
staticvoidunlink(constnode_ptr&node);
>Требуется: Узел — это узел дерева, но не заголовок.
Эффекты: Развязывает узел и перебалансирует дерево.
Сложность: Средняя сложность — это постоянное время.
Бросок: Ничего.
- <
staticnode_ptrunlink_leftmost_without_rebalance(constnode_ptr&header);
>Требуется:
Эффекты: Отключает левый узел от дерева и обновляет ссылку заголовка на новый левый узел.
Сложность: Средняя сложность — это постоянное время.
Броски: Ничего.
Примечания: Эта функция ломает дерево, и дерево может использоваться только для дополнительных вызовов unlink_leftmost_without_rebalance. Эта функция обычно используется для достижения постепенного контролируемого разрушения дерева.
- <
staticboolunique(constconst_node_ptr&node);
>Требуется: «узел» — это узел дерева или узел, инициализированный init(...)
Эффекты: Возвращается истинным, если узел инициализируется init() или init_node().
Сложность: Постоянное время.
Бросает: Ничего.
- <
staticstd::size_tsize(constconst_node_ptr&header);
>Требуется: Узел — это узел дерева, но это не заголовок.
Эффекты: Возвращает количество узлов поддеревья.
Сложность: Линейное время.
Бросает: Ничего.
- <
staticnode_ptrnext_node(constnode_ptr&node);
>Требуется: «узел» — это узел от дерева, за исключением заголовка.
Эффекты: Возвращает следующий узел дерева.
Сложность: Среднее постоянное время.
Бросок: Ничего.
- <
staticnode_ptrprev_node(constnode_ptr&node);
>Требуется: «узел» — это узел от дерева, за исключением самого левого узла.
: Возвращает предыдущий узел дерева.
Сложность: Среднее постоянное время.
Бросает: Ничего.
- <
staticvoidinit(constnode_ptr&node);
>Требуется: «узел» не должен быть частью какого-либо дерева.
Эффекты: После функции уникальный (узел) == истинно.
Сложность: Постоянная.
Бросает: Ничего.
Узлы: Если узел вставлен в дерево, эта функция развращает дерево.
- <
staticvoidinit_header(constnode_ptr&header);
>Требуется: Узел не должен быть частью какого-либо дерева.
Эффекты: Инициирует заголовок, чтобы представить пустое дерево. Уникальный (заголовок) == истинно.
Сложность: Константа.
Броски: Ничего.
Узлы: Если узел вставлен в дерево, эта функция развращает дерево.
- <
staticvoiderase(constnode_ptr&header,constnode_ptr&z);
>Требуется: Заголовок должен быть заголовком дерева, z узла этого дерева и z ! = заголовок.
Эффекты: Стирает узел «z» с дерева заголовком «header».
Сложность: Амортизированное постоянное время.
Броски: Ничего. Дополнительные примечания: предыдущий узел z разыгрывается для ускорения удаления диапазона.
- <
template<typenameNodePtrCompare>
staticbooltransfer_unique(constnode_ptr&header1,NodePtrComparecomp,
constnode_ptr&header2,constnode_ptr&z);>Требуется: заголовок 1 и заголовок 2 должны быть заголовками деревьев tree1 и tree2 соответственно, z незаголовочного узла tree1. NodePtrCompare - функция сравнения дерева1..
Эффекты: Переносит узел «z» с дерева1 на дерево2, если дерево1 не содержит узел, эквивалентный z.
Возврат: Правда, если узел был переадресован, ложно иначе.
Сложность: Логарифмический.
Бросок: Если сравнение падает.
- <
template<typenameNodePtrCompare>
staticvoidtransfer_equal(constnode_ptr&header1,NodePtrComparecomp,
constnode_ptr&header2,constnode_ptr&z);>Требуется: заголовок 1 и заголовок 2 должны быть заголовками деревьев tree1 и tree2 соответственно, z незаголовочного узла tree1. NodePtrCompare - функция сравнения дерева1..
Эффекты: Переносит узел «z» с дерева1 на дерево2.
Сложность: Логарифмический.
Бросает: Если сравнение падает.
- <
template<typenameCloner,typenameDisposer>
staticvoidclone(constconst_node_ptr&source_header,
constnode_ptr&target_header,Clonercloner,
Disposerdisposer);>Требуется: «клонером» должен быть функциональный объект, принимающий узел_ptr и возвращающий ему новый клонированный узел. Диспозитор должен взять узел_ptr и не должен бросать.
Эффекты: Вначале дерево-мишень опорожняется<void disposer::operator()(const node_ptr &)>для каждого узла дерева, кроме заголовка.
Затем дублирует все дерево, на которое указывает «source_header», клонируя каждый узел источника с<node_ptr Cloner::operator()(const node_ptr &)>, чтобы получить узлы целевого дерева. Если «клонер» бросает, клонированные узлы-мишени утилизируются с использованием<void disposer(const node_ptr &)>.
Сложность: Линейный к числу элемента дерева-источника плюс число элементов дерева-мишени при вызове этой функции.
Бросок: Если клонер-функтор бросит. Если это происходит, узлы-мишени удаляются.
- <
template<typenameDisposer>
staticvoidclear_and_dispose(constnode_ptr&header,Disposerdisposer);
>Требуется: Диспозитор должен быть функцией объекта, принимающей параметр node_ptr, и не должен бросать.
Эффекты: Позволяет дереву-мишени звонить<void disposer::operator()(const node_ptr &)>для каждого узла дерева, кроме заголовка.
Сложность: Линейный к числу элемента дерева-источника плюс. количество элементов дерева-мишени при вызове этой функции.
Бросок: Если клонер-функтор бросит. Если это происходит, узлы-мишени удаляются.
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::size_t
count(constnode_ptr&header,constKeyType&key,KeyNodePtrComparecomp);
>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает число элементов с ключом, эквивалентным «ключу» по «комп».
Сложность: Логарифмическая.
Бросает: Если "комп" бросит. Дополнительные примечания: элемент с ключом<key>разыгрывается.
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::size_t
count(constconst_node_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает число элементов с ключом, эквивалентным «ключу» по «комп».
Сложность: Логарифмическая.
Бросает: Если "комп" бросит. Дополнительное примечание: игра не выполняется
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticnode_ptr
lower_bound(constnode_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который не меньше «ключа» согласно «комп» или «заголовку», если этот элемент не существует.
Сложность: Логарифмическая.
Броски: Если "комп" бросит. Дополнительные примечания: разыгрывается первый узел диапазона.
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticnode_ptr
lower_bound(constconst_node_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который не меньше «ключа» согласно «комп» или «заголовку», если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если "комп" бросит. Дополнительное примечание: игра не выполняется
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticnode_ptr
upper_bound(constnode_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который больше, чем "ключ" в соответствии с "комп" или "заголовок", если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если "комп" бросит. Дополнительные примечания: разыгрывается первый узел диапазона.
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticnode_ptr
upper_bound(constconst_node_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который больше, чем "ключ" в соответствии с "комп" или "заголовок", если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если "комп" бросит. Дополнительное примечание: игра не выполняется
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticnode_ptr
find(constnode_ptr&header,constKeyType&key,KeyNodePtrComparecomp);
>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который эквивалентен «ключу» согласно «комп» или «заголовку», если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если "комп" бросит. Дополнительные примечания: найденный узел нижней границы разыгрывается.
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticnode_ptr
find(constconst_node_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает узел_ptr к первому элементу, который эквивалентен «ключу» согласно «комп» или «заголовку», если этот элемент не существует.
Сложность: Логарифмический.
Бросок: Если "комп" бросит. Дополнительное примечание: игра не выполняется
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::pair<node_ptr,node_ptr>
equal_range(constnode_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает пару node_ptr, делимитирующую диапазон, содержащий все элементы, которые эквивалентны "ключу" в соответствии с "комп" или пустой диапазон, который указывает положение, в котором эти элементы были бы, если нет эквивалентных элементов.
Сложность: Логарифмический.
Броски: Если "комп" бросит. Дополнительные примечания: разыгрывается первый узел диапазона.
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::pair<node_ptr,node_ptr>
equal_range(constconst_node_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает пару node_ptr, делимитирующую диапазон, содержащий все элементы, которые эквивалентны "ключу" в соответствии с "комп" или пустой диапазон, который указывает положение, в котором эти элементы были бы, если нет эквивалентных элементов.
Сложность: Логарифмическая.
Броски: Если "комп" бросит. Дополнительное примечание: игра не выполняется
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::pair<node_ptr,node_ptr>
lower_bound_range(constnode_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает пару node_ptr, делимитирующую диапазон, содержащий первый элемент, который эквивалентен "ключу" в соответствии с "комп" или пустой диапазон, который указывает положение, в котором этот элемент будет, если нет эквивалентных элементов.
Сложность: Логарифмическая.
Броски: Если "комп" бросит. Дополнительные примечания: разыгрывается первый узел диапазона.
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::pair<node_ptr,node_ptr>
lower_bound_range(constconst_node_ptr&header,constKeyType&key,
KeyNodePtrComparecomp);>Требуется: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.
Эффекты: Возвращает пару node_ptr, делимитирующую диапазон, содержащий первый элемент, который эквивалентен "ключу" в соответствии с "комп" или пустой диапазон, который указывает положение, в котором этот элемент будет, если нет эквивалентных элементов.
Сложность: Логарифмическая.
Броски: Если "комп" бросит. Дополнительное примечание: игра не выполняется
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::pair<node_ptr,node_ptr>
bounded_range(constnode_ptr&header,constKeyType&lower_key,
constKeyType&upper_key,KeyNodePtrComparecomp,
boolleft_closed,boolright_closed);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare может сравнить KeyType с node_ptrs дерева. Нижний ключ не должен быть больше верхнего ключа в соответствии с компом. Если "нижний_ключ" == "верхний_ключ", ('left_closed' | | 'right_closed') должно быть истинным.
: Возвращает пару со следующими критериями:
первый = нижний_связанный (нижний_ключ), если левый_закрытый, верхний_связанный (нижний_ключ) в противном случае
второй = верхний_связанный (верхний_ключ), если правый_закрытый, нижний_связанный (верхний_ключ) в противном случае
Сложность: Логарифмический.
Бросает: Если "комп" бросает.
Примечание: Эта функция может быть более эффективной, чем вызов top_bound и lower_bound для low_key и upper_key.
Примечание: Экспериментальная функция, интерфейс может измениться. Дополнительные примечания: разыгрывается первый узел диапазона.
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::pair<node_ptr,node_ptr>
bounded_range(constconst_node_ptr&header,constKeyType&lower_key,
constKeyType&upper_key,KeyNodePtrComparecomp,
boolleft_closed,boolright_closed);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare может сравнить KeyType с node_ptrs дерева. Нижний ключ не должен быть больше верхнего ключа в соответствии с компом. Если «нижний_ключ» == «верхний_ключ», то (слева_закрыто) должен быть истинным.
Эффекты: Возвращает пару со следующими критериями:
первый = нижний_bound(lower_key) если левый_замкнут, верхний_bound(lower_key) иначе
второй = верхний_bound(upper_key) если правый_замкнут, нижний_bound(upper_key) иначе
Сложность: Логарифмический.
Бросает: Если "комп" бросает.
Примечание: Эта функция может быть более эффективной, чем вызов top_bound и lower_bound для low_key и upper_key.
Примечание: Экспериментальная функция, интерфейс может измениться. Дополнительное примечание: игра не выполняется
- <
template<typenameNodePtrCompare>
staticnode_ptr
insert_equal_upper_bound(constnode_ptr&header,constnode_ptr&new_node,
NodePtrComparecomp);>Требуется: "h" должно быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs.
Эффекты: Вставляет новый узел в дерево перед верхней границей в соответствии с "комп".
Сложность: Средняя сложность для вставочного элемента является наиболее логарифмической.
Броски: Если "комп" бросит. Дополнительное примечание: вставленный узел разыгран
- <
template<typenameNodePtrCompare>
staticnode_ptr
insert_equal_lower_bound(constnode_ptr&header,constnode_ptr&new_node,
NodePtrComparecomp);>Требуется: "h" должно быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs.
ЭффектыВставляет новый узел в дерево перед нижней границей в соответствии с "комп".
Сложность: Средняя сложность для вставочного элемента является наиболее логарифмической.
Броски: Если "комп" бросит. Дополнительное примечание: вставленный узел разыгран
- <
template<typenameNodePtrCompare>
staticnode_ptr
insert_equal(constnode_ptr&header,constnode_ptr&hint,
constnode_ptr&new_node,NodePtrComparecomp);>Требуется: "заголовок" должен быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs. «Нет» — это узел из дерева «головы».
Эффекты: Вставляет новый_узел в дерево, используя «наконечник» в качестве подсказки, где он будет вставлен. Если «подсказка» находится на верхнем уровне, вставка занимает постоянное время (два сравнения в худшем случае).
Сложность: Логарифмический в целом, но это амортизированное постоянное время, если новый_узел вставлен непосредственно перед «намек».
Бросок: Если "комп" бросит. Дополнительное примечание: вставленный узел разыгран
- <
staticnode_ptr
insert_before(constnode_ptr&header,constnode_ptr&pos,
constnode_ptr&new_node);>Требуется: "заголовок" должен быть узлом заголовка дерева. "pos" должен быть действительным итератором или узлом заголовка (конца). "pos" должен быть итератором, указывающим на преемника "new_node" после вставки в соответствии с порядком уже вставленных узлов. Эта функция не проверяет «по» и это предварительное условие должно быть гарантировано абонентом.
Эффекты: Вставляет новый_узел в дерево до "по".
Сложность: Постоянное время.
Бросает: Ничего.
Примечание: Если «pos» не является преемником вновь вставленных инвариантов дерева «new_node», они могут быть сломаны. Дополнительное примечание: вставленный узел разыгран
- <
staticvoidpush_back(constnode_ptr&header,constnode_ptr&new_node);
>Требуется: «заголовок» должен быть узлом заголовка дерева. "new_node" должен быть, согласно используемому порядку, не меньше, чем наибольший вставленный ключ.
Эффекты: Вставляет новый узел в дерево до "по".
Сложность: Постоянное время.
Бросает: Ничего.
Примечание: Если "new_node" меньше, чем наибольшие инварианты вставленного ключевого дерева, то они разбиваются. Эта функция немного быстрее, чем использование «insert_before». Дополнительное примечание: вставной узел разыгран
- <
staticvoidpush_front(constnode_ptr&header,constnode_ptr&new_node);
>Требуется: "заголовок" должен быть узлом заголовка дерева. "новый_узел" должен быть, согласно используемому порядку, не больше самого низкого вставленного ключа.
Эффекты: Вставляет новый узел в дерево до "по".
Сложность: Постоянное время.
Бросает: Ничего.
Примечание: Если "new_node" больше, чем инварианты наименьшего вставленного ключевого дерева, то они разбиваются. Эта функция немного быстрее, чем использование «insert_before». Дополнительное примечание: вставленный узел разыгран
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::pair<node_ptr,bool>
insert_unique_check(constnode_ptr&header,constKeyType&key,
KeyNodePtrComparecomp,
insert_commit_data&commit_data);>Требуется: «заголовок» должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. Узел PtrCompare сравнивает KeyType with node_ptr.
Эффекты: Проверяет, есть ли эквивалентный узел для «ключа» в дереве в соответствии с «комп» и получает необходимую информацию для реализации вставки узла постоянного времени, если нет эквивалентного узла.
Возвращение: При наличии эквивалентного значения возвращает пару, содержащую node_ptr, к уже существующему узлу и ложному. Если нет эквивалентного ключа, можно вставить возвраты, верные в булевой паре, и заполнить «commit_data», который предназначен для использования с функцией «insert_commit» для достижения функции вставки в постоянное время.
Сложность: Средняя сложность в лучшем случае логарифмическая.
Броски: Если "комп" бросает.
Примечания: Эта функция используется для повышения производительности при строительстве узла дорого и пользователь не хочет иметь два эквивалентных узла в дереве: если есть эквивалентное значение, построенный объект должен быть отброшен. Часто часть узла, которая используется для наложения заказа, намного дешевле в конструировании, чем узел, и эта функция предлагает возможность использовать эту часть для проверки того, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить узел и использовать «insert_commit» для вставки узла в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
«commit_data» остается действительным для последующего «insert_unique_commit» только в том случае, если из набора больше не вставляются или не стираются объекты. Дополнительное примечание: узлы с заданным ключом разыгрываются
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticstd::pair<node_ptr,bool>
insert_unique_check(constnode_ptr&header,constnode_ptr&hint,
constKeyType&key,KeyNodePtrComparecomp,
insert_commit_data&commit_data);>Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает KeyType с node_ptr. "hint" - это узел из дерева "header".
Эффекты: Проверяет, есть ли эквивалентный узел для «ключа» в дереве в соответствии с «компом», используя «наконечник» в качестве подсказки, где он должен быть вставлен, и получает необходимую информацию для реализации вставки узла постоянного времени, если нет эквивалентного узла. Если «подсказка» находится в верхнем узле, функция имеет постоянную временную сложность (два сравнения в худшем случае).
Возвращение: При наличии эквивалентного значения возвращает пару, содержащую node_ptr, к уже существующему узлу и ложному. Если нет эквивалентного ключа, может быть вставлен возврат, истинный в булевой паре возврата, и заполняет «commit_data», который предназначен для использования с функцией «insert_commit» для достижения функции вставки в постоянное время.
Сложность: Средняя сложность в лучшем случае логарифмическая, но это амортизированное постоянное время, если новый_узел должен быть вставлен непосредственно перед «подсказкой»
Бросок: Если "комп" бросит.
Примечания: Эта функция используется для повышения производительности при строительстве узла дорого и пользователь не хочет иметь два эквивалентных узла в дереве: если есть эквивалентное значение, построенный объект должен быть отброшен. Часто часть узла, которая используется для наложения заказа, намного дешевле в конструировании, чем узел, и эта функция предлагает возможность использовать эту часть для проверки того, будет ли вставка успешной.
Если проверка прошла успешно, пользователь может построить узел и использовать «insert_commit» для вставки узла в постоянное время. Это придает полную логарифмическую сложность вставке: check(O(log(N)) + commit(O(1)).
«commit_data» остается действительным для последующего «insert_unique_commit» только в том случае, если из набора больше не вставлены или не стерты объекты. Дополнительное примечание: узлы с заданным ключом разыгрывают
- <
staticvoidinsert_unique_commit(constnode_ptr&header,
constnode_ptr&new_value,
constinsert_commit_data&commit_data);>Требуется: "заголовок" должен быть узлом заголовка дерева. "commit_data" должно быть получено из предыдущего вызова "insert_unique_check". Никакие объекты не должны были быть вставлены или стерты из набора между «insert_unique_check», который заполнил «commit_data» и призывом «insert_commit»
: Вставляет новый_узел в набор, используя информацию, полученную из "commit_data", которую заполнил предыдущий "insert_check".
Сложность:
Бросок: Ничего.
Примечания: Эта функция имеет смысл только в том случае, если ранее была выполнена «insert_unique_check» для заполнения «commit_data». Не следует вставлять или стирать значение между вызовами «insert_check» и «insert_commit».
- <
staticboolis_header(constconst_node_ptr&p);
>Требуется: p - узел дерева.
Эффекты: Возвращается истинно, если p - заголовок дерева.
Сложность: Постоянная.
Бросает: Ничего.
- <
staticvoidrebalance(constnode_ptr&header);
>Требуется: Заголовок должен быть заголовком дерева.
Эффекты:
Бросает: Ничего.
Сложность: Линейный.
- <
staticnode_ptrrebalance_subtree(constnode_ptr&old_root);
>Требуется: Old_root — это узел дерева. Она не будет нулевой.
Эффекты: Уравновешивает поддеревья, укорененные в старом корне.
Возвращение: Новый корень дерева.
Бросает: Ничего.
Сложность: Линейный.
- <
staticvoidsplay_up(constnode_ptr&node,constnode_ptr&header);
>
- <
template<typenameKeyType,typenameKeyNodePtrCompare>
staticnode_ptr
splay_down(constnode_ptr&header,constKeyType&key,
KeyNodePtrComparecomp,bool*pfound=0);>
