C++: время выполнения next () и prev() в многосетевом итераторе?

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

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

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

Может ли кто-нибудь пролить свет на то, что происходит?
2 10
c++ algorithm c++11 binary-search-tree

2 ответа:

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

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

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

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

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

Этот вопрос SO показывает исходный код с основной логикой: каково определение _Rb_tree_increment в битах/stl_tree.ч? (это удивительно трудно найти по какой-то причине).

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

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

1