Iterators overview

Introduction

C++ standart template library (STL) provides a lot of containers with different semantics: variable-length arrays (std::vector), static-length arrays (std::array), linked lists (std::list and std::forward_list), hash tables etc. They are implemented in different ways, but some operations are common: apply the same function to all elements, find an element, accumulate values using addition or other function etc. Additionally, there is a constant need to get a reference to an element for reading value, swapping, insertion, or deletion. All of these tasks may generalized with iterators

C++ iterator roots

Assume you have a C-style array:

struct Entry* arr = (struct Entry*)malloc(sizeof(struct Entry*) * length);

Let's assume we want to get a sum of some Entry fields. To do this, we usually write a loop and check every elements (or, in other words, iterating it):

unsigned i;
unsigned sum = 0;
for (i = 0; i != length; ++i)
    sum += arr[i].field; // sum += (arr + i)->field

Advanced C programmer would avoid address calculation in a loop and uses pointers instead:

struct Entry* begin = arr;
struct Entry* end = arr + length;
struct Entry* ptr;
for (ptr = begin; ptr != end; ++ptr)
    sum += ptr->field;

That points are actually iterators. What operations are possible with them? Here is a short list:

• ptr++, ++ptr — moving to the next element
• ptr--, --ptr — moving to the previous element
• *ptr, ptr-> — dereferencing
• ptr1 - ptr2 — subtraction (distance)

In C++, we may overload operators for classes. Thus, we may introduce a class Iterator which has the same semantics as the pointer. Let's start with std::vector which is just a wrapper over C-style heap array. Its iterator may be just a pointer with some wrapping.

template<typename E>
class iterator {
    E* ptr;
public:
    Iterator<E> operator++() { ++ptr; return *this; }
    // ...
};

std::vector<Entry> my_vec(length);
// ...
std::vector<Entry>::iterator begin = my_vec.begin();
std::vector<Entry>::iterator end   = my_vec.end();
std::vector<Entry>::iterator it;
unsigned sum = 0;
for (it = begin; it != end; ++it)
    sum = it->field;

The big advantage of iterators in C++ is automatization. The code above could be simplified:

// Variant 1
unsigned sum = 0;
for (auto it = my_vec.begin(); it != my_vec.end(); ++it)
    sum += it->field;

// Variant 2
unsigned sum = 0;
for (const auto& entry : my_vec) // automated begin(), end(), and dereference
    sum += entry.field;

// Variant 3
unsigned sum = std::accumulate(my_vec.begin(), my_vec.end(), 0); // automated summation

Iterating non-array containers