creating Random Access Iterator

For this example let's implement a simple StaticArray class:

template <typename T, size_t SizeT>
class StaticArray
{
protected:
    T* m_pData;
protected:
    void __allocate() { m_pData = new T[SizeT]; }
    void __free() { if (m_pData) delete[] m_pData; }
public:
    StaticArray() : m_pData(NULL) { __allocate(); }
    StaticArray(const StaticArray& r) : m_pData(NULL)
    {
        __allocate();
        copy(r.m_pData, r.m_pData + SizeT, m_pData);
    }  
    virtual ~StaticArray() { __free(); }
    const T& operator[](size_t ulInd) const { return m_pData[ulInd]; }
    T& operator[](size_t ulInd) { return m_pData[ulInd]; }
};

StaticArray class holds an array of T typed elements, where the size of the array is SizeT (defined as non-type template parameter). size_t is the type of sizeof operator result, it's defined as unsigned integer number. So user won't be able to define a StaticArray with negative length.

This StaticArray class code really does nothing, it's just a simple wrap-up around plain C array, but it perfectly fits for our first random access iterator implementation task ;).

Random access iterator requirements:

1. Default constructor, copy-constructor, operator=;
2. Prefix & postfix ++, -- operators$
3. operator+(const difference_type&), operator-(const difference_type&);
4. operator+=(const difference_type&), operator-=(const difference_type&);
5. reference operator[](const difference_type&);
6. reference operator*(), pointer operator->();
7. ==, !=, <, >, <=, >= operators;
8. difference_type operator+(const iterator&, const iterator&), difference_type operator-(const iterator&, const iterator&).

difference_type is a typedef for ptrdiff_t. 
reference stands for T&, and pointer is T*.

What is exactly this ptrdiff_t type? It is considered to be a platform-specific signed integer number, in order to be able to hold an address. If we have two pointers ptr1 and ptr2, the type of the result of (ptr1 - ptr2) operation is ptrdiff_t.

Let's now implement our iterator class called PointerIterator. PointerIterator will have a constructor which will receive a pointer to an element that it holds. Basically this iterator is going to be just another wrap-up around plain C pointer type :) But it would give an idea how to implement iterators for more complex types. And of course we're gonna use templates ;)

template<typename TypeT>
class PointerIterator :
    public std::iterator<random_access_iterator_tag, TypeT>
{
protected:
    TypeT* m_pData;   
public:
    typedef random_access_iterator_tag iterator_category;
    typedef
        typename iterator<random_access_iterator_tag, TypeT>::value_type
        value_type;
    typedef
        typename iterator<random_access_iterator_tag, TypeT>::difference_type
        difference_type;
    typedef
        typename iterator<random_access_iterator_tag, TypeT>::reference
        reference;
    typedef
        typename iterator<random_access_iterator_tag, TypeT>::pointer
        pointer;
   
    PointerIterator() : m_pData(NULL) {}

   
    template<typename T2>
    PointerIterator(const PointerIterator<T2>& r) : m_pData(&(*r)) {}
   
    PointerIterator(pointer pData) : m_pData(pData) {}
       
    template<typename T2>
    PointerIterator& operator=(const PointerIterator<T2>& r)
        { m_pData = &(*r); return *this; }

    PointerIterator& operator++()  // PREFIX
        { ++m_pData; return *this; }
    PointerIterator& operator--()  // PREFIX
        { --m_pData; return *this; }
    PointerIterator operator++(int)  // POSTFIX
        { return PointerIterator(m_pData++); }
    PointerIterator operator--(int)  // POSTFIX
        { return PointerIterator(m_pData--); }
    PointerIterator operator+(const difference_type& n) const
        { return PointerIterator(m_pData + n); }
    PointerIterator& operator+=(const difference_type& n)
        { m_pData += n; return *this; }
    PointerIterator operator-(const difference_type& n) const
        { return PointerIterator(pointer(m_pData - n)); }
    PointerIterator& operator-=(const difference_type& n) { m_pData -= n; return *this; }
    reference operator*() const { return *m_pData; }
    pointer operator->() const { return m_pData; }
    reference operator[](const difference_type& n) const { return m_pData[n]; }
};

Why do we use a template copy constructor and template assignment operator? Let's talk about const_iterators and non-const iterators. Const iterators return const TypeT reference and pointer as a result for operator*() and operator->(), whereas non-const iterator returns plain TypeT reference and pointer. That's why const_iterator can be constructed or assigned from iterator and const_iterator, where iterator can be created or assigned only from iterator type. So if we are trying to assing const TypeT* to plain TypeT* pointer, the compiler would throw an error. As you might have noticed our iterator class contains a pointer to a type. So this template copy-constructor and assignment operator will perfectly work in case of const_iterators and plain iterators.

Let's now implement other important operators for PointerIterator class out of its class definition:

template<typename T>
bool operator==(const PointerIterator<T>& r1, const PointerIterator<T>& r2)
    { return (r1.m_pData == r2.m_pData); }

template<typename T>   
bool operator!=(const PointerIterator<T>& r1, const PointerIterator<T>& r2)
    { return (r1.m_pData != r2.m_pData); }
   
template<typename T>
bool operator<(const PointerIterator<T>& r1, const PointerIterator<T>& r2)
    { return (r1.m_pData < r2.m_pData); }

template<typename T>   
bool operator>(const PointerIterator<T>& r1, const PointerIterator<T>& r2)
    { return (r1.m_pData > r2.m_pData); }

template<typename T>
bool operator<=(const PointerIterator<T>& r1, const PointerIterator<T>& r2)
    { return (r1.m_pData <= r2.m_pData); }

template<typename T>   
bool operator>=(const PointerIterator<T>& r1, const PointerIterator<T>& r2)
    { return (r1.m_pData >= r2.m_pData); }

template<typename T>   
typename PointerIterator<T>::difference_type operator+(
    const PointerIterator<T>& r1,
    const PointerIterator<T>& r2)
{ return PointerIterator<T>(r1.m_pData + r2.m_pData); }

template<typename T>   
typename PointerIterator<T>::difference_type operator-(
    const PointerIterator<T>& r1, const PointerIterator<T>& r2)
{ return r1.m_pData - r2.m_pData; }

Since these operators are accessing to protected PointerIterator's data member, we have to define them as friends in the class definition:

    template<typename T>
    friend bool operator==(const PointerIterator<T>& r1, const PointerIterator<T>& r2);

    template<typename T>
    friend bool operator!=(const PointerIterator<T>& r1, const PointerIterator<T>& r2);

    template<typename T>
    friend bool operator<(const PointerIterator<T>& r1, const PointerIterator<T>& r2);

    template<typename T>
    friend bool operator>(const PointerIterator<T>& r1, const PointerIterator<T>& r2);

    template<typename T>
    friend bool operator<=(const PointerIterator<T>& r1, const PointerIterator<T>& r2);

    template<typename T>
    friend bool operator>=(const PointerIterator<T>& r1, const PointerIterator<T>& r2);
       
    template<typename T>   
    friend typename PointerIterator<T>::difference_type operator+(
        const PointerIterator<T>& r1, const PointerIterator<T>& r2);

    template<typename T>   
    friend typename PointerIterator<T>::difference_type operator-(
        const PointerIterator<T>& r1, const PointerIterator<T>& r2);

Looks good so far.
Now, let's make it look like when we declare std::vector<T>::iterator by adding necessery typedefs to StaticArray class:

    typedef PointerIterator<const T> const_iterator;
    typedef PointerIterator<T> iterator;

and implement begin(), end() methods for it:

    const_iterator begin() const
        { return const_iterator(m_pData); }
       
    const_iterator end() const
        { return const_iterator(m_pData + SizeT); }

    iterator begin()
        { return iterator(m_pData); }
       
    iterator end()
        { return iterator(m_pData + SizeT); }

Take a look at end() method, it returns the iterator to the element one after the actual end of the array.
Hopefully this example gives the general idea of how to implement all iterator requirements.


Full source code is available here.