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