迭代和遍历有什么区别？

Question

在过去的几周中，我一直在学习迭代器。我仍然不明白在遍历链接列表和穿行其中之间的主要区别。我知道遍历意味着浏览（访问每个元素）链接列表，而当迭代时，您基本上做了同样的事情，但有什么不同，为什么不能通过一切（标准库数据结构）进行迭代？

- FJam

---

“迭代器”是指用于“遍历”容器的东西。 - Escualo

Answer 1

"遍历"只是指遍历数据结构中的所有或部分元素。

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

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

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

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

---

¹ 特别是杰拉尔德·萨斯曼（Gerald Sussman）在SICP中的用法。

² 但是，看似非线性的数据结构，例如树，可以通过应用右手法则（墙跟随算法）进行线性化以便进行迭代，并因此可以在没有堆栈的情况下遍历。

- Konrad Rudolph

---

不是每个遍历都是迭代。你有例子吗？ - typ1232

@misteryeti 嗯，你实际上可以遍历树，因为它们具有良好定义的结构（并非所有图都是树！），但这需要一些非平凡操作。我实际上不知道标准库如何实现这一点…但由于标准库的复杂性要求，我期望标准库树迭代器实际上确实进行迭代。 - Konrad Rudolph

但是这样你也无法遍历图！这就是我的观点。 - typ1232

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/29271/discussion-between-mister-yeti-and-konrad-rudolph - typ1232

+1，我喜欢遍历是一个更通用的术语，而迭代则用于具有自然顺序视图的数据结构的想法。 - Sebastian Redl

Answer 2

注意：我只是自己编了这个定义，但它符合我的心理模型，所以我就采用它。

迭代是离散的，遍历可以是离散的也可以不是。因此，你可以遍历扬声器上模拟音量旋钮的允许范围，但不能对其进行迭代。

但迭代是遍历的一种类型。因此，每次迭代都是一次遍历，但并非每次遍历都是迭代。

- Benjamin Lindley

Answer 3

据我所知，它们是同义词。您为什么认为有区别呢？

我感觉 ;)，“遍历”有时用于指示利用内部结构。你通过从父节点到子节点遍历树，或者通过跟随下一个指针遍历列表。

另一方面，数组可以迭代。您拥有所有的元素，只需要逐个处理即可。

- Sarien

---

@FJam，我非常确定它们没有区别。 - Mooing Duck

Answer 4

我会称呼iterator为“代理”，称呼traverse为“操作”。实际上，当人们讲述在某些东西上进行traversing时，常常把它和在某些东西上进行iteration混淆（因为对我而言，iteration是指数值方法，通过迭代收敛于数学点）。但另一方面，我也经常混用这两个词。

如果容器没有traversal的概念，则无法在其上进行iteration。至少，要遍历某些东西，你需要知道是否有邻居以及如何到达它。

- Escualo

Answer 5

迭代器基本上为您提供了遍历数据结构的功能 - 访问每个元素。我会将 traversing 和 iterating 视为同义词。有 iterators，但是我不知道编程中的 traversers。

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

一些数据结构没有提供此类信息。例如，在堆栈上，您不应该能够遍历所有元素，因为您只能访问堆栈的顶部。

- typ1232

---

所以它们基本上是一样的吗？ - FJam

迭代器是一种帮助您遍历某些内容的对象。我认为“遍历”和“迭代”是同义词。在编程中有迭代器，但我不知道是否有“遍历器”。 - typ1232