C ++: двоичный поиск дерева end () итератор
У меня есть базовая (без рандомизации, упорядочения и т. Д.) Реализация BST. Я хочу добавить реализации итераторов и сделать BST подходящим для цикла for на основе диапазона.
Поэтому мне нужно функции член функции begin (), end () и увеличение итератора.
Я понимаю, что должна делать begin () — вернуть итератор в самый нижний левый узел и эта тема обсуждает различные возможности обхода BST (= увеличение итератора)
Но end () должен дать итератор элементу «один за последним». И это актуальный вопрос, который я не понимаю, в чем смысл этого в контексте BST?
Решение
Конечный итератор не обязательно должен быть один за последним элементом (это имеет смысл для векторов, но в меньшей степени для деревьев, например.). Это должен быть просто итератор, который может быть четко определен как недопустимый итератор, используемый для указания того, что достигнут конец структуры данных.
На практике это можно сделать несколькими способами, в зависимости от того, как ваш итератор ссылается на то, на что он указывает. Если он использует указатель на узел дерева, например, тогда нулевой указатель может использоваться для конечного итератора.
Другие решения
Очень простая схема, использующая два дополнительных указателя памяти, состоит в том, чтобы просто наложить дважды связанный круговой список поверх BST. Ваш end() Затем итератор просто указывает на сторожевой узел. Это также делает ваш итератор приращением / уменьшением очень простым.
BST::iterator &
BST::iterator::operator++() {
n = n->next;
return *this;
}
и т.д. Обратите внимание, что использование такого стража означает, что end Итератор не требует специальной обработки. Вы можете уменьшить его и получить абсолютно правильное поведение.
Несмотря на мой комментарий, Сандер Де Дайкер имеет правильную идею. У меня есть другой способ думать об этом.
Все контейнеры, которые поддерживают итераторы, имеют логический порядок. За vector порядок основан на том, как были сделаны вставки — порядок индекса / индекса. За map а также set это основано на заказе ключа. За multimap а также multiset это немного того и другого. За unordered_map и т.д. утверждение очень незначительное, но я все еще могу спорить об алгоритмах хеширования и обработке коллизий.
В логическом порядке вы можете ссылаться на упорядоченные элементы, но иногда имеет смысл ссылаться на границы между каждым элементом. Логически (а в некоторых случаях даже для реализации) это получается довольно удобно …
| | | | | | | | |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| | | | | | | | |
0 1 2 3 4 5 6 7 8
Вы сами решаете, куда идет нулевая «граница», независимо от того, куда идет нулевой элемент, но вы всегда получаете простое отношение сложения / вычитания. Если наименьшая граница пронумерована так же, как наименьший элемент, последняя граница пронумерована на один больше, чем последний элемент. следовательно end как один из последних элементов.
В реализации двоичного дерева каждый узел может иметь две границы — по одной с каждой стороны элемента. В этой схеме все, кроме begin а также end происходит дважды. Вы можете представить границу 1, используя RHS элемента 0 или LHS или элемента 1. Таким образом, в принципе вы можете использовать указатель узла и флаг. Вместо того, чтобы иметь два представления для большинства границ, вы, вероятно, выберете наиболее удобный, где это возможно, — тот, в котором вы не просто ссылаетесь на правую границу, но также ссылаетесь на элемент, который хотите видеть при разыменовании. Это означает, что флаг будет установлен только при обращении к end, в этом случае вы не должны поддерживать разыменование в любом случае.
IOW следуя этой логике говорит вам, что вам не нужно следовать этой логике, хотя я думаю, что это все еще полезная ментальная модель. Все, что вам действительно нужно, это идентифицируемое представление для end, Возможно, для этого представления полезно включить указатель на конечный указатель (в качестве отправной точки, например, для уменьшения этого итератора). Возможно, существуют ситуации, когда удобно иметь псевдо-итераторы внутри, которые распознают две эквивалентные границы как разные.
Подобные, но немного отличающиеся модели и варианты возникают, например, при рассмотрении. многоходовые деревья, где каждый узел содержит массив элементов.
По сути, я думаю, что полезно мысленно распознавать связанные позиции как отдельные, но связанные с позициями элементов, но эта ментальная модель не должна ограничивать ваш выбор реализации — она может вдохновлять альтернативы, но это просто ментальная модель.