Имеет ли смысл реализовывать итераторы для контейнеров, которые не имеют очевидного конца - напримердеревья?
https://stackoverflow.com/questions/1207478
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пишу шаблон бинарного дерева поиска по двум причинам - изучаю C ++ и наиболее распространенные алгоритмы и структуры данных.
Итак, вот в чем вопрос - пока я хочу реализовать итераторы, мне кажется, что нет строгого определения того, где заканчивается дерево.Каковы ваши предложения?Как мне это сделать?
Решение
Для деревьев существуют стандарты обхода дерева, то есть перечисления узлов: обход по предварительному заказу, обход по порядку и обход по порядку. Вместо того, чтобы описывать все это здесь, я перенаправлю вас на http://en.wikipedia.org/wiki/Tree_traversal . Концепции в основном применяются к бинарным деревьям, но вы можете распространить идею на произвольные деревья, добавив больше случаев: эффективно обработать узел, затем выполнить рекурсию, выполнить повторную обработку, затем обработать узел, обработать все дочерние элементы, затем выполнить рекурсию в каждое ... и т. Д. Я не знаю никакой канонической классификации этого подхода.
Другие советы
При написании итератора нужно что-то прояснить - итератор для структуры данных обеспечивает доступ к коллекции в виде линейной последовательности элементов. Некоторые коллекции, такие как массивы, списки и очереди, естественно совместимы с обработкой как линейная последовательность. Другие типы коллекций - деревья, словари, графики - не обязательно имеют простую интерпретацию как линейный список. На самом деле, множественные интерпретации в целом действительны.
Что вы действительно делаете при написании итератора для коллекции, такой как дерево, - это решение следующих проблем:
<Ол>Что бы вы ни выбрали, вы должны четко понимать, как вы называете (и документируете) свой итератор, чтобы было понятно, как он будет посещать и излучать узлы.
Возможно, вам потребуется написать несколько итераторов для разных типов путешествий, которые вы намереваетесь поддерживать. Здесь есть несколько хороших статей, которые обсуждают = nMJxSs6CMJKcMaOsubEM & usg = AFQjCNFYiakxxRqG2mq_MLT6vE2oDwyq3g & sig2 = 9zSF_sM3PpRcMt5IY5mbdQ "rel =" nofollow noreferrer <>>aa.
Если под "строгим" вы подразумеваете:единого всеобъемлющего определения, вы правы, такового не существует.
Но "конец" для деревьев очень хорошо определен, хотя и зависит от выбранного вами метода обхода.
- Если вы выполняете обход по порядку (или симметрично), крайний правый элемент будет
end. - в предварительном порядке (или в первую очередь по глубине) крайним правым элементом будет
end, и т.д. - в postorder корневым элементом будет
end, и т.д.
Наиболее распространенный обход дерева методы.
Ваше определение итератора немного неверно. Итераторы не переходят от start к finish и front к back . Вместо этого они пересекают всех членов этой структуры.
Если вы попросите выполнить итерацию по упорядоченной структуре, то есть массиву, связанному списку и т. д., вы (как правило) вернете своих членов по порядку.
Для неупорядоченных элементов, например, набора, вы получите их в любом порядке, который итератор набора хочет вам предоставить, но вы получите их все по одному, точно так же, как вы это сделаете с массивом-итератором.
Что касается деревьев, другие люди уже упоминали: у них есть четко определенные понятия общего порядка, вам нужно просто выбрать один:)
Это зависит от того, что вы хотите сделать с деревом - возможно, было бы неплохо иметь, например, итераторы Breadth-First-Search или Depth-First-Search (или оба).
Если у вас есть какой-то особый способ обыскивать дерево, то в действительности у вас есть начало и конец. Это не так очевидно, как линейные отношения в списках и наборах, но оно есть, если вы хотите наложить на него некоторый порядок.
Это имеет смысл особенно в подобных случаях, потому что дает пользователям вашего класса возможность легко обходить все элементы различными способами, в зависимости от ситуации. Без них пользователи должны сами писать сложными, обычно рекурсивными способами. По сравнению, например, с векторы, в которых итераторы набирают больше, чем используют для (i = 0; i
Я думаю, что в итераторе более абстрактно. Я не вижу в шаблоне итератора ничего, что действительно говорит о начале или конце! Так почему же ограничиваться этим видением. Мы можем представить себе итератор, который касается только следующего элемента, вот и все. Я имею в виду, что я сталкивался (особенно в массовой обработке) с ситуациями, когда с самого начала мы не знаем расширение коллекции, мы не знаем, закончится ли она когда-нибудь, или у нас нет всех их элементы загружаются в память, и нам все равно. Мы заботимся только о получении следующего элемента. В одной из этих реализаций следующий узел создается сразу после вызова метода следующего элемента. Мы можем открыть свои умы и думать о бесконечных коллекциях (в конце концов, коллекция - это тип математического набора), таких как коллекции всех чисел, коллекция всех случайных чисел. Вам не обязательно иметь все элементы в памяти (это очевидно для бесконечных коллекций). Конечно, это не практические примеры, но мое сообщение таково, что пользователю Итератора не нужно полагаться на фактическую структуру или расширение коллекции. ПРОСТО ДАЙ МНЕ СЛЕДУЮЩЕЕ (ЕСЛИ ТЫ ЕСТЬ).
