Iterators

Iterators

In other languages, like Java or Python, iterators only allow you to do the operations needed for iterating like checking if there is next element and getting the next element. C++ is relatively unique because it's iterators are modeled after pointers.

Iterating with Pointers

If you had an array, you'd probably iterate over it using an index like this:

int a[] = {11, 22, 33, 44, 55};
for (int i = 0; i < 5; ++i) {
  cout << a[i] << endl;
}

However, you could also equivalently iterate over it using pointers, like this:

int a[] = {11, 22, 33, 44, 55};
int *begin = &a[0], *end = &a[5];
for (int *p = begin; p != end; ++p) {
  cout << *p << endl;
}

This works because in an array, the elements are stored one after another in memory. If a[i] is at address 1,024 (0x400) and sizeof(int) == 4, then a[i + 1] is at address 1,024 + sizeof(int) == 1,028 (0x404).

In the loop, p starts out pointing to &a[0], then gets incremented (++p) to point to &a[1] which is sizeof(int) == 4 bytes later in memory, and so on.

Iterating over std::vector

Since std::vector stores it's elements in an array, we can actually iterate over it in the same we that we did for an array.

std::vector<int> a = {11, 22, 33, 44, 55};
int *begin = &a[0], *end = &a[5];
for (int *p = begin; p != end; ++p) {
  cout << *p << endl;
}

That loop is almost identical to how you'd iterate over an std::vector with iterators:

std::vector<int> a = {11, 22, 33, 44, 55};
for (auto it = a.begin(); it != a.end(); ++it) {
  cout << *it << endl;
}

This is how iterators are modeled or inspired by pointers. All iterators in C++ support the operations you need to loop in this way but not all iterators in C++ support other things like subtraction or addition, like regular pointers: you can copy them (auto it = a.begin()), compare them (it != a.end()), increment them (++it), and dereference them (*it) like a pointer. std::vector::iterator is what's called a RandomAccessIterator and supports a lot of the same things that regular pointers do, like subtraction (a.end() - a.begin() == 5 in the example above). Other iterators, like std::list::iterator support fewer operations but all iterators support the operations you need to write a for-loop.

For-each Loops

For-each loops in C++ are actually just using iterators behind the scenes. The following loops are equivalent:

std::vector<int> a = {11, 22, 33, 44, 55};
{
  auto it_end = a.end();
  for (auto it = a.begin(); it != it_end; ++it) {
    cout << *it << endl;
  }
}

for (const int x : a) {
  cout << x << endl;
}

For each loops work on any iterable that provides a begin() and end() method that returns an appropriate iterator.

Making your own Iterators

To keep things simple, let's start by making an iterator that just wraps a pointer, just to show that iterators in C++ really do behave like pointers:

class IntPointerIterator {
  int *p;
public:
  IntPointerIterator(int *p) : p(p) {}

  bool operator!=(const IntPointerIterator& other) {
    return p != other.p;
  }

  IntPointerIterator& operator++() {
    ++p;
    return *this;
  }

  int operator*() {
    return *p;
  }
};

int main() {
  int a[] = {11, 22, 33, 44, 55};
  IntPointerIterator begin(a), end(a + 5);
  for (IntPointerIterator it = begin; it != end; ++it) {
    cout << *it << endl;
  }
}