Keycode

template< class InputIterator, class Distance >
void advance( InputIterator &i, Distance n )
{
   if( is_random_access_iterator( I ) ) {
      advance_RAI( i, n );
   } else if( is_bidirectional_iterator( I ) ) {
      advance_BI( i, n );
   } else {
      advance_II( i, n );
   }
}

The disadvantage of this approach is which advance_xx() is going to be used is determined during runtime, not at compile time, and thus the performance is not ideal.

Overloading mechanism can address this problem.

// Define five tag types
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

These classes are only used as tags, and no need any members.

Now, the above advance_xx() functions can be written like below:

template< class InputIterator, class Distance >
inline void __advance( InputIterator &i, Distance n, input_iterator_tag )
{
   while( n-- ) ++I;
}

template< class ForwardIterator, class Distance >
inline void __advance( ForwardIterator &i, Distance n, forward_iterator_tag )
{
   advance( i, n, input_iterator_tag() );
}

template< class BidirectionalIterator, class Distance >
inline void __advance( BidirectionalIterator &i, Distance n, bidirectional_iterator_tag )
{
   if( n >= 0 ) {
      while( n-- ) ++i;
   } else {
      while( n++ ) --i;
   }
}

template< class RandomAccessIterator, class Distance >
inline void __advance( RandomAccessIterator &i, Distance n, random_access_iterator_tag )
{
   i += n;
}

The third parameter is only used to invoke overloading mechanism.

Now, the interface advance() is much simpler as below:

template< class InputIterator, class Distance >
void advance( InputIterator &i, Distance n )
{
   __advance( i, n, iterator_traits< InputIterator >::iterator_category() );
}

In addition, to achieve the above feature, traits needs another type:

template< class I >
struct iterator_traits {
   ...
   typedef typename I::iterator_category iterator_category;
};

// Partial specialisation for raw pointer
template< class T >
struct iterator_traits< T* > {
   ...
   // Note, raw pointer is of RandomAccessIterator
   typedef random_access_iterator_tag iterator_category;
};

// Partial specialisation for pointer-to-const
template< class T >
struct iterator_traits< const T* > {
   ...
   // Similarly, pointer-to-const is also of RandomAccessIterator
   typedef random_access_iterator_tag iterator_category;
};

In C++, template argument deduction doesn’t work for function return type. One solution is using nested type like below:

template< class T >
struct MyIter {
   typedef T value_type; // nested type
   T* ptr_;
   MyIter( T* p=nullptr ) : ptr_( p ){}
   T& operator*() const { return *ptr_; }
};


template< class I >
typename I::value_type func( I iter )
{
   return *iter;
}

// ...
MyIter< int > iter( new int(8) );
cout << func( iter ); // Output: 8 

A drawback of this approach is not all iters are of class type, e.g. raw pointer. It’s not possible to define nested type for a raw pointer.

Traits and Template partial specialisation can address this.

// Traits
template< class I >
struct iterator_traits
{ 
   typedef typename I::value_type value_type;
}

// Template Partial Specialisation for T*
template< class T >
typename iterator_traits< T* > 
{
   typedef T value_type;
}

// Template Partial Specialisation for const T*
template< class T >
typename iterator_traits< const T* > 
{
   typedef T value_type; // Note, here should be T rather than const T
}

The above func() could be written like below:

template< class I >
typename iterator_traits< I >::value_type func( I iter )
{
   return *iter;
}