C++ Iterator

Introduction

C++ Iterator is an abstract notion which identifies an element of a sequence. A sequence could be anything that are connected and sequential, but not necessarily consecutive on the memory. C++ Iterator could be a raw pointer, or any data structure which satisfies the basics of a C++ Iterator. It has been widely used in C++ STL standard library, especially for the std containers and functions.

In this blog post, I would like to discuss how to implement C++ Iterator using nested class inside a certain sequence container class for generic programming.

Examples

In this example, we would like to apply different sequence data structures, including std::list, std::array, std::vector, and a custom dummy vector class DummyVector, to the custom template function maximum and the std function std::max_element, which take in two Iterator instances and return an Iterator instance, to find out the maximum value in the sequence. Since std containers have already implemented the Iterators for us, we would just use DummyVector as an example for how to implement class-specific nested Iterator class while making it generic by satisfying the Iterator abstract notions.

According to the C++ standard, an iterator must provide the overloading for *, (prefix) ++, ==, and !=. For completeness, I also implemented (postfix) ++, (prefix) --, and (postfix) --, since some custom template function, such as our maximum function, might use these operators as well without following the exact C++ standard.

iterator.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <list>
#include <vector>

// Custom data structure with iterators
// For some additional implementations for Vector
// /blog/CPP-Const-Overloading/
template <typename T>
class DummyVector
{
public:
    // Default constructors
    DummyVector();
    // Constructors which take more than zero arguments
    explicit DummyVector(size_t size);
    explicit DummyVector(std::initializer_list<T> lst);

    // Iterator basics
    class Iterator;
    Iterator begin();
    Iterator end();

private:
    size_t mSize;
    T* mBuffer;
};

// However, the best practice for template classes and functions is to put the
// definition and the declaration together. Mainly, there are two reasons
// 1. Compiler needs to know all the definition for any templates during compile
// time
// 2. Namescope is trivial to write and confusing
template <typename T>
DummyVector<T>::DummyVector() : mSize{0}, mBuffer{nullptr}
{
}

template <typename T>
DummyVector<T>::DummyVector(size_t size) : mSize{size}, mBuffer{new T[size]}
{
    for (int i = 0; i < mSize; i++)
    {
        mBuffer[i] = 0;
    }
}

template <typename T>
DummyVector<T>::DummyVector(std::initializer_list<T> lst)
    : mSize{lst.size()}, mBuffer{new T[lst.size()]}
{
    std::copy(lst.begin(), lst.end(), this->mBuffer);
}

// Iterator is an abstract notion
template <typename T>
class DummyVector<T>::Iterator
{
public:
    // Constructor
    Iterator(T* ptr);
    // Compulsory methods
    // Prefix
    Iterator& operator++();
    Iterator& operator--();
    // Postfix
    // Returns the value before update
    // Impossible to return by reference
    // Return by value instead
    Iterator operator++(int);
    Iterator operator--(int);
    T& operator*();
    bool operator==(const Iterator& iter);
    bool operator!=(const Iterator& iter);

private:
    T* mPtr;
};

template <typename T>
DummyVector<T>::Iterator::Iterator(T* ptr) : mPtr{ptr}
{
}

// Prefix overloading
// If T::X is a dependent typename, then we need to prefix it by typename to
// tell the compiler to parse it in a certain way.
template <typename T>
typename DummyVector<T>::Iterator& DummyVector<T>::Iterator::operator++()
{
    this->mPtr++;
    return *this;
}
// Prefix overloading
template <typename T>
typename DummyVector<T>::Iterator& DummyVector<T>::Iterator::operator--()
{
    this->mPtr--;
    return *this;
}

// Postfix overloading
template <typename T>
typename DummyVector<T>::Iterator DummyVector<T>::Iterator::operator++(int)
{
    DummyVector<T>::Iterator temp = *this;
    this->mPtr++;
    return temp;
}
// Postfix overloading
template <typename T>
typename DummyVector<T>::Iterator DummyVector<T>::Iterator::operator--(int)
{
    DummyVector<T>::Iterator temp = *this;
    this->mPtr--;
    return temp;
}

template <typename T>
T& DummyVector<T>::Iterator::operator*()
{
    return *this->mPtr;
}

template <typename T>
bool DummyVector<T>::Iterator::operator==(const Iterator& iter)
{
    return this->mPtr == iter.mPtr;
}

template <typename T>
bool DummyVector<T>::Iterator::operator!=(const Iterator& iter)
{
    return this->mPtr != iter.mPtr;
}

template <typename T>
typename DummyVector<T>::Iterator DummyVector<T>::begin()
{
    return DummyVector<T>::Iterator{this->mBuffer};
}

template <typename T>
typename DummyVector<T>::Iterator DummyVector<T>::end()
{
    return DummyVector<T>::Iterator{this->mBuffer + this->mSize};
}

// Template function for iterators
template <typename Iter>
Iter maximum(Iter first, Iter last)
{
    Iter max = first;
    for (Iter iter = first; iter != last; iter++)
    {
        if (*max < *iter)
        {
            max = iter;
        }
    }
    return max;
}

int main()
{
    // STL containers
    std::list<int> lst{1, 2, 3, 4, 5};
    std::array<float, 5> arr{1, 2, 3, 4, 5};
    std::vector<float> vec{1, 2, 3, 4, 5};
    // Custom container
    DummyVector<double> dummyVec{1, 2, 3, 4, 5};

    auto lstMaxIter = maximum(lst.begin(), lst.end());
    std::cout << *lstMaxIter << std::endl;
    auto arrMaxIter = maximum(arr.begin(), arr.end());
    std::cout << *arrMaxIter << std::endl;
    auto vecMaxIter = maximum(vec.begin(), vec.end());
    std::cout << *vecMaxIter << std::endl;
    auto dummyVecMaxIter = maximum(dummyVec.begin(), dummyVec.end());
    std::cout << *dummyVecMaxIter << std::endl;

    lstMaxIter = std::max_element(lst.begin(), lst.end());
    std::cout << *lstMaxIter << std::endl;
    arrMaxIter = std::max_element(arr.begin(), arr.end());
    std::cout << *arrMaxIter << std::endl;
    vecMaxIter = std::max_element(vec.begin(), vec.end());
    std::cout << *vecMaxIter << std::endl;
    dummyVecMaxIter = std::max_element(dummyVec.begin(), dummyVec.end());
    std::cout << *dummyVecMaxIter << std::endl;
}

To compile the program, please run the following command in the terminal.

$ g++ iterator.cpp -o iterator -std=c++11

The expected output of the program would be as follows.

$ ./iterator 
5
5
5
5
5
5
5
5

Conclusions

If we have a custom sequence container class, and we want to take the advantage of the existing C++ STL algorithm std template functions, we could just implement the Iterator for the custom sequence container class. This container class would then be compatible with all the C++ STL algorithm std template functions. This is an extremely good example of the C++ generic programming concept.