Как работает итератор std :: map?
STL-класс C ++ std :: map реализует поиск O (log (n)) с использованием двоичного дерева. Но с деревьями не сразу очевидно, как будет работать итератор. Что на самом деле означает оператор ++ в древовидной структуре? В то время как концепция «следующего элемента» имеет очевидную реализацию в массиве, для меня это не так очевидно в дереве. Как реализовать итератор дерева?
Решение
Для обхода по порядку (вероятно, работает и для других), если у вас есть родительский указатель в ваших узлах, вы можете сделать нерекурсивный обход. Должна быть возможность хранить два указателя в вашем итераторе: вам нужно указать, где вы находитесь, и вам, вероятно, (я сейчас не занимаюсь исследованием) понадобится что-то вроде «предыдущего» указателя, чтобы вы могли понять Ваше текущее направление движения (т.е. мне нужно перейти в левое поддерево или я только что вернулся с него).
«Предыдущая» воля наверное быть что-то вроде «родитель», если мы только что вошли в узел; «left», если мы возвращаемся из левого поддерева, «right», если мы возвращаемся из правого поддерева, и «self», если последний узел, который мы вернули, был нашим собственным.
Другие решения
Рассмотрим набор всех элементов на карте, которые не меньше текущего элемента, которые также не являются текущим элементом. «Следующий элемент» — это элемент из этого набора элементов, который меньше всех других элементов в этом наборе.
Чтобы использовать карту, у вас должен быть ключ. И этот ключ должен реализовывать операцию «меньше чем». Это определяет способ формирования карты так, чтобы операции поиска, добавления, удаления, увеличения и уменьшения были эффективными.
Обычно карта внутренне использует какое-то дерево.