In the previous chapter, we implemented several generic algorithms that operated on containers. Consider one of those algorithms again:

    template<typename Container>
    void double_each_element(Container& arr) 
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      }
    }

This algorithm is defined in terms of the lower-level operations .size() and .at(). This works reasonably well for a container type such as array_of_ints or std::vector, but it doesn't work nearly so well for, say, a linked list such as the previous chapter's list_of_ints:

    class list_of_ints {
      struct node {
        int data;
        node *next;
      };
      node *head_ = nullptr;
      node *tail_ = nullptr;
      int size_ = 0;
    public:
      int size() const { return size_; }
      int& at(int i) {
        if (i >= size_...

In the absence of any abstraction, how does one normally identify an element of an array, an element of a linked list, or an element of a tree? The most straightforward way would be to use a pointer to the element's address in memory. Here are some examples of pointers to elements of various data structures:

To iterate over an array, all we need is that pointer; we can handle all the elements in the array by starting with a pointer to the first element and simply incrementing that pointer until it reaches the last element. In C:

    for (node *p = lst.head_; p != nullptr; p = p->next) {
      if (pred(p->data)) {
        sum += 1;
      }
   }

But in order to efficiently iterate over a linked list, we need more than just a raw pointer; incrementing a pointer of type node* is highly unlikely to produce a pointer to the next node in the list! In that case...

There's just one more complication to consider, before we abandon this list iterator example. Notice that I quietly changed our count_if function template so that it takes Container& instead of const Container&! That's because the begin() and end() member functions we provided are non-const member functions; and that's because they return iterators whose operator* returns non-const references to the elements of the list. We'd like to make our list type (and its iterators) completely const-correct--that is, we'd like you to be able to define and use variables of type const list_of_ints, but prevent you from modifying the elements of a const list.

The standard library generally deals with this issue by giving each standard container two different kinds of iterator: bag::iterator and bag::const_iterator. The non-const member function...

Now that we understand the fundamental concept of an iterator, let's put it to some practical use. We've already seen that if you have a pair of iterators as returned from begin() and end(), you can use a for-loop to iterate over all the elements of the underlying container. But more powerfully, you can use some pair of iterators to iterate over any sub-range of the container's elements! Let's say you only wanted to view the first half of a vector:

    template<class Iterator>
    void double_each_element(Iterator begin, Iterator end) 
    {
      for (auto it = begin; it != end; ++it) {
        *it *= 2;
      } 
    }

    int main() 
    {
      std::vector<int> v {1, 2, 3, 4, 5, 6};
      double_each_element(v.begin(), v.end());
        // double each element in the entire vector
      double_each_element(v.begin(), v...

Let's revisit the count and count_if functions that we introduced in
Chapter 1, Classical Polymorphism and Generic Programming. Compare the function template definition in this next example to the similar code from that chapter; you'll see that it's identical except for the substitution of a pair of Iterators (that is, an implicitly defined range) for the Container& parameter--and except that I've changed the name of the first function from count to distance. That's because you can find this function, almost exactly as described here, in the Standard Template Library under the name std::distance and you can find the second function under the name std::count_if:

    template<typename Iterator>
    int distance(Iterator begin, Iterator end) 
    {
      int sum = 0;
      for (auto it = begin; it != end; ++it) {
        sum += 1...

We can imagine even weaker concepts than ForwardIterator! For example, one useful thing you can do with a ForwardIterator is to make a copy of it, save the copy, and use it to iterate twice over the same data. Manipulating the iterator (or copies of it) doesn't affect the underlying range of data at all. But we could invent an iterator like the one in the following snippet, where there is no underlying data at all, and it's not even meaningful to make a copy of the iterator:

    class getc_iterator {
      char ch;
    public:
      getc_iterator() : ch(getc(stdin)) {}
      char operator*() const { return ch; }
      auto& operator++() { ch = getc(stdin); return *this; }
      auto operator++(int) { auto result(*this); ++*this; return result; }
      bool operator==(const getc_iterator&) const { return false; }
      bool operator!=(const...

Putting together everything we've learned in this chapter, we can now write code like the following example. In this example, we're implementing our own list_of_ints with our own iterator class (including a const-correct const_iterator version); and we're enabling it to work with the standard library by providing the five all-important member typedefs.

    struct list_node {
      int data;
      list_node *next;
    };

    template<bool Const>
    class list_of_ints_iterator {
      friend class list_of_ints;
      friend class list_of_ints_iterator<!Const>;

      using node_pointer = std::conditional_t<Const, const list_node*,
        list_node*>;
      node_pointer ptr_;

      explicit list_of_ints_iterator(node_pointer p) : ptr_(p) {}
    public:
      // Member typedefs required by std::iterator_traits
      using difference_type...

You might be wondering: "Every iterator class I implement needs to provide the same five member typedefs. That's a lot of boilerplate--a lot of typing that I'd like to factor out, if I could." Is there no way to eliminate all that boilerplate?

Well, in C++98, and up until C++17, the standard library included a helper class template to do exactly that. Its name was std::iterator, and it took five template type parameters that corresponded to the five member typedefs required by std::iterator_traits. Three of these parameters had "sensible defaults," meaning that the simplest use-case was pretty well covered:

    namespace std {
      template<
        class Category,
        class T,
        class Distance = std::ptrdiff_t,
        class Pointer = T*,
        class Reference = T&
      > struct iterator {
        using...

In this chapter, we've learned that traversal is one of the most fundamental things you can do with a data structure. However, raw pointers alone are insufficient for traversing complicated structures: applying ++ to a raw pointer often doesn't "go on to the next item" in the intended way.

The C++ Standard Template Library provides the concept of iterator as a generalization of raw pointers. Two iterators define a range of data. That range might be only part of the contents of a container; or it might be unbacked by any memory at all, as we saw with getc_iterator and putc_iterator. Some of the properties of an iterator type are encoded in its iterator category--input, output, forward, bidirectional, or random-access--for the benefit of function templates that can use faster algorithms on certain categories of iterators.

If you're defining your...