迭代和遍历有什么区别？

Question

过去几周我一直在学习迭代器。我仍然不明白迭代链接列表和遍历链接列表之间的主要区别。我知道遍历意味着遍历（访问每个元素）链接列表，并且在迭代时基本上做同样的事情，但是有什么不同，为什么不能遍历所有内容（标准库数据结构）？

Answer 1

“遍历”仅意味着遍历数据结构的（全部或部分）元素。

从历史上看，计算机科学中的“迭代”是一种特殊形式的递归，不需要额外的堆栈空间¹——换句话说，尾递归。这种形式在计算上完全等同于我们现在俗称的“迭代”，即有限循环（例如具有固定下限和上限的

for

循环）。

现在，这使得迭代特别适合（与一般递归相比）遍历线性数据结构²。请注意，它不适用于所有容器（例如一般图），因为在这里您需要记住已经访问过的节点（例如使用深度优先搜索，它是根据相邻节点递归定义的，而不是通过C++ 迭代器的概念）。

正是在这种情况下，术语“迭代”在应用于容器的 C++ 中使用。

总而言之：并非每次遍历都是一次迭代，但每次迭代（在数据结构上）都是一次遍历。然而，值得注意的是，许多人没有做出这样的区分，而是互换使用这些术语。

---

¹ 特别是这是 SICP 名声大噪的 Gerald Sussman 的用法。

² 但是，看似非线性的数据结构（例如树）可以通过应用右手定则（沿墙算法）出于迭代目的而线性化，因此可以无需堆栈进行遍历。

Answer 2

据我所知，它们是同义词。是什么让您认为有差异？

我觉得；）“遍历”有时被用来表示内部结构被利用。您可以通过从父节点到子节点来遍历树，或者通过跟随下一个指针来遍历列表。

另一方面，您迭代的是一个数组。您已经拥有所有要素，只需一一完成它们即可。

Answer 3

注意：我刚刚提出了这个定义，但它符合我的心理模型，所以我就采用它。

迭代是离散的，遍历可能是离散的，也可能不是。因此，您可以遍历扬声器上模拟音量旋钮上允许的音量范围，但无法迭代它们。

但是迭代是一种遍历。所以每次迭代都是一次遍历，但并不是每次遍历都是一次迭代。

Answer 4

我将

iterator

称为“代理”，将

traverse

称为“行动”。实际上，当人们将某物上的

traversing

称为某物上的

iterating

时，我常常感到困惑（因为对我来说

iteration

与通过迭代收敛到数学点的数值方法有关）。另一方面，即使我也可以互换使用这些词。

您不能对没有

iterate

概念的容器进行

traversal

操作。至少，为了

traverse

某件事，你至少需要知道你是否有邻居，以及如何到达它。

Answer 5

迭代器基本上为您提供了遍历数据结构的功能 - 访问每个元素。我将

traversing

和

iterating

称为同义词。有

iterators

，但是我不会编程

traversers

。

and why cannot you iterate through everything(STL datastructures)?

某些数据结构没有允许这样做的信息。例如，在堆栈上，您不应该能够遍历所有元素，因为您只能访问堆栈的顶部。

Answer 6

遍历：遍历并考虑或讨论主题的整个范围。 通过考虑或讨论主题的整个范围的一系列可行的动作来穿越或延伸。 基本上浏览一个主题的项目。

Iterate：重复执行一个操作，将其应用于上一次应用的结果。

所以

根据定义，traverse并不关心你正在经历的方式或内容，只关心你涵盖了整个主题（但不一定涵盖上下文中的每个项目）。 迭代重复一个过程，可以应用于遍历的每个步骤。

或

对于任何有条目集合的主题：

• 遍历：浏览条目并涵盖整个主题。
• 迭代：重复一个过程，可以针对遍历某些内容时的每个条目。

注意：迭代不是一种遍历，它本质上是一种重复的动作。例如，

for

循环的迭代可以是对某些内容的遍历，但是您可以像在

while

或

do while

循环中一样迭代每个块，而无需遍历任何内容。