迭代和遍历有什么区别?

问题描述 投票:0回答:6

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

c++ data-structures iteration terminology traversal
6个回答
29
投票

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

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

for
循环)。

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

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

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


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

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


5
投票

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

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

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


5
投票

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

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

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


3
投票

我将

iterator
称为“代理”,将
traverse
称为“行动”。实际上,当人们将某物上的
traversing
称为某物上的
iterating
时,我常常感到困惑(因为对我来说
iteration
与通过迭代收敛到数学点的数值方法有关)。另一方面,即使我也可以互换使用这些词。

您不能对没有

iterate
概念的容器进行
traversal
操作。至少,为了
traverse
某件事,你至少需要知道你是否有邻居,以及如何到达它。


2
投票

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

traversing
iterating
称为同义词。有
iterators
,但是我不会编程
traversers

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

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


0
投票

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

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

所以

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

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

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

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

for
循环的迭代可以是对某些内容的遍历,但是您可以像在
while
do while
循环中一样迭代每个块,而无需遍历任何内容。

© www.soinside.com 2019 - 2024. All rights reserved.