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_заменить в его положении на дереве новым_узлом. Дерево не нуждается в перебалансировке

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

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

Примечание: Эта функция будет нарушать инварианты упорядочивания контейнеров, если новый узел не эквивалентен замещённому в соответствии с правилами упорядочивания узлу_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_. Эта функция быстрее, чем стирание и вставка узла, поскольку не требуется перебалансировки или сравнения. Экспериментальная функция

staticnode_ptrunlink_leftmost_without_rebalance(constnode_ptr&header);

Требует: Заголовок — это заголовок дерева.

Эффекты: Отключает самый левый узел от дерева и обновляет ссылку заголовка на новый самый левый узел.

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

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

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

staticboolunique(constconst_node_ptr&node);

Требуется: «узел» - это узел дерева или узел, инициализированный init(...) или init_node.

Эффекты: Возвращается истинным, если узел инициализируется 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);

Требуется: Узел не должен быть частью какого-либо дерева.

Эффекты: Инициирует заголовок, чтобы представить пустое дерево. Уникальный (заголовок) == истинно.

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

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

Узлы: Если узел вставлен в дерево, эта функция развращает дерево.

template<typenameAlphaByMaxSize>
 staticnode_ptr
 erase(constnode_ptr&header,constnode_ptr&z,std::size_ttree_size,
       std::size_t&max_tree_size,AlphaByMaxSizealpha_by_maxsize);

Требуется: Заголовок должен быть заголовком дерева, z узла этого дерева и z ! = заголовок.

Эффекты: Стирает узел "z" с дерева заголовком "header".

Сложность: Амортизированное постоянное время.

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

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>
 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(constconst_node_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(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(constconst_node_ptr&header,constKeyType&lower_key,
               constKeyType&upper_key,KeyNodePtrComparecomp,
               boolleft_closed,boolright_closed);

Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare может сравнить KeyType с node_ptrs дерева. Нижний ключ не должен быть больше верхнего ключа в соответствии с компом. Если «нижний_ключ» == «верхний_ключ», то (слева_закрыто) должен быть истинным.

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

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

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

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

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

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

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

template<typenameKeyType,typenameKeyNodePtrCompare>
 staticstd::size_t
 count(constconst_node_ptr&header,constKeyType&key,
       KeyNodePtrComparecomp);

Требуется: "заголовок" должен быть узлом заголовка дерева. KeyNodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. KeyNodePtrCompare можно сравнить KeyType with tree's node_ptrs.

Эффекты: Возвращает число элементов с ключом, эквивалентным «ключу» по «комп».

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

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

template<typenameNodePtrCompare,typenameH_Alpha>
 staticnode_ptr
 insert_equal_upper_bound(constnode_ptr&h,constnode_ptr&new_node,
                          NodePtrComparecomp,std::size_ttree_size,
                          H_Alphah_alpha,std::size_t&max_tree_size);

Требуется: "h" должно быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs.

ЭффектыВставляет новый узел в дерево перед верхней границей в соответствии с "комп".

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

Броски: Если "комп" бросит.

template<typenameNodePtrCompare,typenameH_Alpha>
 staticnode_ptr
 insert_equal_lower_bound(constnode_ptr&h,constnode_ptr&new_node,
                          NodePtrComparecomp,std::size_ttree_size,
                          H_Alphah_alpha,std::size_t&max_tree_size);

Требуется: "h" должно быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs.

Эффекты: Вставляет новый узел в дерево перед нижней границей согласно "комп".

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

Броски: Если "комп" бросит.

template<typenameNodePtrCompare,typenameH_Alpha>
 staticnode_ptr
 insert_equal(constnode_ptr&header,constnode_ptr&hint,
              constnode_ptr&new_node,NodePtrComparecomp,
              std::size_ttree_size,H_Alphah_alpha,
              std::size_t&max_tree_size);

Требуется: "заголовок" должен быть узлом заголовка дерева. NodePtrCompare - это функциональный объект, который вызывает строгое слабое упорядочение, совместимое со строгим слабым упорядочением, используемым для создания дерева. NodePtrCompare сравнивает два узла_ptrs. «Нет» — это узел из дерева «головы».

Эффекты: Вставляет новый_узел в дерево, используя «наконечник» в качестве подсказки, где он будет вставлен. Если «подсказка» находится на верхнем уровне, вставка занимает постоянное время (два сравнения в худшем случае).

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

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

template<typenameH_Alpha>
 staticnode_ptr
 insert_before(constnode_ptr&header,constnode_ptr&pos,
               constnode_ptr&new_node,std::size_ttree_size,
               H_Alphah_alpha,std::size_t&max_tree_size);

Требуется: "заголовок" должен быть узлом заголовка дерева. "pos" должен быть действительным итератором или узлом заголовка (конца). "pos" должен быть итератором, указывающим на преемника "new_node" после вставки в соответствии с порядком уже вставленных узлов. Эта функция не проверяет «по» и это предварительное условие должно быть гарантировано абонентом.

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

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

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

Примечание: Если «pos» не является преемником вновь вставленных инвариантов дерева «new_node», они могут быть сломаны.

template<typenameH_Alpha>
 staticvoidpush_back(constnode_ptr&header,constnode_ptr&new_node,
                       std::size_ttree_size,H_Alphah_alpha,
                       std::size_t&max_tree_size);

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

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

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

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

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

template<typenameH_Alpha>
 staticvoidpush_front(constnode_ptr&header,constnode_ptr&new_node,
                        std::size_ttree_size,H_Alphah_alpha,
                        std::size_t&max_tree_size);

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

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

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

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

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

template<typenameKeyType,typenameKeyNodePtrCompare>
 staticstd::pair<node_ptr,bool>
 insert_unique_check(constconst_node_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(constconst_node_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» только в том случае, если из набора больше не вставлены или не стерты объекты.

template<typenameH_Alpha>
 staticvoidinsert_unique_commit(constnode_ptr&header,
                                  constnode_ptr&new_value,
                                  constinsert_commit_data&commit_data,
                                  std::size_ttree_size,H_Alphah_alpha,
                                  std::size_t&max_tree_size);

Требуется: "заголовок" должен быть узлом заголовка дерева. "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».

template<typenameNodePtrCompare,typenameH_Alpha,typenameAlphaByMaxSize>
 staticbooltransfer_unique(constnode_ptr&header1,NodePtrComparecomp,
                             std::size_ttree1_size,
                             std::size_t&max_tree1_size,
                             constnode_ptr&header2,constnode_ptr&z,
                             std::size_ttree2_size,
                             std::size_t&max_tree2_size,H_Alphah_alpha,
                             AlphaByMaxSizealpha_by_maxsize);

Требуется: заголовкиидолжны быть заголовками деревьевисоответственно, z незаголовочного узла. NodePtrCompare - функция сравнения дерева1..

Эффекты: Переносит узел «z» с дерева1 на дерево2, если дерево1 не содержит узел, эквивалентный z.

Возвращает: Верно, если узел был трассферирован, ложно иначе.

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

Бросает: Если сравнение падает.

template<typenameNodePtrCompare,typenameH_Alpha,typenameAlphaByMaxSize>
 staticvoidtransfer_equal(constnode_ptr&header1,NodePtrComparecomp,
                            std::size_ttree1_size,
                            std::size_t&max_tree1_size,
                            constnode_ptr&header2,constnode_ptr&z,
                            std::size_ttree2_size,
                            std::size_t&max_tree2_size,H_Alphah_alpha,
                            AlphaByMaxSizealpha_by_maxsize);

Требуется: заголовок1 и заголовок2 должны быть заголовками деревьев tree1 и tree2 соответственно, z незаголовочного узла tree1. NodePtrCompare - функция сравнения дерева1..

Эффекты: Переносит узел «z» с дерева1 на дерево2.

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

Бросает: Если сравнение падает.

staticboolis_header(constconst_node_ptr&p);

Требуется: p - узел дерева.

Эффекты: Возвращается истинно, если p - заголовок дерева.

Сложность:

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

staticvoidrebalance(constnode_ptr&header);

Требуется: p - узел дерева.

Эффекты: Возвращается истинно, если p - заголовок дерева.

Сложность:

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