Tag: C++

Traits and Template Partial Specialisation – 2

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;
};

Traits and Template Partial Specialisation – 1

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;
}

What if the derived class in CRTP is a template class?

CRTP (Curiously Recurring Template Pattern) is a very useful skill to achieve static polymorphism.

How to achieve CRTP if the derived class is a template class? Here is an example.

#include <iostream>
#include <string>

using namespace std;

// Base class A
template< typename Type, template< typename > class Derived >
class A {
  public:
    A() = default;
    virtual ~A() = default;
    
    void output( Type num ) {
      cout << "From base A, ";
      static_cast< Derived< Type > * > (this)->speak( num );
    }
    
  protected:
    virtual void speak( Type num ) = 0;
};

// Derived class B, override the protected method speak()
template< typename Type >
class B : public A< Type, B > {
  friend class A< Type, B >;
  public:
    using A< Type, B >::A;
    
  protected:
    void speak( Type num ) override {
      cout << "I am B, and I got " << std::to_string( num ) << endl;
    }      
};

// Derived class C, override the protected method speak()
template< typename Type >
class C : public A< Type, C > {
  friend class A< Type, C >;
  public:
    using A< Type, C >::A;
    
  protected:
    void speak( Type num ) override {
      cout << "I am C, and I got " << std::to_string( num ) << endl;
    }   
};

// Client code
int main(int argc, char** argv) {
  B< float > b;
  b.output( 5 );
  
  C< float > c;
  c.output( 8 );

  return 0;
}

Use g++ to compile the above code, and get the outputs.

g++ -o crtptest main.cpp --std=c++14
./crtptest
From base A, I am B, and I got 5.000000
From base A, I am C, and I got 8.000000