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())