В чем разница между итерацией и обходом?
Последние несколько недель я изучал итераторы. Я до сих пор не понимаю основного различия между итерацией по списку ссылок и прохождением по нему. Я знаю, что обход означает прохождение (посещение каждого элемента) списка ссылок, и при итерации вы в основном делаете одно и то же, но что отличается, и почему вы не можете выполнять итерацию по всему (стандартные структуры данных библиотеки)?
Решение
«Обход» означает просто прохождение (всех или некоторых) элементов структуры данных.
Исторически «итерация» в информатике — это особая форма рекурсии, для которой не требуется дополнительное пространство в стеке.1 — другими словами, хвостовая рекурсия. Эта форма в вычислительном отношении в точности эквивалентна тому, что мы теперь в разговорной речи называем «итерацией», а именно конечным циклом (таким как for петля с фиксированной нижней и верхней границей).
Теперь это делает итерацию особенно подходящей (по сравнению с общей рекурсией) для обхода линейных структур данных2. Обратите внимание, что это не работает для все контейнеры (например, общие графики), потому что здесь вам нужно запомнить уже посещенные узлы (например, используя поиск в глубину, который определяется рекурсивно в терминах смежных узлов, а не через концепцию итераторов C ++).
Именно в этом контексте термин «итерация» используется в C ++ применительно к контейнерам.
Итак, не каждый обход является итерацией, но каждая итерация (по структуре данных) является обходом. Однако стоит отметить, что многие люди не проводят такого различия и используют термины взаимозаменяемо.
1 В частности, это использование Джеральда Суссмана из SICP известность.
2 Но, казалось бы, нелинейные структуры данных, такие как деревья, могут быть линеаризованы с целью итерации, применяя Правило правой руки (алгоритм следования за стеной) и, таким образом, может быть пройден без стек.
Другие решения
Примечание: я только что сформулировал это определение, но оно соответствует моей ментальной модели, поэтому я продолжу.
Итерация дискретна, обход может или не может быть. Таким образом, вы можете перемещаться по диапазону допустимых уровней громкости на аналоговой ручке громкости на вашем громкоговорителе, но вы не можете перебирать их.
Но итерация — это тип обхода. Таким образом, каждая итерация является обходом, но не каждый обход является итерацией.
AFAIK они являются синонимами. Что заставляет вас думать, что есть разница?
Я чувствую;) что «траверса» иногда используется, чтобы указать, что внутренняя структура эксплуатируется. Вы пересекаете дерево, переходя от родительских узлов к дочерним, или пересекаете список, следуя следующим указателям.
Массив, с другой стороны, вы перебираете. У вас есть все элементы, просто проработайте их один за другим.
Я бы позвонил iterator «агент» и traverse Действие». На самом деле, меня часто смущает, когда люди обращаются к traversing над чем-то, как iterating за что-то (потому что для меня iteration связан с численными методами, которые сходятся к математической точке с помощью итерации). С другой стороны, даже я использую слова взаимозаменяемо.
Ты не можешь iterate над контейнерами, для которых нет понятия traversal, Как минимум, чтобы traverse Что-то, нужно знать хотя бы, есть ли у тебя сосед и как к нему добраться.
Итератор в основном дает вам функциональность для прохождения через структуру данных — посещение каждого элемента. Я бы позвонил traversing а также iterating синонимы. Есть iteratorsно я не знаю traversers в программировании.
and why cannot you iterate through everything(STL datastructures)?
Некоторые структуры данных не имеют информации, позволяющей это сделать. Например, в стеке вы не сможете пройти через все элементы, потому что вы можете получить доступ только к вершине стека.