Iterators

Iterators provide a uniform interface for traversing container data structures.

So far, we have covered a variety of C++ data structures—std::map, std::vector, std::set, std::deque, std::unordered_map, std::unordered_set—all of which have a variety of different implementations behind the scenes—binary search tree, contiguous allocation, array of arrays, hash table. Despite this internal complexity, we are still able to do certain operations on these containers without worrying about how they are implemented behind the scenes. For example, consider this code^[1]:

std::vector<int> container { 1, 2, 3 };

// The for loop below will still work if we had defined container as:
//
//    - std::deque<int> container;
//    - std::map<std::string, int> container;
//    - std::set<int> container;
//    - std::unordered_map<std::string, int> container;
 
for (const auto& elem : container) {
  // Do something with `elem`
}

How does this syntax work? Under the hood, the compiler does a syntactic transformation of the above code into the following:

std::vector<int> container { 1, 2, 3 };

auto begin = std::begin(container);
auto end = std::end(container);

for (auto it = begin; begin != end; ++it) {
  const auto& elem = *it;
  // Do something with `elem`
}

What is std::begin(container)? What is it? As we will see, these are iterators, data types that share the same semantics as pointers and allow generic iteration over a data structure, independent of how that data structure was implemented.

Iterator Basics

Imagine you want to iterate through every element in an std::vector. You might have code that looks like this:

std::vector<std::string> strings { "Bjarne", "Stroustrup", "says" };

for (size_t i = 0; i < strings.size(); i++) {
  const auto& elem = strings[i];
  std::cout << elem << "\n";
}

This code uses an index i to keep track of which element the for loop is currently at. You have likely seen this code many times before, or something like it. Once i is no longer a valid index, we stop looping—otherwise, we increment i at the end of every iteration.

What if we wanted to apply the same kind of loop to an std::set? Recall from the previous chapter that unlike std::vector, std::set does not store its elements sequentially in memory. We also cannot use an integer index to get an element from a set, since it has no operator[]. What we'd like is some kind of construct that allows us to keep track of where we are in a container while iterating, but which can handle more powerful data structures than std::vector.

Container Interface

Roughly speaking, an iterator functions as a pointer to an element in a container. The iterators of a container define a sequence of elements—each iterator knows how to get to the next iterator in the sequence. Every C++ container has built-in methods that return iterators to the beginning and end of its container. These methods are guaranteed to run in constant-time.

Note that c.end() is a past-the-end iterator—it doesn't actually point to any element of the container, but is instead one past the last element of the container. This helps us to build looping logic and represent empty containers. Consider the following set and its iterators:

std::set<int> s { 1, 2, 3, 4, 5 };
auto begin = s.begin();
auto end = s.end();

Note that an empty container has c.begin() and c.end() pointing to the same (non-existent) element:

std::set<int> s;
auto begin = s.begin();
auto end = s.end();

Iterator Interface

Iterators, on the other hand, all provide a simple set of operations to allow traversing through a container. Like the container methods, these are also required to run in constant-time.

Be careful not to increment an iterator past the end (e.g. ++c.end()) or try to dereference the end iterator (*c.end()). Both of these are undefined behaviour in C++!

Putting both the container and iterator interfaces together, try reasoning through what this code to iterate through a container is doing now:

std::vector<int> container { 1, 2, 3 };

auto begin = std::begin(container);
auto end = std::end(container);

for (auto it = begin; begin != end; ++it) {
  const auto& elem = *it;
  // Do something with `elem`
}

If you have read and are familiar with the chapter on pointers, you might notice that semantics of iterators are very similar to that of pointers. Iterators, like pointers, can be dereferenced, incremented, compared, etc. In some sense, iterators are a generalization of pointers to memory that is not necessarily sequential. This allows more complex data types, such as unordered_map, to seem as if their elements are represented sequentially in memory.

Note: You may notice in this chapter that we use ++it instead of it++ when incrementing iterators. To see why, it can help to look at the call signatures of these two versions and how they differ:

/** The prefix form, e.g. ++it */
Iterator& operator++() {
  /*
   * Code that moves this iterator to the next element
   */
  return *this;
}

/** The postfix form, e.g. it++
 *
 * Note the `int` in the signature exists only to differentiate
 * from the above method. 
 */
Iterator operator++(int) {
  Iterator prev = *this;    // Save a copy the iterator's current state
  ++*this;                  // Move the iterator forward using the prefix form above
  return prev;              // Return the **old** state!
}

/** The prefix form, e.g. ++it */ Iterator& operator++() { /* * Code that moves this iterator to the next element */ return *this; } /** The postfix form, e.g. it++ * * Note the `int` in the signature exists only to differentiate * from the above method. */ Iterator operator++(int) { Iterator prev = *this; // Save a copy the iterator's current state ++*this; // Move the iterator forward using the prefix form above return prev; // Return the **old** state! }

Copy

In particular, the prefix form (++it) updates an iterator in-place, returning a reference to the same iterator. The postfix form (it++) still updates the iterator, but returns a copy of the old value of the iterator before it was incremented. For this reason, it++ can be a bit slower than ++it because an extra copy is created^[2].

Iterator Types

So far, we have used auto to let the compiler deduce the type of, for example, c.begin(). What actually is the type of an iterator? This will depend on the container, but generally speaking, given a container type C, its iterator type will be C::iterator. For example, std::string::iterator and std::unordered_map<std:string, double>::iterator are both iterator types.

Under the hood, these iterator types are implemented by the compiler internally for each data structure and type-aliased with a using definition inside of the container class. For example, consider one possible definition for a std::vector:

template <typename T>
class std::vector {
public:
  using iterator = T*;
};

This code works because std::vector actually does store its elements sequentially in memory (through a heap allocated buffer) and pointers, as previously mentioned, share the basic semantics of iterators. A look behind the scenes for a more complex type like std::unordered_map might reveal a different implementation:

template <typename K, typename V>
class std::unordered_map {
public:
  using iterator = _unordered_map_iterator<K, V>;
};

template <typename K, typename V>
struct _unordered_map_iterator {
  // Advance to the next element in the map
  void operator++();

  // Get access to the element associated with the iterator
  std::pair<const K, V>& operator*();
};

where _unordered_map_iterator is some internal, compiler-dependent type representing an iterator to an unordered map and which overloads all the necessary operations to meet the interface criteria for an iterator. _unordered_map_iterator is just an example—the actual type used will depend on the compiler.

Iterator Categories

Not all iterators support the same set of operations. As a consequence of how their container is defined internally, some are more "powerful" than others. This is primarily a result of the restriction in the C++ Standard that all iterator methods be $O(1)$ in runtime complexity. For example, it is trivial to jump ahead by $n$ elements with a vector iterator in $O(1)$ time since a vector's memory is laid out sequentially, but not so straightforward to do so for an std::unordered_map whose elements are arranged in a distributed fashion. This gives rise to a variety of different iterator categories: each container's iterators fall into one of the following categories depending on what operations it supports.

Output

An iterator is an output iterator if it supports overwriting the pointed to element via operator=, e.g.:

*it = elem;

Some container iterators will not be output if modifying their element would require restructuring the container. For example, changing the key of an element in a std::map might change where that element lives in its binary-search tree, so std::map<K, V>::iterator is not output.

Input

An iterator is an input iterator if it supports reading the pointed to element, e.g.:

auto elem = *it;

Almost all iterators are input iterators^[3]—in fact, all of the following iterator categories are specializations of input iterators.

Forward

Up to this point, we have not actually specified whether it is valid to make multiple passes over the iterators of a container. For example, given a range of elements between begin and end iterator, would it be valid to traverse these elements multiple times?

for (auto it = begin; it != end; ++it) {
  std::cout << *it << " ";
}

std::cout << "\n\n";

/* Are we allowed to run this for loop again with the same iterators? */
for (auto it = begin; it != end; ++it) {
  std::cout << *it << " ";
}

Forward iterators guarantee that multiple passes are valid. Every STL container's iterators are forward—intuitively, this should make sense: simply iterating over a container's elements doesn't change them in a way that would prevent iterating again. Outside of the STL containers, however, this is not generally true^[4].

More formally, forward iterators must satisfy the multi-pass guarantee. That is, given iterators a and b which point to the same element (a == b), it must hold that ++a == ++b. In plain English, moving both iterators forward (in either order) should land them at the same element.

Bidirectional

Bidirectional iterators are a kind of forward iterator that can be moved backwards as well as forwards, e.g.

--it;

A container's iterators will be bidirectional if there is some way to identify the previous element. This may be the case if the container is sequential (like a vector) or its elements are sorted (like a std::map). Some containers have no easy way to go backwards from an iterator (or choose not provide this behaviour) like std::unordered_map.

Be careful not to decrement before the begin iterator! Writing --c.begin() is undefined behaviour, just like ++c.end().

Random Access

A random-access iterator is a bidirectional iterator that supports jumping forwards or backwards multiple elements at a time.

auto it = c.begin() + n;

Negative values will move the iterator backwards. These iterators closely resemble pointers in their syntax. For example, we can use operator[] to combine an increment/dereference together:

std::vector<int> v { 1, 2, 3 };
auto it = v.begin();
auto elem = it[2];      // Same as *(it + 2)

Once again, be careful not to go out of bounds or dereference the end iterator!

Contiguous

Contiguous iterators are a subset of random-access iterators that further stipulate that their elements are stored contiguously in memory. For example, an std::deque is random-access, but not contiguous (recall its implementation details).

Functionally, there is not much difference between contiguous and random-access iterators. However, taking the address of the elements pointed to by these iterators (&*it) will reveal that they are stored contiguously in memory.

Iterator Invalidation

What happens to an iterator if we modify its underlying container? Iterators, much like pointers, point to a fixed location in memory where their element is stored, plus some bookkeeping data to derive the location of the next element. As a result, operations which restructure a container may invalidate previously obtained iterators. This can lead to undefined behaviour if we are not careful.

Here's a table sumarizing which operations will and will not invalidate iterators for the containers discussed in this textbook:

Iterator Flavors

Occasionally, you will discover some variants of the above iterator concepts when working with C++ in practice. These iterator "flavors" allow us to handle const containers more appropriately, as well as work with bidirectional iterators in reverse order.

const Iterators

Given a const container, we would not want to allow elements of that container to be modified through their iterators. This is the idea of const correctness—objects that are marked const should not be allowed to be modified through any part of their interface.

const iterators allow for container types to conform to this principle. A container type C with elements of type T will in practice have two iterator types:

• C::iterator which points to elements of type T (e.g. std::string::iterator points to char)
• C::const_iterator which points to elements of type const T (e.g. std::string::const_iterator points to const char)

Namely, this means that you cannot modify the elements that a const_iterator points to. As a result, every const_iterator is necessarily not an output iterator, since you can't write to the underlying element (however, you can still have non-output containers which have a meaningful distinction between their iterator and const_iterator types!^[6]).

Practically speaking, const_iterator can be used anywhere an iterator for the same container was expected, so long as you do not require modification. For example, iterator algorithms (discussed in the next chapter) which do not modify their range (e.g. std::count_if counts the number of elements between two iterators) will work just as well on const_iterators as they do on regular iterators. However, algorithms which do modify their range (e.g. std::sort sorts the elements between two iterators in-place) will not compile for const_iterator.

Given a const container c, calling c.begin() or c.end() will automatically return const_iterators through the provided const overloads for these methods. However, if you require a const iterator for a non-const container, you can request these through the following convenience methods defined on every standard library container:

Reverse Iterators

Bidirectional iterators provide an easy way for us to create a reverse ordering of the elements in a container. This is useful if we wanted to iterate through a container in reverse, or if we want to apply an iterator algorithm in reverse order (e.g. std::find(c.begin(), c.end(), v) searches for a value v starting from the left—what if we wanted to search from the right?). This is precisely what reverse iterators accomplish.

Every container whose iterators are bidirectional provides a reverse iterator interface for iterating backwards through a sequence. These methods are analogous to their ordinary counterparts:

Reverse iterators can only exist for bidirectional iterators: behind the scenes, a reverse iterator stores a regular iterator and moving forward (operator++) on the reverse iterator decrements the stored iterator (operator--). Reverse iterators are implemented as a templated wrapper (std::reverse_iterator) around a bidirectional iterator, so containers do not need to implement any additional functionality to achieve this result. In effect, a reverse iterator stores an iterator to the element one ahead its dereferenced value, as explained by the diagram below.

std::vector<int> v { 1, 2, 3, 4, 5 };

auto rbegin = v.rbegin();
auto rend = v.rend();

We can get the actual iterator a reverse iterator stores by calling the member function base() on it, e.g.

std::vector<int> v { 1, 2, 3, 4, 5 };

auto rb = v.rbegin();
auto re = v.rend();

auto rb_base = rb.base();
auto re_base = re.base();

Reverse iterators generally inherit the category of their underlying iterator (e.g. random access iterators are random access in reverse). The only exception to this is contiguous iterators—since the elements are ordered in reverse, they are no longer strictly contiguous as the addresses decrease instead of increase as you move forward in the reverse sequence.

Deep Dive: std::deque::iterator

In this section, we will see how an iterator might actually be implemented for a real STL container data structure—in this case, an std::deque. Compilers are free to implement iterators however they choose, so long as the iterator operators are constant time and respect the invalidation rules above. In this section, our implementation will roughly mirror the g++ compiler's implementation, whose source code can be found here, with a few simplifications. std::deque<T>::iterator is a random-access iterator, but for brevity, we will only implement the bidirectional iterator operations, namely operator*, operator++, and operator--. The remaining random-access operations are left as an exercise to the reader.

Recall from the chapter on sequence containers that a deque organizes its elements as an array of fixed-sized blocks of elements:

std::deque<int> d { 4, 5, 6, 7, 8, 9 };

Accordingly, we can imagine that a std::deque, behind the scenes, might look something like this:

#define BLOCK_SIZE 4

template <typename T>
class _deque_iterator {
  // TODO: Implementation of a deque iterator
  // We will implement this later in this section!
};

template <typename T>
class std::deque<T> {
public:
  using iterator = _deque_iterator<T>;
  using const_iterator = _deque_iterator<const T>;

  iterator begin() { return start; }
  iterator end() { return finish; }

  const_iterator begin() const { return start; }
  const_iterator end() const { return finish; }

  auto rbegin() { return std::make_reverse_iterator(end()); }
  auto rend() { return std::make_reverse_iterator(begin()); }

  auto rbegin() const { return std::make_reverse_iterator(end()); }
  auto rend() const { return std::make_reverse_iterator(begin()); }

  /* Remaining operations of a deque: constructor, push_front, push_back, etc. */

private:
  iterator start, finish;   // begin and end iterators
  T** blocks;               // array of fixed-size block pointers
  size_t capacity;          // allocated size of blocks array
};

_deque_iterator is the name of the iterator type for a deque which we will implement. Before we do so, take note of a few details:

• iterator and const_iterator are type aliases for an underlying _deque_iterator to a T or const T, respectively.
• BLOCK_SIZE is the fixed size of the individual blocks. In actual practice, g++'s definition of this value is a bit more involved, with the actual size depending on the type T.
• begin() and end() have const overloads. This will pose a problem for the const-versions of these methods, since _deque_iterator<T> cannot be converted to _deque_iterator<const T> by default. As a result, we will need to make sure our _deque_iterator provides a constructor for converting between these as a result.
• rbegin() and rend() (and their const overloads) call std::make_reverse_iterator, which given a bidirectional iterator, produces a new iterator to the reversed range. We use auto to let the compiler deduce the return type, which will be std::reverse_iterator<iterator> (or std::reverse_iterator<iterator> for the const versions).

So what goes into implementing _deque_iterator? For starters, we must decide what data the iterator needs to track in order to increment and decrement the iterator. This poses an interesting challenge: if an iterator points to the end of one block, operator++ needs to somehow know to move on to the start of the next block. operator-- must likewise reposition iterators to the final element of the previous block. To solve this, compilers typically keep track of four pointers: the element the iterator points to, the element's block, and the first and last element in that block. In code, we might have a _deque_iterator that looks like this:

template <typename T>
class _deque_iterator {
private:
  T** block;
  T*  current;
  T*  first;
  T*  last;

public:
  /** Increments an iterator with prefix notation, e.g. ++it */
  _deque_iterator& operator++();

  /** Decrements an iterator with prefix notation, e.g. --it */
  _deque_iterator& operator--();

  /** Allows dereferencing the iterator, e.g. *it */
  T* operator->() const { return current; }

  /** Allows using the arrow operator for compound T, e.g. it->member */
  T& operator*() const { return *current; }

  /** Increments an iterator with postfix notation, e.g. it++ */
  _deque_iterator operator++(int) {
    _deque_iterator prev = *this;
    ++*this;
    return prev;
  }

  /** Increments an iterator with postfix notation, e.g. it-- */
  _deque_iterator operator--(int) {
    _deque_iterator prev = *this;
    --*this;
    return prev;
  }


  /**
   * Constructs a _deque_iterator from an element pointer and the pointer to its block pointer.
   * Sets the first and last pointers using BLOCK_SIZE accordingly.
   *
   * std::deque will call this constructor internally to create iterators (not shown).
   */
  _deque_iterator(T* current, T** block)
    : block(block), current(current), first(*block), last(*block + BLOCK_SIZE)
    { }

  /**
   * Handles conversion from an iterator to a const_iterator.
   * In this case, V = U and T = const U for some typename U
   *
   * Notice that the other way around would not compile,
   * since a const T* cannot be assigned to a T*.
   */
  template <typename V>
  _deque_iterator(const _deque_iterator<V>& it)
    : block(it.block), current(it.current), first(it.first), last(it.last)
    { }
};

In the above implementation, our _deque_iterator class has the four pointers as described, with a constructor that initializes them and a copy constructor that will handle conversion from an iterator to a const_iterator (both constructors are constant-time, as required). We have hidden the implementation of the core iterator operators—the prefix operator++() and operator--()—which we will cover shortly. Notice that the postfix forms—operator++(int) and operator--(int)—are implemented in terms of their prefix equivalents.

To implement operator++, we will attempt to move the current pointer to the next contiguous element within its block. If this increment would cause current to exceed its block, we will reposition it to the next block pointer, setting first and last accordingly. This could be implemented as:

_deque_iterator& operator++() {
  ++current;                    // Attempt to move current forward
  if (current == last)          // Check OOB (assume last is past-the-end of the block)
  {
    ++block;                    // Move to next block
    first = *block;             // Get first element of block
    last  = first + BLOCK_SIZE; // Get last element of block
    current = first;            // Reposition current
  }
  return *this;
}

Notice that while the individual blocks of a deque are not all contiguous in memory, the blocks array which contains all the pointers-to-blocks is itself contiguous! This allows us to write ++block in the above implementation. Also notice that operator++ is constant-time, as required.

Implementing operator-- will take a similar approach:

_deque_iterator& operator--() {
  --current;                    // Attempt to move current backwards
  if (current < first)          // Check OOB (first is in-bounds)
  {
    --block;                    // Move to previous block
    first = *block;             // Get first element of block
    last  = first + BLOCK_SIZE; // Get last element of block
    current = last - 1;         // Reposition current
  }
  return *this;
}

Voila! Putting everything together, we have built a bidirectional deque iterator. To complete it, we would need to add the random-access operators, in particular operator+= and operator-=. One approach might be to call operator++ and operator-- above n times, except that this would violate the restriction that iterator operations are constant-time. Instead, the actual random-access operators will precompute how many blocks they need to skip, and skip them in one fell swoop (e.g. blocks += block_offset). We will not implement this here, but we encourage you to consider how you might implement it yourself or take a look at the g++ source for these methods.