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;
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;