c++ - 迭代和遍历有什么区别？

Question

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

Answer 1

“遍历”只是指遍历数据结构的（全部或部分）元素。

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

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

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

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

---

¹这尤其是SICP声望的 Gerald Sussman 的用法。

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

Answer 2

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

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

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

Answer 3

AFAIK 他们是同义词。是什么让你觉得有区别？

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

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

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)?

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