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.

implementing custom STL-compatible iterator.

Several days ago I was implementing a small class structure which had to be compatible with standard STL algorithms. STL was designed to separate data-containers and algorithms that allow to do lots of different things with the data stored. So basically the only common thing between standard C++ containers and algorithms are iterators.

Let's implement our custom STL-compatible InputIterator, which would take the begining and the end iterators of a sequence as input parameters and return all even numbers in it. Well, actually it would return any value of a type that contains overloaded operator% that returns zero.

An InputIterator class has some requirements:
1. Iterator class must have default constuctor, copy-constructor and overloaded operator=().
2. The InputIterator can only be moved forward in the predefined range of values. So that is why operator++() (for prefix increment), operator++(int) (for postfix increment), operator==() and operator!=() must be overloaded also.
3. In order to get the value iterator points to, operator*() and operator->() must be overloaded.

There is the base template class in STL:

template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
            typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
   typedef _Category  iterator_category;
   typedef _Tp        value_type;
   typedef _Distance  difference_type;
   typedef _Pointer   pointer;
   typedef _Reference reference;
};

these type definitions are needed for all the algorithms, which we want to use with our

iterator implementation. 

iterator_category - the iterator type,  in our case it is going to

be  struct input_iterator_tag { }; 

value_type - defines the type of the value iterator points to.

difference_type - defines the type of the difference between two iterators

of the sequence.

pointer and reference - types of the pointer and reference to the value. 

So our even numbers iterator looks like that:

template<typename IterT, typename TypeT>
class even_iterator :
 public std::iterator<input_iterator_tag, TypeT>
{
protected:
 IterT m_itCur;
 IterT m_itEnd;

protected:
 void __find_first_even()
 {
  for (; m_itCur != m_itEnd; ++m_itCur)
   if (*m_itCur % 2 == 0) break;
 }

 void __find_next_even()
 {
  if (m_itCur == m_itEnd) return; 
  for (++m_itCur; m_itCur != m_itEnd; ++m_itCur)
   if (*m_itCur % 2 == 0) break;
 }
 
public:
 even_iterator() :
  m_itEnd(), m_itCur() {}

 even_iterator(const IterT& itCur, const IterT& itEnd) : 
  m_itCur(itCur), m_itEnd(itEnd)
 { __find_first_even(); } 
 
 even_iterator(const even_iterator& r) : 
  m_itCur(r.m_itCur),
  m_itEnd(r.m_itEnd) {}
 
 even_iterator<IterT, TypeT>& operator=(const even_iterator& r)
 {
  m_itCur = r.m_itCur;
  m_itEnd = r.m_itEnd;
  
  return *this;
 }
 
 even_iterator<IterT, TypeT>& operator++()
 {
  __find_next_even();  
  return *this;
 }

 even_iterator<IterT, TypeT> operator++(int)
 {
  even_iterator it = *this;
  __find_next_even();  
  return it;
 }
 
 TypeT& operator*()
   { return *m_itCur; }
 
 TypeT* operator->()
   { return &(*m_itCur); }
 
 bool operator!=(const even_iterator& r) const
   { return (m_itCur != r.m_itCur); }
 
 bool operator==(const even_iterator& r) const
   { return !operator!=(r); }
};

In order to check that our iterator works fine with algorithm STL-library, lets check it with the std::copy function:

int main(int argc, char* argv[])
{ 
 srand((unsigned int) time(NULL));
 
 vector<int> vnNums(20);
 for (size_t u = 0; u < 20; ++u)
  vnNums[u] = rand() / (float) RAND_MAX * 100;
  
 cout << "initial vector:" << endl;
 copy(vnNums.begin(), vnNums.end(), ostream_iterator(cout, "\t"));
 cout << endl;
 
 
 typedef even_iterator<vector&lgt;int>::const_iterator, const int> int_vec_even_iter;
 
 cout << "even vector:" << endl;
 
 copy(int_vec_even_iter(vnNums.begin(), vnNums.end()),
   int_vec_even_iter(vnNums.end(), vnNums.end()),
   ostream_iterator<int>(cout, "\t")
   );
 cout << endl;

 return 0;
} 

To create even_iterator instance I've used it's constructor:

 even_iterator(const IterT& itCur, const IterT& itEnd);

where the first parameter defines the begining of the source sequence, and the second argument sets the end of the sequence.

As it was shown in the std::copy example

 copy(int_vec_even_iter(vnNums.begin(), vnNums.end()),
   int_vec_even_iter(vnNums.end(), vnNums.end()),
   ostream_iterator<int>(cout, "\t")
   );

in order to define the iterator that points to the end of the source sequence I used constructor:

int_vec_even_iter(vnNums.end(), vnNums.end())