Custom STL Compatible Iterators

What is an Iterator?

The Iterator is the abstraction at the heart of all Collection-related functionality within the C++ Standard Library. Most algorithms are defined in terms of iterators. What is an iterator exactly?

Fundamentally, an Iterator represents a point of iteration. A point of iteration describes:

• How to retrieve the value at the point
• How the point of iteration can be incremented/decremented
• How to compare it with other points of iteration

For example: Conceptually, if you are ‘iterating’ over a book’s pages, the point of iteration could describe the following rules:

• The value at the point of iteration can be retrieved by reading the current page.
• The point of iteration can be incremented by turning the page forward.
• You can compare the point of iteration with other points of iteration by looking at the page number.

Take note how this book example does not describe how to ‘decrement’ the iteration. Philosophically speaking, using this description; you could only ever turn the pages forward, never back.

In C++, iterators are defined as objects with methods describing their rules.

Creating a Custom Collection

First, we are going to create a custom collection type compatible with STL algorithm constructs and ranged for-loops. At that level of abstraction all we need to provide is begin() and end() methods, and then we will be able to write code like this:

Collection col;

for(auto& c : col)
    cout << c << endl;

std::transform(begin(col), end(col), begin(col), [](auto& i)
{
    return i * i;
});

Our collection will be a simple wrapper class around a c-array. This is what std::array provides in the Standard Library. In reality, you will only write custom collections and iterators if you need very particular data structures satisfying very specific requirements. Here is our collection definition:

template<class T, int N>
class Collection
{
    T data[N] = { 0 };
public:
    col_iterator<T> begin()
    {
        return col_iterator<T>(data);
    }
    col_iterator<T> end()
    {
        return col_iterator<T>(data + N);
    }
};

We take type and size as template arguments, create an array of that type and size. We also define methods which return the iterators to the beginning and end of the collection, passing the pointers to the first element (data) and just past the last element (data + N) as arguments.

The Iterator Itself

Now that we have created a collection-type, we need to define the iterator for use with the begin() and end() methods. First, we declare our iterator class ahead of our collection class declaration (The class needs to be aware of the iterator’s existence), and then we define the iterator below the collection definition:

template <class T> class col_iterator; // Declaration

// Collection class definition  here ...

template <class T>
class col_iterator // Definition
{
    // Iterator Definition Goes Here
}

There a few things an iterator needs in order to be STL compatible. This also depends on the type of the iterator. The types of iterators are:

• Input Iterators
• Output Iterators
• Forward Iterator
• Bidirectional Iterators
• Random-Access Iterators

Each of these have different requirements. For the sake of simplicity, we will be defining a Forward Iterator for our collection, which has less requirements. These are the requirements for Forward Iterators:

1. Iterator Characteristics - Five member type definitions which describe the iterator type and datatypes that iterator is related to.
2. Default Constructor - Ability to construct the iterator with no arguments
3. **Dereference Operator *** - to access the underlying data the iterator is “pointing” towards.
4. Not-Equal Operator != - to know when iterators are not equal to one another
5. Pre-Increment Operator ++ - to increment the iterator.
6. Post-Increment Operator ++ - to create and return an incremented iterator.

And that’s it! If these elements are present in a class it is a valid iterator that can be used with STL algorithms. These members must be publically accessible.

Let’s define our iterator in code:

#include <iterator>

template <class T>
class col_iterator
{
    T* data;
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = size_t;
    using pointer = T*;
    using reference = T&;

    col_iterator(){}
    col_iterator(pointer _data) : data(_data) {}

    pointer data() { return data; }
    reference operator*() { return *data; }
    bool operator!=(const col_iterator& other)
    {
        return data != other.data();
    }
    col_iterator<T>& operator++()
    {
        data += 1;
        return *this;
    }
    col_iterator<T> operator++(int)
    {
        return col_iterator<T>(data + 1);
    }
};

As you can see we have defined all the required elements of a Forward Iterator. One thing to note is the member iterator_category. It uses the std::forward_iterator_tag from the standard library marking this iterator as a Forward Iterator. These tags are available in .

Now our class should easily work with STL algorithms such as the following:

Collection<int, 5> test;
std::fill(test.begin(), test.end(), 10);

To get more familiar with iterators:

• Add constant iterators to your collection ( define cend() and cbegin()).
• Read up on the different iterator types and their specific requirements.
• Implement different iterator types for your collection.
• Try creating a collection with a different underlying type. For example using a linked-list instead of c-array. The increment and decrement methods will be much different.

Complete Code Example

#include <iterator>
#include <iostream>
#include <algorithm>

template <class T> class col_iterator;

template<class T, int N>
class Collection
{
    T data[N] = { 0 };
public:
    col_iterator<T> begin()
    {
        return col_iterator<T>(data);
    }
    col_iterator<T> end()
    {
        return col_iterator<T>(data + N);
    }
};

template <class T>
class col_iterator
{
public:
    T* data;
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = size_t;
    using pointer = T*;
    using reference = T&;

    col_iterator(){}
    col_iterator(pointer _data) : data(_data) {}

    reference operator*() { return *data; }
    bool operator!=(const col_iterator& other)
    {
        return data != other.data;
    }
    col_iterator<T>& operator++()
    {
        data += 1;
        return *this;
    }
    col_iterator<T> operator++(int)
    {
        return col_iterator<T>(data + 1);
    }
};

int main(void)
{
    Collection<int,10> test;

    std::fill(test.begin(), test.end(), 2);

    std::transform(test.begin(), test.end(), test.begin(), [](int i)
    {
        return i * i;
    });

    for(auto t : test)
        std::cout << t << std::endl;
}