Traits

Templates enable us to parameterize classes and functions for various types. If we want a fine grain template parametrization, that could lead unmanageble number of template parameter. Most template parameters may have default value, and other parameters could depend from them.

The traits and policy classes are the C++ template tools to manage this kind of dependent type parameters. We show these techniques in the followings:

An example for traits

Let suppose we have a normal template matrix class with the appropriate copy constructor. The copy constructor uses a for loop copying T elements from source to target.


#ifndef MATRIX_H
#define MATRIX_H

template <class T>
class matrix
{
public:
    matrix( int i, int j );
    matrix( const matrix &other);
    ~matrix();
    matrix operator=( const matrix &other);

    int rows() const { return x; }
    int cols() const { return y; }

    T& at( int i, int j) throw(indexError);
    T  at( int i, int j) const throw(indexError);
    T& operator()( int i, int j);
    T  operator()( int i, int j) const;
    
    matrix operator+=( const matrix &other);
private:
    int  x;
    int  y;
    T   *v;
    void copy( const matrix &other);
    void check( int i, int j) const throw(indexError);
};

template <class T>
matrix<T> operator+( const matrix<T> &x, const matrix<T> &y);
           

template <class T>
matrix<T>::matrix( int i, int j)
{
    x = i; 
    y = j;
    v = new T[x*y];
}
template <class T>
matrix<T>::matrix( const matrix &other)
{
    copy( other);
}
template <class T>
matrix<T>::~matrix()
{
    delete [] v;
}
template <class T>
matrix<T> matrix<T>::operator=( const matrix &other)
{
    if ( this != &other )
    {
        delete [] v;
        copy( other);
    }
    return *this;
}
template <class T>
void matrix<T>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new T[x*y];
    for ( int i = 0; i < x*y; ++i )
        v[i] = other.v[i];
}
template <class T>
void matrix<T>::check( int i, int j) const throw( indexError )
{
    if ( ( 0 <= i  && i < x ) && ( 0 <= j  && j < y ) )
        /* ok */ ;
    else
        throw indexError(i,j); 
}
template <class T>
T& matrix<T>::at( int i, int j) throw(indexError)
{
    check(i,j); 
    return operator()(i,j); 
}
template <class T>
T matrix<T>::at( int i, int j) const throw( indexError)
{ 
    check(i,j); 
    return operator()(i,j); 
}
template <class T>
T& matrix<T>::operator()( int i, int j)
{ 
    return v[i*y + j]; 
}
template <class T>
T matrix<T>::operator() ( int i, int j) const 
{ 
    return v[i*y + j]; 
}
template <class T>
matrix<T> matrix<T>::operator+=( const matrix &other)
{
    for ( int i = 0; i < x*y; ++i )
        v[i] += other.v[i];
    return *this;
}
template <class T>
matrix<T> operator+( const matrix<T> &x, const matrix<T> &y)
{
    matrix<T> temp( x );
    temp += y;
    return temp;
}

#endif /* MATRIX_H */

The client code can use these functions:


clude "trmatrix1.h"

using namespace std;

int main()
{
    matrix<int>    mi1(6,6), mi2(6,6);
    matrix<double> md1(5,5), md2(5,5);
    matrix<long>   ml1(2,2), ml2(2,2);

    mi2 = mi1;
    md2 = md1;
    ml2 = ml1;
    
    return 0;
}

All copy will instantiate the copy memberfunction, which uses a loop to copy the objects. However this is not necessary for trivial POD types: they can safely copied by a memcpy(void* target, void* source, int n) function.

We can try to specialize matrix for those types, which are bitwise copyable.


template <class T>
void matrix<T>::copy( const matrix &other)
{
    std::cerr << "elementary copy in loop" << std::endl;
    
    x = other.x;
    y = other.y;
    v = new T[x*y];
    for ( int i = 0; i < x*y; ++i )
        v[i] = other.v[i];
}
template <>
void matrix<long>::copy( const matrix &other)
{
    std::cerr << "bitwise copy for long" << std::endl;
    
    x = other.x;
    y = other.y;
    v = new long[x*y];
    memcpy( v, other.v, sizeof(long)*x*y);
}

This works, but far from the perfect solution:

  • We need a separate specialization for each type

  • The different type-specific code-fragments are speared into different places of the matrix-code.

Therefore we are using a trait class to concentrate the type specific information into one place:


template <typename T> 
struct copy_trait
{
    static void copy( T* to, const T* from, int n)
    {
        std::cerr << "default copy with loop" << std::endl;
        
        for( int i = 0; i < n; ++i )
            to[i] = from[i];
    }
};
template <> 
struct copy_trait<long>
{
    static void copy( long* to, const long* from, int n)
    {
        std::cerr << "bitwise copy for long" << std::endl;
        
        memcpy( to, from, n*sizeof(long));
    }
};

template <class T, class Cpy = copy_trait<T> >
class matrix
{
public:
    matrix( int i, int j );
    matrix( const matrix &other);
    ~matrix();
    matrix operator=( const matrix &other);

    int rows() const { return x; }
    int cols() const { return y; }

    T& at( int i, int j);
    const T&  at( int i, int j) const;
    T& operator()( int i, int j);
    const T&  operator()( int i, int j) const;
    
    matrix operator+=( const matrix &other);
private:
    int  x;
    int  y;
    T   *v;
    void copy( const matrix &other);
};

// ...

template <class T, class Cpy>
void matrix<T,Cpy>::copy( const matrix &other)
{
    x = other.x;
    y = other.y;
    v = new T[x*y];

    Cpy::copy( v, other.v, x*y);
}


Policy classes

The previous solution is a correct, easy maintenable code, where every concept is well-sepatated and clearly encapsulated. But we can still do it better.

We separate the policy of copy and the declarative part of the types:


#ifndef MATRIX_H
#define MATRIX_H

#include <iostream>

template <typename T>
struct is_pod
{
    enum { value = false };
};

template <>
struct is_pod<long>
{
    enum { value = true };
};

template <typename T, bool B> 
struct copy_trait
{
    static void copy( T* to, const T* from, int n)
    {
        std::cerr << "default copy with loop" << std::endl;
        
        for( int i = 0; i < n; ++i )
            to[i] = from[i];
    }
};
template <typename T> 
struct copy_trait<T, true>
{
    static void copy( T* to, const T* from, int n)
    {
        std::cerr << "bitwise copy for long" << std::endl;
        
        memcpy( to, from, n*sizeof(T));
    }
};

template <class T, class Cpy = copy_trait<T,is_pod<T>::value> >
class matrix
{
public:
    matrix( int i, int j );
    matrix( const matrix &other);
    ~matrix();
    matrix operator=( const matrix &other);

    int rows() const { return x; }
    int cols() const { return y; }

    T& at( int i, int j);
    const T&  at( int i, int j) const;
    T& operator()( int i, int j);
    const T&  operator()( int i, int j) const;
    
    matrix operator+=( const matrix &other);
private:
    int  x;
    int  y;
    T   *v;
    void copy( const matrix &other);
};

We can still overrule the default behaviour: for example we can specify a matrix of doubles with default copy strategy and one with the memcopy strategy.


#include "trmatrix4.h"

using namespace std;

int main()
{
    matrix<int>    mi1(6,6), mi2(6,6);
    matrix<double> md1(5,5), md2(5,5);
    matrix<double, copy_trait<double,true> > md3(5,5), md4(5,5);
    matrix<long>   ml1(2,2), ml2(2,2);

    mi2 = mi1;
    md2 = md1;
    md4 = md3;
    ml2 = ml1;
    
    return 0;
}

The perfect solution is however to use type_traits. See in Loki.

More traits

One of the simpliest STL algorithm is the following function, to exchange the value of the objects the two iterator refer to.


template <class ForwardIterator1, class ForwardIterator2>
void iter_swap( ForwardIterator1 it1, ForwardIterator2 it2)
{
    T tmp = *it1;
    *it1  = *it2;
    *it2  = tmp;
}

Ok, but what is T? How to define the type of the objects. One idea is to refer the value_type of the iterator:


template <class ForwardIterator1, class ForwardIterator2>
void iter_swap( ForwardIterator1 it1, ForwardIterator2 it2)
{
    typename ForwardIterator1::value_type tmp = *it1;
    *it1  = *it2;
    *it2  = tmp;
}

But this is not a good solution. If the types are ordinary pointers, we are in trouble. Ordinary pointers have no members, and therefore has no value_type.


void f(int *p1, int *p2)
{
    iter_swap(p1,p2);   // error!
}

We can solve any problem, by introducing an extra level of indirection. - Butler Lampson

This is sometime called as the Fundamental Theorem of Software Engineering". This time the extra level is called iterator_traits. This is the way to define value_type without modify the iterator itselves. That we can associate information with a type in non-intrusive way.


template <class Iterator> struct iterator_traits;

template <class ForwardIterator1, class ForwardIterator2>
void iter_swap( ForwardIterator1 it1, ForwardIterator2 it2)
{
    typename terator_traits<ForwardIterator1>::value_type tmp = *it1;
    *it1  = *it2;
    *it2  = tmp;
}

namespace std
{
    template <>
    struct iterator_traits<T*>
    {
        typedef T  value_type;
        typedef T& reference;
        typedef T* pointer;
        typedef ptrdiff_t difference_type;
        typedef random_access_iterator_tag iterator_category;
    };
}

For the ease of use there is a shortcut: The default definition of the iterator_traits has default type for value_type:


template <class Iterator>
struct iterator_traits
{
    typedef typename Iterator::value_type value_type;
    //...
};

Character Trait

The most famous example for traits is the char_traits.


template<class Ch> struct char_traits { };

template<> struct char_traits<char>
{   // char_traits operations should not throw exceptions
    typedef char char_type;     // type of character

    static void assign(char_type&, const char_type&);   // = for char_type

    // integer representation of characters:
    typedef int int_type;       // type of integer value of character

    static char_type to_char_type(const int_type&); // int to char conversion
    static int_type to_int_type(const char_type&);  // char to int conversion
    static bool eq_int_type(const int_type&, const int_type&);  // ==

    // char_type comparisons:
    static bool eq(const char_type&, const char_type&); // ==
    static bool lt(const char_type&, const char_type&); // <

    // operations on s[n] arrays:
    static char_type* move(char_type* s, const char_type* s2, size_t n);
    static char_type* copy(char_type* s, const char_type* s2, size_t n);
    static char_type* assign(char_type* s, size_t n, char_type a);

    static int compare(const char_type* s, const char_type* s2, size_t n);
    static size_t length(const char_type*);
    static const char_type* find(const char_type* s, int n, const char_type&);

    // I/O related:
    typedef streamoff off_type;     // offset in stream
    typedef streampos pos_type;     // position in stream
    typedef mbstate_t state_type;   // multi-byte stream state

    static int_type eof();              // end-of-file
    static int_type not_eof(const int_type& i); // i unless i equals eof(); if not any value!=eof()
    static state_type get_state(pos_type p);    // multibyte conversion state of character in p
};

template<> struct char_traits<wchar_t>
{
    typedef wchar_t char_type;
    typedef wint_t int_type;
    typedef wstreamoff off_type;
    typedef wstreampos pos_type;

    // like char_traits<char>
};

template<class Ch, class Tr = char_traits<Ch>, class A = allocator<Ch> >
class std::basic_string
{
public:
    // ...
};

Case Insensitive String with Traits

We can define a trait for a case insensitive string behaviour. Since we are in an object-oriented language :-), we don't need to reproduce the whole char_traits<>, it is enough to redefine those parameters, which are differ from the default.


#ifndef CISTRING_H
#define CISTRING_H

#include <string>

//using namespace std;

struct ci_char_traits : public std::char_traits<char>
{
    static bool eq( char c1, char c2)
    {
        return toupper(c1) == toupper(c2);
    }
    static bool lt( char c1, char c2)
    {
        return toupper(c1) < toupper(c2);
    }
    static int compare( const char *s1, const char *s2, size_t n)
    {
        return memicmp( s1, s2, n);     // non-standard !
    }
    static const char *find( const char *s, int n, char ch)
    {
        while ( n-- > 0  &&  toupper(*s) != toupper(ch) )
        {
            ++s;
        }
        return n > 0 ? s : 0;
    }
};

typedef std::basic_string<char, ci_char_traits> ci_string;

#endif /* CISTRING_H */

Now we can define the case-insensitive string class.


#include <iostream>
#include <string>
#include "cistring1.h"

using namespace std;

int main()
{
    string s1("hELlo");
    string s2("HEllo");

    cout << boolalpha << (s1 == s2) << endl;

    ci_string cs1("hELlo");
    ci_string cs2("HEllo");

    cout << boolalpha << (cs1 == cs2) << endl;

    return 0;
}

Problem with traits

There is no such thing as a free supper. Every facility has a tarde-off. Since traits are compile-time tools, we have problems when try to mix strings with different trait parameters:


#include <iostream>
#include <string>
#include "cistring1.h"

using namespace std;

int main()
{
    string s1("hELlo");
    string s2("HEllo");

    cout << boolalpha << (s1 == s2) << endl;

//    ci_string cs1("hELlo");
//    ci_string cs2("HEllo");
    ci_string cs1 = "hELlo";
    ci_string cs2 = "HEllo";

    cout << cs1 << ", " << cs2 << endl;  // syntax error !
/*
    template <class charT, class Traits, class Allocator>
    basic_ostream<charT, Traits>&
        operator<< (basic_ostream<charT, Traits>& os,
                    const basic_string<charT, Traits, Allocator>& str)

    cout has type:  basic_ostream<char, char_traits<char> > !
 */

    cs1 += s1;  // syntax error !

    return 0;
}