Key Points

Iterators

• An iterator is an object that represents a “location” in a collection (a.k.a. container).

  • It can get/set the item at that location, and move forward to the next location.
  • Provides a unified interface for iteration in lots of data structures.
  • Allows a data structure to define the best way to iterate through its items.

• Other languages also have iterators, so they are a general concept; not C++ specific.

• C++'s iterators are inspired by the begin/past-the-end scheme for iterating over an array.

• In the C++ standard library, a container provides the following functions:

  • begin—returns an iterator to the first item, and
  • end—returns an iterator "one past" the last item.
    • We use the end iterator to know when we've gone too far in a loop!
  • It must be the case that…
    • If i is an iterator to the last item in c, then ++i == c.end(), and
    • A container c is empty if and only if c.begin() == c.end().

• In the C++ standard library, an iterator offers the following operations:

• *iter — returns a reference to the item at the iterator's location.

  • ++iter — advances the iterator to the next location.
  • iter != otherIter — returns true if the two iterators are not at the same location.

• "Iterator" is not another word for "pointer".

  • Both iterators and pointers abstractly represent a concept of “location” and allow access to the data at a location.
  • A pointer is the iterator type for a primitive array.
  • An iterator might have a pointer as a member to help it do its job.
  • But an iterator object has data and member functions, whereas a pointer is just a primitive type representing a memory address.

• Common idioms for looping through a collection using an iterator:

  for (std::vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
      std::cout << *iter << std::endl;
  }
  

  or

  for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
      std::cout << *iter << std::endl;
  }
  

  or

  for (int x : vec) {
      std::cout << x << std::endl;
  }
  

• Read-only iterators are a distinct type where operator* returns a const reference rather than a non-const reference. They're usually called const_iterator rather than iterator.

C++'s Sequence Containers

We also learned about std::vector and std::list in C++'s standard library. They are both examples of sequence containers (a.k.a. lists), and they're both generic in that they can hold a type of our choosing.

• std::list<T> is a doubly linked list with list items of type T.
• std::vector<T> is an array-backed list with array elements items of type T and automatic resizing.

Both are full-featured list objects, with useful member functions well-suited to their underlying representations (a.k.a. encodings).

(When logged in, completion status appears here.)

Previous Page Next Page