С++: время выполнения next() и prev() в многозадачном итераторе?

Какова временная сложность применения функции next() и prev() для объекта типа multiset<int>::iterator, где соответствующий мультимножество содержит элементы N?

Я понимаю, что в STL мультимножество реализовано как сбалансированное двоичное дерево поиска, и поэтому я ожидаю, что временная сложность будет равна O (log N) за операцию (в худшем случае), если мы просто пересечем дерево до тех пор, пока мы найдите соответствующее значение, но у меня есть догадка, что это должно быть O (1) в среднем.

Но что, если дерево реализовано следующим образом: при вставке элемента x в сбалансированное двоичное дерево поиска мы также можем получить наибольшее число в дереве, меньшем, чем x, и наименьшее число в дереве больше x в O (log N). Таким образом, теоретически мы можем иметь каждый node в дереве поддерживать указатель на его элементы next и prev, чтобы next() и prev() выполнялись в постоянное время для каждого запроса.

Кто-нибудь может рассказать о том, что?

Ответ 1

В стандарте указывается, что все операции с итераторами выполняются в режиме амортизированного постоянного времени: http://www.eel.is/c++draft/iterator.requirements#general-10. Основная идея заключается в том, что каждая категория итераторов определяет только операции, которые могут быть реализованы в амортизированном времени.

Итерация - это обычная вещь, и если operator++ на итераторе (я предполагаю, что то, что вы подразумеваете под следующим?), было logN, тогда перемещение контейнера в цикле было бы NlogN. Стандарт делает это невозможным; поскольку operator++ амортизируется постоянной, итерация по любой структуре данных в стандарте всегда равна O (N).

Однако я применил реализацию multiset в gcc5.4, чтобы хотя бы один пример. Оба set и multiset реализованы в рамках одной и той же базовой структуры, _Rb_tree. Введя немного в эту структуру, узлы имеют не только указатели слева и справа node, но также родительский указатель node, а итератор - это просто указатель на node.

Учитывая node в двоичном дереве поиска, который содержит указатель на его родительский элемент, легко понять, что следующий node в дереве:

Если у него есть правильный ребенок, спуститесь к правильному ребенку. Затем опускайте левого ребенка насколько это возможно; что следующий node.
Если у него нет правильного ребенка, войдите в родителя и определите, является ли исходный node левым или правым дочерним элементом родителя. Если node является левым дочерним элементом родительского элемента, то родительский является следующим node. Если node является правом родителя, родительский объект уже обработан, поэтому вам необходимо применить рекурсивно одну и ту же логику между родителем и его дедушкой.

Этот вопрос SO показывает исходный код с основной логикой: Что такое определение _Rb_tree_increment в бит /stl _tree.h? (его удивительно сложно найти для некоторых причина).

Это не имеет постоянного времени, в частности, в 1 и 2. у нас есть петли, которые либо спускаются, либо поднимаются и могут занимать не более log (N) времени. Тем не менее, вы можете легко убедить себя, что амортизированное время является постоянным, поскольку, когда вы пересекаете дерево с помощью этого алгоритма, каждый node затрагивается не более 4 раз:

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

В ретроспективе я бы сказал, что это довольно очевидный выбор. Итерация по всей структуре данных является общей операцией, поэтому производительность очень важна. Добавление третьего указателя на node - это не тривиальное количество пространства, но это не конец света; в лучшем случае он раздует структуру данных от 3 до 4 слов (2 указателя + данные, выравнивание которых составляет минимум 3, против 3 указателей + данных). Если вы работаете с диапазонами, в отличие от двух итераторов, альтернативой будет поддерживать стек, а затем вам не нужен указатель родителя, но это работает только в том случае, если вы выполняете итерацию с самого начала до конца; это не позволит итерации от итератора посередине до конца (что также является важной операцией для BST).

Ответ 2

Я думаю, что next() и prev() будут занимать от 1 до h, где h - высота дерева, которая приблизительно равна O (log N). Если вы используете next() для перехода от начала до конца, N узлов, то итератор должен посетить все дерево, а это примерно 2N (2, потому что итератору нужно пройти вниз, а затем вверх через указатели, связывающие узлы). Общий обход не O (N * log N), поскольку некоторые шаги лучше других шагов. В худшем случае следующая() может быть из листа node в голову node, которая равна h приблизительно O (log N). Но это произойдет только дважды (один раз для начала(), второй раз справа node левого дерева в голову node). Таким образом, в среднем next() и prev() равны 2, что равно O (1).