过去几周我一直在学习迭代器。我仍然不明白迭代链接列表和遍历链接列表之间的主要区别。我知道遍历意味着遍历(访问每个元素)链接列表,并且在迭代时基本上做同样的事情,但是有什么不同,为什么不能遍历所有内容(标准库数据结构)?
“遍历”仅意味着遍历数据结构的(全部或部分)元素。
从历史上看,计算机科学中的“迭代”是一种特殊形式的递归,不需要额外的堆栈空间1——换句话说,尾递归。这种形式在计算上完全等同于我们现在俗称的“迭代”,即有限循环(例如具有固定下限和上限的
for
循环)。
现在,这使得迭代特别适合(与一般递归相比)遍历线性数据结构2。请注意,它不适用于所有容器(例如一般图),因为在这里您需要记住已经访问过的节点(例如使用深度优先搜索,它是根据相邻节点递归定义的,而不是通过C++ 迭代器的概念)。
正是在这种情况下,术语“迭代”在应用于容器的 C++ 中使用。
总而言之:并非每次遍历都是一次迭代,但每次迭代(在数据结构上)都是一次遍历。然而,值得注意的是,许多人没有做出这样的区分,而是互换使用这些术语。
1 特别是这是 SICP 名声大噪的 Gerald Sussman 的用法。
2 但是,看似非线性的数据结构(例如树)可以通过应用右手定则(沿墙算法)出于迭代目的而线性化,因此可以无需堆栈进行遍历。
据我所知,它们是同义词。是什么让您认为有差异?
我觉得;)“遍历”有时被用来表示内部结构被利用。您可以通过从父节点到子节点来遍历树,或者通过跟随下一个指针来遍历列表。
另一方面,您迭代的是一个数组。您已经拥有所有要素,只需一一完成它们即可。
注意:我刚刚提出了这个定义,但它符合我的心理模型,所以我就采用它。
迭代是离散的,遍历可能是离散的,也可能不是。因此,您可以遍历扬声器上模拟音量旋钮上允许的音量范围,但无法迭代它们。
但是迭代是一种遍历。所以每次迭代都是一次遍历,但并不是每次遍历都是一次迭代。
我将
iterator
称为“代理”,将 traverse
称为“行动”。实际上,当人们将某物上的 traversing
称为某物上的 iterating
时,我常常感到困惑(因为对我来说 iteration
与通过迭代收敛到数学点的数值方法有关)。另一方面,即使我也可以互换使用这些词。
您不能对没有
iterate
概念的容器进行 traversal
操作。至少,为了traverse
某件事,你至少需要知道你是否有邻居,以及如何到达它。
迭代器基本上为您提供了遍历数据结构的功能 - 访问每个元素。我将
traversing
和 iterating
称为同义词。有iterators
,但是我不会编程traversers
。
and why cannot you iterate through everything(STL datastructures)?
某些数据结构没有允许这样做的信息。例如,在堆栈上,您不应该能够遍历所有元素,因为您只能访问堆栈的顶部。
遍历:遍历并考虑或讨论主题的整个范围。 通过考虑或讨论主题的整个范围的一系列可行的动作来穿越或延伸。 基本上浏览一个主题的项目。
Iterate:重复执行一个操作,将其应用于上一次应用的结果。
所以
根据定义,traverse并不关心你正在经历的方式或内容,只关心你涵盖了整个主题(但不一定涵盖上下文中的每个项目)。 迭代重复一个过程,可以应用于遍历的每个步骤。
或
对于任何有条目集合的主题:
注意:迭代不是一种遍历,它本质上是一种重复的动作。例如,
for
循环的迭代可以是对某些内容的遍历,但是您可以像在while
或do while
循环中一样迭代每个块,而无需遍历任何内容。