CS 70

What Is An Iterator?

  • Hedgehog speaking

    My head is spinning a bit. What exactly is an iterator?

  • LHS Cow speaking

    Okay, let's break it down two ways: how iterators work in C++, and a more abstract view of the general concept.

  • RHS Cow speaking

    But first let's try to define an iterator in a couple of sentences.

Fundamentally, an iterator is an object that represents the location of one item in a collection of items (such as a list). We can move the iterator around to visit all the items in the collection and access their values.

Most Concretely: What Is An Iterator in C++?

In C++, an iterator is any type which will support the following kind of loop:

for (auto i = start_point; i != past_the_end_point; ++i) {
    ... *i ...
}
  • Cat speaking

    So, pointers are a kind of iterator?

  • LHS Cow speaking

    Yes, and a very common one.

  • RHS Cow speaking

    But they aren't the only kind of iterator. Any class that we define that supports the necessary operations is also an iterator.

So:

  • Iterators need to be initialized to some starting point—the begin() member function provides that value.
  • ++ moves the iterator forward through the data structure.
  • * accesses the element the iterator is currently referring to.
  • != is used to see if we've run off the end and should stop.
    • != needs a special “past the end” value to compare against—the end() member function provides that value.

That's it.

  • Bjarne speaking

    Iterators also typically support == for symmetry, and the -> operator, too.

  • LHS Cow speaking

    True.

  • Bjarne speaking

    Also, technically, the operations above are the ones for a forward iterator. C++ has other kinds of iterators as well; for example, bidirectional iterators provide --i as well, and random access iterators provide + and - operations. And…

  • LHS Cow speaking

    Thank you, yes. All true. But let's just focus on the basics—forward iterators— for now.

Iterators are designed to “look like” a pointer moving through an array, but two key things to remember are:

  • Although every pointer type could be used as an iterator for an array (e.g., a double* is the iterator for an array of doubles), it's important to realize that…
  • Not all iterators are pointers or refer to array elements (specifically, iterators for data structures that are not primitive arrays are custom classes, not pointers).
  • Hedgehog speaking

    I still don't know why you made them look like pointers. It just seems confusing.

  • Dog speaking

    I think it's cool!!

  • Alien speaking

    I suspect that you, canine creature, are easily pleased.

More Abstractly: What Are the Fundamental Iterator Operations?

Iterators are a general concept that exist beyond C++. Abstractly, independent of C++ specifics, an iterator needs to do these operations:

  • BEGIN(data): initializes an iterator to some starting point in data.
  • NEXT(iter): move the iterator forward through the data structure
  • FETCH(iter): access the piece of data the iterator is currently referring to
  • IS-DONE(iter): determine whether the iterator has reached its end point

That's the idea in broad strokes. Different languages implement these fundamental ideas in slightly different ways (of course). Here are some examples of how iterators look in different languages:

  • In Java,

    • BEGIN(myList) is performed using i = myList.iterator()
    • IS-DONE(i) is performed by saying !i.hasNext()
    • NEXT and FETCH operations are combined in an i.next() which both returns the value the iterator refers to and advances the iterator.

  • In Python,

    • BEGIN is performed using i = iter(myList)
    • NEXT, FETCH, and IS-DONE are all combined in the next() method on iterators, which returns the value it found and also either advances the iterator or throws a StopIteration exception if it has gone off the end.

  • In Swift,

    • BEGIN is performed using i = myList.makeIterator()
    • NEXT, FETCH, and IS-DONE are combined in the next() method on iterators, which returns an Optional value—it either returns the value it found and advances the iterator, or returns no value (nil) if it has gone off the end.

Rust's iterators are quite similar to Swift's, and JavaScript and Lua also have iterators.

  • Hedgehog speaking

    So none of these other languages make iterators that look like pointers!

  • LHS Cow speaking

    That's true.

  • RHS Cow speaking

    But C++ goes all in on iterators, with many kinds.

  • Bjarne speaking

    Technically, these other languages are mostly just providing forward iterators, and, specifically, input iterators, where we can read data but not write it. Much more limited.

 

  • Goat speaking

    I don't remember ever seeing any iterators when I coded in Python.

  • Python speaking

    Actually, they're there. Just hidden. If you used a for loop in Python, it was almost certainly using an iterator behind the scenes.

(When logged in, completion status appears here.)