What is the difference between iteration and traversing?

Question

The past few weeks I have been learning about iterators. I still do not understand the main difference between iterating through a link list and traversing through one. I know that traversing means to go through (visiting every element) the link list, and when iterating you basically do the same thing, but what is different, and why cannot you iterate through everything (standard library data-structures)?

Esdraelon

An iterator is something that traverses a container. – Dotation

Answer 1

“Traversal” just means walking through (all or some) elements of a data structure.

Historically, “iteration” in computer science is a special form of recursion for which no additional stack space is needed¹ – in other words, tail recursion. This form is computationally exactly equivalent to what we now colloquially know as “iteration”, namely a finite loop (such as a for loop with a fixed lower and upper bound).

Now this makes iteration especially well suited (compared to general recursion) for traversing linear data structures². Note that it does not work for all containers (e.g. general graphs) because here you need to remember the already visited nodes (e.g. using depth-first search, which is defined recursively in terms of adjacent nodes, rather than via the C++ concept of iterators).

It is in this context that the term “iteration” is used in C++ applied to containers.

In summary: not every traversal is an iteration but every iteration (over a data structure) is a traversal. However, it’s worth noting that many people make no such distinction and use the terms interchangeably.

---

¹ In particular this is the usage of Gerald Sussman of SICP fame.

² But seemingly non-linear data structures such as trees can be linearised for the purpose of iteration by applying the right-hand rule (wall-following algorithm) and can thus be traversed without a stack.

Identity

not every traversal is an iteration Do you have an example for this? – Expressionism

@misteryeti Yes, and it’s in my answer: breadth-first search. However, depth-first search is a better example since it explicitly uses a stack (or recursion) while BFS often uses a queue instead (but that changes nothing). – Identity

So when implementing a tree class you would say defining an iterator for it would be wrong naming? I know several tree implementations that use iterators. – Expressionism

@misteryeti Well you can actually iterate through trees because of their well-defined structure (not every graph is a tree!) but that requires some nontrivial operations. I have actually no idea how the standard library implements this … but due to the complexity requirements of the standard library I expect that the standard library tree iterators actually do iterate. – Identity

@misteryeti But in fact you could even define iterators for general graphs, by just iterating over the graph’s internal representation (for instance if that representation is an adjacency list. So for practical purposes I see no issue with defining an iterator over a graph. However, without access to the internal representation you cannot in general iterate over a graph, using the strict historical definition. – Identity

But then you could also not traverse the graph! That's my point. – Expressionism

@misteryeti Hmm, I don’t understand that. You can traverse it – using recursion. – Identity

let us continue this discussion in chat – Expressionism

+1, I like the idea that traversal is a more generic term while iteration is used for data structures that have a natural sequential view. – Belittle

every iteration is a traversal: This seems too strong to me -- traversal is with respect to a data structure, while iteration in general does not. As a very simple example, an iterative algorithm to multiply two numbers by repeated addition isn't traversing anything. – Dispersal

@Edward You are right (although you could phrase such an iterative multiplication algorithm in terms of a data structure) - I was actually referring to the usage of the terms in the context of data structures. Valid clarification though. – Identity

Answer 2

AFAIK they are synonymous. What makes you think there is a difference?

I feel ;) that "traverse" is sometimes used to indicate that internal structure is exploited. You traverse a tree by going from parentnodes to childnodes or you traverse a list by following the next pointers.

An array on the other hand you iterate over. You have all the elements, just work through them one by one.

Amphicoelous

@FJam, I'm pretty sure there isn't a difference. – Cuckooflower

Answer 3

Note: I just made this definition up, but it fits my mental model, so I'm going with it.

Iteration is discrete, traversal may or may not be. So, you can traverse the range of allowable volumes on the analog volume knob on your speaker, but you cannot iterate through them.

But iteration is a type of traversal. So every iteration is a traversal, but not every traversal is an iteration.

Johnathanjohnathon

Answer 4

I would call iterator the "agent" and traverse the "action". Actually, it often confuses me when people refer to traversing over something as iterating over something (because to me iteration is related to numerical methods which are converging towards a mathematical point via iteration). On the other hand, even I use the words interchangeably.

You cannot iterate over containers for which there is no concept of traversal. At a minimum, in order to traverse something, you need to know at least whether you have a neighbor, and how to get to it.

Dotation

Answer 5

A iterator basically gives you the functionality to traverse through a datastructure - visiting every element. I would call traversing and iterating synonyms. There are iterators, but I don't know traversers in programming.

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

Some datastructures do not have information that allows this. For example on a stack you should not be able to traverse though all the elements because you can only access the top of the stack.

Expressionism

so they are basically the same? – Esdraelon

An iterator is a object that helps you traverse something. I would call "traversing" and "iterating" synonyms. There are Iterators, but i don't know "Traversers" in programming :) – Expressionism

Answer 6

Traverse: go through and consider or discuss the whole extent of a subject. travel or extend across or through by means of a practicable series of movements that consider or discuss the whole extent of a subject. basically go through the items of a subject.

Iterate: perform an operation repeatedly, applying it to the result of the previous application.

so

by definition, traverse doesn't care how or what you're going through, only that you cover the entire subject (but not necessarily every item in context). iterate repeats a process that can be applied at each step of a traversal.

or

for any subject with a collection of entries:

• traverse: go through the entries and cover the whole subject.
• iterate: repeat a process, which can be for each entry as you traverse something.

Note: iterate is not a type of traversal, it is in essence a repeated action. for example the iteration of a for or foreach loop can be a traversal of something however you can iterate each block like in a while or do while loop that does not need to traverse anything.

Barcelona