EMACS & 程序编程点滴...

泛型编程和面向对象编程不同，它并不要求你通过额外的间接层来调用函数，它让你编写完全一般化并可重复使用的算法，其效率与针对某特定数据类型而设计的算法相同。泛型编程的代表作品STL是一种高效、泛型、可交互操作的软件组件。所谓泛型(Genericity)，是指具有在多种数据类型上皆可操作的含意，与模板有些相似。STL巨大，而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。 STL以迭代器(Iterators)和容器(Containers)为基础，是一种泛型算法(Generic Algorithms)库，容器的存在使这些算法有东西可以操作。STL包含各种泛型算法(algorithms)、泛型指针(iterators)、泛型容器(containers)以及函数对象(function objects)。STL并非只是一些有用组件的集合，它是描述软件组件抽象需求条件的一个正规而有条理的架构。

TOP模板

通过使用模板可以使程序具有更好的代码重用性。
模板是对源代码进行重用，而不是通过继承和组合重用对象代码，当用户使用模板时，参数由编译器来替换。
模板由类模板和函数模板二部分组成，以所处理的数据类型的说明作为参数的类就叫类模板，而以所处理的数据类型的说明作为参数的函数叫做函数模板。
模板参数可以由类型参数或非类型参数组成，类型参数可用class和typename关键字来指明，二者的意义相同，都表示后面的参数名代表一个潜在的内置或用户定义的类型，非类型参数由一个普通参数声明构成。

基本的模板技术

以下罗列出各种模板技术¹。

TOPTemplate Arguments versus Template Parameters

template <typename T, int N>
class ArrayInClass {
  public:
      T array[N];
};

template <typename T>
class Dozen {
public:
    ArrayInClass<T,12> contents;
public:
    void  setValue(T value) {
        for(int i = 0; i< 12; i++) {
            contents.array[i] = value;
        }
    }
};

int main()
{
    ArrayInClass<double,10> ad;
    ad.array[0] = 1.0;

    Dozen<char> test;
    test.setValue('A');

    return 0;
}

TOPClass template full specialization

template<class T, class U>
int Partial_Test<T,U>::high()
{
    return __t.high() + __u.high();
}

template<class T, class U>
int Partial_Test<T,U>::weight()
{
    return __t.weight() + __u.weight();
}

template<>
class Partial_Test<Horse,Cat>
{
public:
    int high();
    int weight();

    Horse  __horse;
    Cat    __cat;
};

int Partial_Test<Horse,Cat>::high()
{
    return __horse.high()/2 + __cat.high()*3;
}

int Partial_Test<Horse,Cat>::weight()
{
    return __horse.weight()/2 + __cat.weight()*3;
}

TOPClass template partial specialization

template<int Base, int Exponent>
class XY
{
public:
    enum { result_ = Base * XY<Base, Exponent-1>::result_ };
};
template<int Base>
class XY<Base, 0>  // partial specialization
{
public:
    enum { result_ = 1 };
};

int main()
{
    printf("X^Y<5, 4>::result_ = %d\n" , XY<5, 4>::result_);
    return 0;
}

template<class T>
class Partial_Test<T,Dog>
{
public:
    int high();
    int weight();

    typedef T   type_T;

    type_T   __t;
    Dog  __dog;
};

template<class T>
int Partial_Test<T,Dog>::high()
{
    return __t.high() + __dog.high()*2;
}
template<class T>
int Partial_Test<T,Dog>::weight()
{
    return __t.weight() + __dog.weight()*3;
}

TOPSeparate compilation model for function template (Exported templates)

// test_export_template.hpp
export template <typename T> void fun(T t);

//test_export_template.cpp
#include "test_export_template.hpp"

template <typename T>
void fun(T t)
{
    printf("---------%d--------\n",t);
}

// test_main.cpp
#include "test_export_template.hpp"

int main()
{
    fun(100);
    return 0;
}

TOPMember templates

template <class T>
class Queue {
public:
        // class member template
        template <class Type>
        class CL
        {
           Type member;
           T mem;
        };
public:
        // function member template
        template <class Iter>
        void assign( Iter first, Iter last )
        {
            printf("Queue<T>::assign()\n");
        }
};
int  main()
{
  // nested types
  Queue<int>::CL<char> c;
  Queue<int>::CL<long> s;

  // instantiation of Queue<int>
  Queue<int> qi;

  // instantiation of Queue<int>::assign( int *, int * )
  int ai[4] = { 0, 3, 6, 9 };
  qi.assign(ai, ai+4);

  return 0;
}

TOPAuto export types by compiler

template <class T1, class T2, class T3>
T1 sum( T2 v2, T3 v3)
{
    return T1(v2+v3);
}

typedef unsigned int ui_type;

ui_type calc( char ch, ui_type ui )
{
    ui_type (*pf)( char, ui_type ) = &sum< ui_type >;

    ui_type loc = (*pf)(ch, ui);
    return loc;
}

int main()
{
    printf("...%d",calc('c', ui_type(1024)));
    return 0;
}

TOPSpecify function template’s types

template <class T1, class T2, class T3>
   T1 sum( T2 op1, T3 op2 ) { /* ... */ return T1(10); }

void manipulate( int (*pf)( int,char ) ) { };
void manipulate( double (*pf)( float,float ) ) { };

int  main( )
{
    manipulate( &sum< double, float, float > );
    return 0;
}

TOPFun-template explicit specialization

template <class T1, class T2, class T3>
T1 sum(T2 op1, T3 op2)
{
    printf("generic form\n");
    return static_cast<T1>(op1+op2);
}

template<> double sum<double>(float op1, float op2)
{
    printf("specialization form1\n");
    return static_cast<double>(op1+op2);
}

template<> int sum<int, char, char>(char op1, char op2)
{
    printf("specialization form2\n");
    return static_cast<int>(op1+op2);
}

int main()
{
    int i=5;
    char c='a';
    float f=4.5;
    double d=6.5;

    printf("....%d....\n", sum<int>(i, i));
    printf("....%f....\n", sum<double>(f, f));
    printf("....%d....\n", sum<int>(c, c));
    return 0;
}

TOPClass template with friend function

template <typename T> class A;
template <typename T> void get (const A<T>& a);

template <typename T> class B;
template <typename T> void put (const B<T>& b);

template <typename T>
class A
{
    friend void get<T>(const A<T>& a);
public:
    A (T i) : _i(i) {
        front = new B<T>(i);
        back  = new B<T>(i);
    }
    ~A() {
        if (front) {
            delete front;
        }
        if (back) {
            delete back;
        }
    }
private:
    T _i;
    B<T>* front;
    B<T>* back;
};

template <typename T>
void get(const A<T>& a)
{
    printf("------ %d ----- %d -------\n",(a.front),(a.back));
}

template <typename T>
class B
{
    friend void put<T>(const B<T>& b);
public:
    B (T i) : _item(i), _value(i) { }
private:
    T _item;
public:
    T  _value;
};

template <typename T>
void put(const B<T>& b)
{
    printf("------ %d -------\n",b._item);
}

int  main()
{
    A<int>   a1(5);
    A<float> a2(5.4);
    A<char>  a3('a');
    B<long>  b1(3);

    get(a1);
    get(a2);
    get(a3);
put(b1);

    return 0;
}

TOPClass template with friend function(with nest types)

template <typename T> class A;
template <typename T> void get (const A<T>& a);

template <typename T>
class A
{
    friend void get<T>(const A<T>& a);
private:
    class B   // nested class
    {
    public:
        B (T i) : _item(i) { }
        T _item;
    };

    public:
        A (T i) : _i(i) {
            front = new B(i);
            back  = new B(i);
        }
        ~A()
        {
            if (front) delete front;
            if (back) delete back;
        }

    private:
        T _i;
        B* front;
        B* back;
};

template <typename T>
void get(const A<T>& a)
{
    printf("------ %d ----- %d -------\n",(a.front),(a.back));
}

int  main()
{
    A<int>   a1(5);
    A<float> a2(5.4);
    A<char>  a3('a');

    get(a1);
    get(a2);
    get(a3);

    return 0;
}

TOPTemplate template parameters

template <typename T>
struct CompareCat
{
    T    __obj;
    Cat  __cat;

    bool compare()
    {
        return (__obj.weight() - __cat.weight());
    }
};

template <typename T>
struct CompareDog
{
    T    __obj;
    Dog  __dog;

    bool compare()
    {
        return (__obj.weight() - __dog.weight());
    }
};

template <typename T>
struct CompareHorse
{
    T      __obj;
    Horse  __horse;

    bool compare()
    {
        return (__obj.weight() - __horse.weight());
    }
};

template <template <class> class Animal>
class DogZoo : public Animal<Dog>
{
public:
    bool horse_compare()
    {
        return Animal<Horse>().compare();
    }

    bool cat_compare()
    {
        return Animal<Cat>().compare();
    }

};

typedef DogZoo<CompareDog> MyDogZoo;

int main()
{
    MyDogZoo zoo;

    printf("---- dog's compare %d --- \n",zoo.compare());

    printf("---- horse_compare's compare %d --- \n",zoo.horse_compare());
    printf("---- cat_compare's compare %d --- \n",zoo.cat_compare());
    return 0;
}

TOPCompile-time Assertions

template<bool>
struct CompileTimeChecker
{
    CompileTimeChecker(...);
};
template<> struct CompileTimeChecker<false> {};

#define STATIC_CHECK(expr, msg)\
{\
    class ERROR_##msg {}; \
    (void)sizeof(CompileTimeChecker<(expr)>(ERROR_##msg()));\
}


template <class To, class From>
To safe_reinterpret_cast(From from)
{
    STATIC_CHECK(sizeof(From) <= sizeof(To),Destination_Type_Too_Narrow);
    return reinterpret_cast<To>(from);
}


const char *str = "12345\n54321\09999";

struct Dog {
    const char* name(){
        return str;
    }
    int age(){
        return 10;
    }
};

int main()
{
    Dog dog;

    void* somePointer = &dog;
    char c = safe_reinterpret_cast<char>(somePointer);

    return 0;
}

TOPLocal classes

template <class T, class P>
IAnimal* MakeAnimal(const T& obj, const P& arg)
{
    class Local : public IAnimal
    {
    public:
        Local(const T& obj, const P& arg)
            : obj_(obj), arg_(arg) {}
        virtual int    weight()
        {
            return obj_.weight() + arg_.weight();
        }
        virtual int    high()
        {
            return obj_.high() + arg_.high();
        }
    private:
        T obj_;
        P arg_;
    };
    return new Local(obj, arg);
}

int main()
{
    Dog dog;
    Horse horse;
    IAnimal* panimal = MakeAnimal(dog,horse);
    printf("---the animal's weight %04x --- \n",panimal->weight());
    printf("---the animal's high %04x --- \n",panimal->high());

    delete panimal;
    return 0;
}

TOPType mapping (int2Type)

template <int v>
struct Int2Type
{
    enum { value = v };
};

template <typename T, bool isMul>
class NiftyContainer
{
private:
    int DoSomething(T* pObj, Int2Type<true>)
    {
        return pObj->weight()*pObj->high();
    }
    int DoSomething(T* pObj, Int2Type<false>)
    {
        return pObj->weight()/pObj->high();
    }
public:
    int DoSomething(T* pObj)
    {
        return DoSomething(pObj, Int2Type<isMul>());
    }
};

int main()
{
    NiftyContainer<Dog,true> dog;
    NiftyContainer<Horse,false> horse;

    Dog    __dog;
    Horse  __horse;

    printf("---the animal %04x --- \n",dog.DoSomething(&__dog));
    printf("---the animal %04x --- \n",horse.DoSomething(&__horse));

    return 0;
}

TOPType mapping (Type2Type)

template <typename T>
struct Type2Type
{
    typedef T OriginalType;
};
template <class T, class U>
int  high(const U& arg, Type2Type<T>)
{
    return arg->high();
}
template <class U>
int  high(const U& arg, Type2Type<Dog>)
{
    Dog dog;
    return arg->high()+dog.high();
}
int main()
{
    Horse  __horse;
    printf("---the animal's high %04x --- \n",high(&__horse,Type2Type<Cat>()));
    printf("---the animal's high %04x --- \n",high(&__horse,Type2Type<Dog>()));
    return 0;
}

TOPType selection

template <bool flag, typename T, typename U>
struct Select
{
    typedef T Result;
};
template <typename T, typename U>
struct Select<false, T, U>
{
    typedef U Result;
};
template <typename T, bool isMul>
class NiftyContainer
{
    typedef typename Select<isMul, T*, T>::Result      ValueType;

private:
    ValueType DoSomething(T* pObj, Int2Type<true>)
    {
        return pObj;
    }
    ValueType DoSomething(T* pObj, Int2Type<false>)
    {
        return *pObj;
    }
public:
    ValueType DoSomething(T* pObj)
    {
        return DoSomething(pObj, Int2Type<isMul>());
    }
};
int main()
{
    NiftyContainer<Dog,true> dog;
    NiftyContainer<Horse,false> horse;

    Dog    __dog;
    Horse  __horse;

    printf("---the animal high %04x --- \n",dog.DoSomething(&__dog)->high());
    printf("---the animal high %04x --- \n",horse.DoSomething(&__horse).high());

    return 0;
}

TOPDetecting convertibility and Inheritance at compile time

template <class T, class U>
struct ConversionHelper
{
    typedef char Small;
    struct Big { char dummy[2]; };
    static Big   Test(...);
    static Small Test(U);
    static T MakeT();
};

template <class T, class U>
struct Conversion
{
    typedef ConversionHelper<T, U> H;
#ifndef __MWERKS__
    enum { exists = sizeof(typename H::Small) == sizeof((H::Test(H::MakeT()))) };
#else
    enum { exists = false };
#endif
    enum { exists2Way = exists && Conversion<U, T>::exists };
    enum { sameType = false };
};

template <class T>
struct Conversion<T, T>
{
    enum { exists = 1, exists2Way = 1, sameType = 1 };
};

template <class T>
struct Conversion<void, T>
{
    enum { exists = 0, exists2Way = 0, sameType = 0 };
};

template <class T>
struct Conversion<T, void>
{
    enum { exists = 0, exists2Way = 0, sameType = 0 };
};

template <>
struct Conversion<void, void>
{
public:
    enum { exists = 1, exists2Way = 1, sameType = 1 };
};


template <class T, class U>
struct SuperSubclass
{
  enum { value = (Conversion<const volatile U*, const volatile T*>::exists &&
                  !Conversion<const volatile T*, const volatile void*>::sameType) };
};


template<class T,class U>
struct SuperSubclassStrict
{
  enum { value = (Conversion<const volatile U*, const volatile T*>::exists &&
                 !Conversion<const volatile T*, const volatile void*>::sameType &&
                 !Conversion<const volatile T*, const volatile U*>::sameType) };
};


#define SUPERSUBCLASS(T, U) \
    SuperSubclass<T,U>::value

#define SUPERSUBCLASS_STRICT(T, U) \
    SuperSubclassStrict<T,U>::value
int main()
{
    printf("---  SUPERSUBCLASS test  %d  --- \n",SUPERSUBCLASS(Dog,IAnimal));
    printf("---  SUPERSUBCLASS test  %d  --- \n",SUPERSUBCLASS(IAnimal,Dog));

    printf("---  SUPERSUBCLASS test  %d  --- \n",SUPERSUBCLASS(Cat,ICat));
    printf("---  SUPERSUBCLASS test  %d  --- \n",SUPERSUBCLASS(ICat,Cat));

    printf("---  SUPERSUBCLASS test  %d  --- \n",SUPERSUBCLASS(Cat,Dog));
    printf("---  SUPERSUBCLASS test  %d  --- \n",SUPERSUBCLASS(Dog,Cat));

    return 0;
}

应用于设计的模板技术

TOPTraits and Policy Classes

这里和这里有一些介绍Traits技术的，利用它，我们可以取出类成员类型或是变量。首先是Type Traits，基本的形式如下：

struct __true_type {};
struct __false_type {};

template <class T>
struct TypeTraits {
    typedef __true_type     this_dummy_member_must_be_first;
    typedef __false_type    has_trivial_default_constructor;
    typedef __false_type    has_trivial_copy_constructor;
    typedef __false_type    has_trivial_assignment_operator;
    typedef __false_type    has_trivial_destructor;
    typedef __false_type    is_POD_type;
};

// 一个特化的类型
template<> struct TypeTraits<bool> {
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

// partial-specialization的版本
template <class T>
struct TypeTraits<T*> {
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

以下是测试代码：

template <typename T>
void __copy(T* destination,const T* source,int size,__false_type)
{
    destination->clone(source);
}

template <typename T>
void __copy(T* destination,const T* source,int size,__true_type)
{
    memcpy(static_cast<void *>(destination),static_cast<const void*>(source),size);
}

template <typename T>
void copy(T* destination,const T* source,int size)
{
    __copy(destination,source,size, typename TypeTraits<T>::has_trivial_copy_constructor());
}

class TestClass {
private:
    int             _age;
    char*           _name;
public:
    TestClass(): _age(0),_name(NULL) {}
    ~TestClass() {
        if (_name) {
            delete _name; _name = NULL;
        }
    }
    void    clone(const TestClass* pobj)
    {
        _age = pobj->_age;
        _name = new char(strlen(pobj->_name)+1);
        strcpy(_name,pobj->_name);
    }
public:
    inline void    setName(const char* name)
    {
        _name = new char(strlen(name)+1);
        strcpy(_name,name);
    }

    inline void    setAge(int age)
    {
        _age = age;
    }
};

// 测试代码的type_traits特殊化
template<> struct TypeTraits<TestClass> {
    typedef __true_type      has_trivial_default_constructor;
    typedef __false_type     has_trivial_copy_constructor;
    typedef __false_type     has_trivial_assignment_operator;
    typedef __false_type     has_trivial_destructor;
    typedef __false_type     is_POD_type;
};

int main()
{
    TestClass test1,test2;

    test1.setAge(100);
    test1.setName("the elder");

    copy(&test2,&test1,sizeof(test1));

    return 0;
}

再看看Iterator Traits:

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

// 以下是迭代器的base类型，所有的迭代器需从它继承
template <class _Category,
          class _Tp,
          class _Distance = ptrdiff_t,
          class _Pointer = _Tp*,
          class _Reference = _Tp&>
struct iterator {
    typedef _Category  iterator_category;
    typedef _Tp        value_type;
    typedef _Distance  difference_type;
    typedef _Pointer   pointer;
    typedef _Reference reference;
};

// eg. istreambuf_iterator的实现
template<class _CharT, class _Traits>
class istreambuf_iterator : public iterator<input_iterator_tag,
                                            _CharT,
                                            typename _Traits::off_type,
                                            _CharT*,
                                            _CharT&>
{
public:
    typedef _CharT                           char_type;
    typedef _Traits                          traits_type;
    typedef typename _Traits::int_type       int_type;
    typedef basic_streambuf<_CharT, _Traits> streambuf_type;
    typedef basic_istream<_CharT, _Traits>   istream_type;

public:
    istreambuf_iterator(streambuf_type* __p = 0);
    istreambuf_iterator(istream_type& __is);

    char_type operator*() const;

    istreambuf_iterator& operator++();
    istreambuf_iterator  operator++(int);
    bool equal(const istreambuf_iterator& __i) const;
    ...
};

// iterator_traits
template <class _Iterator>
struct iterator_traits {
    typedef typename _Iterator::iterator_category  iterator_category;
    typedef typename _Iterator::value_type        value_type;
    typedef typename _Iterator::difference_type   difference_type;
    typedef typename _Iterator::pointer           pointer;
    typedef typename _Iterator::reference         reference;
};

// partial-specialization版本
template <class _Tp>
struct iterator_traits<_Tp*> {
    typedef random_access_iterator_tag   iterator_category;
    typedef _Tp                         value_type;
    typedef ptrdiff_t                   difference_type;
    typedef _Tp*                        pointer;
    typedef _Tp&                        reference;
};
template <class _Tp>
struct iterator_traits<const _Tp*> {
    typedef random_access_iterator_tag   iterator_category;
    typedef _Tp                        value_type;
    typedef ptrdiff_t                    difference_type;
    typedef const _Tp*                  pointer;
    typedef const _Tp&                  reference;
};

// 利用下面的函数，可以得到迭代器的类型
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
iterator_category(const _Iter&)
{
    typedef typename iterator_traits<_Iter>::iterator_category _Category;
    return _Category();
}

// 以用下面的函数，得到迭代器的distance type
template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
distance_type(const _Iter&)
{
    return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
}

// 取得迭代器的value type
template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
value_type(const _Iter&) {
    return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
}

// 以下为测试代码
template <class _InputIterator,class T>
void __assign( _InputIterator first, _InputIterator last, const T& value, input_iterator_tag) {
    printf("--------input_iterator_tag -----------\n");
}

template <class _OutputIterator,class T>
void __assign( _OutputIterator first, _OutputIterator last,
              const T& value, output_iterator_tag) {
    printf("--------output_iterator_tag -----------\n");
}

template <class _RandomAccessIterator,class T>
void __assign( _RandomAccessIterator first, _RandomAccessIterator last,
              const T& value, random_access_iterator_tag) {
    printf("--------random_access_iterator_tag -----------\n");
}

template <class Iter,class T>
void assign( Iter first, Iter last, const T& value) {
    typedef typename iterator_traits<Iter>::iterator_category _Category;
    __assign(first,last,value,_Category());
}

class test_iterator : public iterator<input_iterator_tag, char> {
    //........
};

int  main()
{
    test_iterator first,last;
    assign(first, last,100);

    return 0;
}

TOPTemplates and Inheritance

TOPThe Empty Base Class Optimization (EBCO)

利用C++模板的泛型编程技术中，经常使用空类对象The Empty Base Class Optimization (EBCO)。它们通常只是定义了一些typedef或者是一些成员函数。缺省的被其他类使用。当然你可以继承它，替换它们的缺省实现来满足自己的需要。正因为是缺省的，所以要做到最轻量，优化。不占用空间就是空对象的最大特征之一。C++标准库正是利用这一特征来优化许多组件，不至于使代码过于膨胀。

例如以下的类：

template <class T>
    class allocator {   // an empty class
      . . .
      static T* allocate(size_t n)
        { return (T*) ::operator new(n * sizeof T); }
      . . .
};

怎样使用这一特征呢？看以下的例子：

// 一个空对象
struct Bar { };

// 如果像这样使用空对象，是不可能省下空间的。
// 以下的Baz对象仍旧是8个字节。
// b虽然只占了一个字节，但是因为对齐的原因，实际上是8个字节。
struct Baz {
    Bar b;
    int* p;
};

// 如果这样使用，那么基类就被认为是空基类，尺寸是0
struct Baz2 : Bar {
    int* p;
};

// 我们已经知道了allocator是个空对象，内嵌类P从allocator继承
// allocator的尺寸是0！
// 在容器类list中通过head_成员来分配空间
template <class T, class Alloc = allocator<T> >
    class list {
      . . .
      struct Node { . . . };
      struct P : public Alloc {
        P(Alloc const& a) : Alloc(a), p(0) { }
        Node* p;
      };
      P head_;

     public:
      explicit list(Alloc const& a = Alloc())
        : head_(a) { . . . }
      . . .
};

// 我们可以将这个方法用模板封装起来
// 以后在类中声明BaseOpt的对象就可以了
template <class Base, class Member>
struct BaseOpt : Base
{
    Member m;
    BaseOpt(Base const& b, Member const& mem)
    : Base(b), m(mem)
    { }
};

template <class T, class Alloc = allocator<T> >
class list {
    ...
    struct Node { . . . };
    BaseOpt<Alloc,Node*> head_;
public:
    explicit list(Alloc const& a = Alloc()) : head_(a,0)
    { . . . }
    . . .
};

TOPThe Curiously Recurring Template Pattern (CRTP)

利用The Curiously Recurring Template Pattern (CRTP)可以实现静态的多态。其原理就像是以下的代码，将子类自身作为基类的模板参数。

template <typename CountedType>
class ObjectCounter {
  private:
      static size_t count;    // number of existing objects
  protected:
      // default constructor
      ObjectCounter() {
          ++ObjectCounter<CountedType>::count;
      }
      // copy constructor
      ObjectCounter (ObjectCounter<CountedType> const&) {
          ++ObjectCounter<CountedType>::count;
      }
      // destructor
      ~ObjectCounter() {
          --ObjectCounter<CountedType>::count;
      }
  public:
      // return number of existing objects:
      static size_t live() {
          return ObjectCounter<CountedType>::count;
      }
};

// initialize counter with zero
template <typename CountedType>
size_t ObjectCounter<CountedType>::count = 0;

template <typename CharT>
class MyString : public ObjectCounter<MyString<CharT> > {
};

int main() {
    MyString<char> s1, s2;
    MyString<wchar_t> ws;
    printf("number of MyString<char>: %d\n", MyString<char>::live());
    printf("number of MyString<wchar_t>: %d\n",ws.live());
    return 0;
}

那么这么做在什么情况下适当呢？我们来看几种它的应用。

TOP不需要虚拟函数的代码再利用

如果想改变某个类成员函数的行为，一般都是将该函数定义为虚函数，在派生类中重载使用。而利用CRTP，我们可以不需要这个虚函数。比如下面的例子。

template<class T> class X {
    public:
        static size_t getSize() { return sizeof(T); }
};

class A : public X <A> {
    int x;
};

int main() {
    cout << "sizeof(A) = " << A::getSize() << endl;
}

这里，class A 自体对象生成之前，利用X<A>，X的实例已经被模板化。在X<A>里面，因为A本身还没有生成，sizeof不是不能使用吗？其实，对于类模板来说，只要没有显示的实例化，或者特化（specialization），类自身的成员函数、静态变量不会被实例化。

从上面的代码看，X<A>实例化的时候，静态的成员函数 getSize() 没有被实例化，所以不需要 class A 之前声明(像是class A; 的前置声明)。而第一次使用 getSize() 的时候是在 main 函数中，而此时 getSize() 已经被实例化了（main 函数到达之前）。

如果你在比较早的编译器上（比如g++ 2.95.3）实验这些代码，结果sizeof(A) = 8，而在 g++ 3.2 或者 VC++6.0 上，sizeof(A) = 4。

以下是一个实际的例子，用来实现内存池。

#include <new>
template<class T, int N>
class MemPool {
private:
    static T buffer[N];
    static int usedNum;

public:
    static void* operator new( size_t size ) {
        if (size == sizeof(T)) {
        if (usedNum < N) {
            return &buffer[usedNum++];
        } else {
            throw std::bad_alloc();
        }
        } else {
            return ::operator new(size);
        }
    }

    static void operator delete( void* ptr ) {
    }

    static void release() {
        usedNum = 0;
    }
};

template<class T, int N> T MemPool<T,N>::buffer[N];
template<class T, int N> size_t MemPool<T,N>::usedNum = 0;

class Foo : public MemPool<Foo, 100> {
    // ....
};

int main()
{
    Foo* foo = new Foo; // 调用MemPool的operator new
    delete foo;         // 调用MemPool的operator delete
    // ……
    Foo::release();
}

TOP利用Template Method实现代码自动化

例如以下的代码：

class C{
public:
  C operator+(C const &rhs) const
  {
    // ...
  }

  C &operator+=(C const &rhs)
  {
    // ...
    return *this;
  }
};

C C::operator+(C const &rhs) const
{
  C tmp(*this);
  tmp += rhs;   // 委托operator+=
  return tmp;
}

利用CRTP的技术，实现其自动化的版本。

template<class T>
struct addable{
  T operator+(T const &rhs) const
  {
    T tmp(static_cast<T const &>(*this));
    tmp += rhs;
    return tmp;
  }
};

// 利用CRTP实现派生类
class C : public addable<C>
{
public:
  C &operator+=(C const &rhs){
    // 实现
    return *this;
  }
};

我们只用一行代码从addable模板类继承，就实现了 C 类中的 operator+ 。当然，在 C 类中必须实现 operator+= 。用户实现的不同 operator+= 方法，基于基类的 operator+ 方法自动的表征出来。如果在 addable 部分中提供一些基础类库，用户可以像定义 class C 一样的方式方便，高效地使用这些类库。

在boost中，像这样使用CRTP的例子很多。boost::operators, boost::iterator_facade, boost::iterator_adaptor等就是。

TOP静态的多态性

理解CRTP的静态多态性，可以看以下的例子：

#include <iostream>

template<class T>
class base{
public:
  void method(){ as_derived().method(); }

protected:
  T &as_derived(){ return static_cast<T&>(*this); }
  T const &as_derived() const{ return static_cast<T const &>(*this); }
};

class A : public base<A>{
public:
  void method(){ std::cout << "This is A::method()" << std::endl; }
};

class B : public base<B>{
public:
  void method(){ std::cout << "This is B::method()" << std::endl; }
};

template<class T>
void some_process(base<T> &r)
{
  r.method();
}

int main(int argc, char *argv[])
{
  A a;
  some_process(a);

  B b;
  some_process(b);

  return 0;
}

在上面的代码中，some_process 函数根据利用参数r实现的多态。也许看到这里你也许会说，r的多态与利用CRTP实现类base, A, B的没有本质的关系，如果要让 some_process 函数静态的多态，标准的模板就能做到，比如：

class A{
public:
  void method(){ std::cout << "This is A::method()" << std::endl; }
};

class B{
public:
  void method(){ std::cout << "This is B::method()" << std::endl; }
}

template<class T>
void some_process(T &r)
{
  r.method();
}

没有错，但是存在必有它的道理。

template<class T> void some_process(T &r);
{
  r.method();
}

template<class T> void some_process(base<T> &r);
{
  r.method();
}

先看看来这两种定义有什么区别，1行是针对所有类型T，而第6行的方法是base<T>或者其派生类型的定义。那么针对所有类型T一定会有 method() 方法吗？如果我们针对int类型实例化 some_process。那么编译器一定出现一大堆莫名其妙的错误信息。面对编译器的错误信息，会让你白天摸不着头脑。

再来看看CRTP的实现。应为只针对了base<T>或者其派生类型，那么当其成员中没有 method() 方法时，编译器能给出很清楚的错误信息。用户可以很快的找到原因并解决。

所以说，这是使用CRTP的原因之一：编译期检测概念不匹配

boost::concept_check中就是使用了这个方法。

另外，针对CRTP的实现方法，我们可以重载 some_process 方法，譬如：

1
2
3

template<class T> void some_process(dog<T> &r);

template<class T> void some_process(cat<T> &r);

当然，我们也可以特化一般的函数模板，但是每种类型都必须这样做，使用模板还有什么意义。

这是使用CRTP的原因之二：限制通用函数名称的导入

TOPParameterized Virtuality

可以利用模板来确定一个类的是否使用虚函数。

class NotVirtual {
};
class Virtual {
public:
    virtual void foo() {
    }
};

template <typename VBase>
class Base : private VBase {
public:
    void foo() {
        printf("Base::foo()\n");
    }
};

template <typename V>
class Derived : public Base<V> {
public:
    void foo() {
        printf("Derived::foo()\n");
    }
};

int main()
{
    Base<NotVirtual>* p1 = new Derived<NotVirtual>;
    p1->foo();  // calls Base::foo()

    Base<Virtual>* p2 = new Derived<Virtual>;
    p2->foo();  // calls Derived::foo()
    return 0;
}

TOPExpression Templates

在一般的编程语言中，往往是分布计算一个表达式，最后将结构合并。比如 a*b+c/d ，首先计算 a*b 和 c/d，让后将结果相加。但是，为了优化算法，常常将整个表达式作为一个整体来处理。C++模板中就是利用了Expression Templates来实现该技巧。

具体实现就是重载算术符，例如 a*b+c/d 就想 add< mul< var<T>,var<T> >, div< var<T>,var<T> > > 一样在以模板参数的方式实现了表达式的构造。

例如以下的代码：

template <typename Left, typename Op, typename Right>
struct LOR {
    Left fod;
    Right rod;

    LOR(Left p, Right r): fod(p), rod(r) {}
    double operator[](int i) {
        return Op::apply(fod[i], rod[i]);
    }
};

template <typename T>
class Vtr {
 private:
     int length;
     T   * vr;
 public:
     Vtr(int n, T * d) { length =n; vr = d; }

     template <typename Left, typename Op, typename Right>
     void operator=(LOR<Left, Op, Right > exprn) {
         for (int i=0; i<length; i++) vr[i] = exprn[i];
     };
     T operator[](int i) const {return vr[i];}
};

struct Multiply {
    static double apply(double a, double b) {return a*b;}
};

struct Addition {
    static double apply(double a, double b) {return a+b;}
};

typedef Vtr<double> Vtr_Double;

template <typename Left>
LOR<Left, Multiply, Vtr_Double>
operator*(Left a, Vtr_Double b) {
    return LOR<Left, Multiply, Vtr_Double >(a,b);
};

template <typename Left>
LOR<Left, Addition, Vtr_Double>
operator+(Left a, Vtr_Double b) {
    return LOR<Left, Addition, Vtr_Double >(a,b);
};
int main(void)
{
    double a[]={1,2,3,4,5};
    double b[]={1,2,3,4,5};
    double c[]={1,2,3,4,5};
    double d[]={1,2,3,4,5};
    double e[]={1,2,3,4,5};
    Vtr_Double X(5,a), Y(5, b), Z(5,c), W(5, d), Q(5, e);
    W = X*Y*Z;
    Q = X+Y+Z;
    return 0;
}

比如「＋」的情况下：

Vtr_Double A, B, C, D;

D = A + B + C;

= LOR<Vtr_Double, Addition,Vtr_Double>() + C;

= LOR<LOR<Vtr_Double, Addition,Vtr_Double>, Addition,Vtr_Double>();

由此可见，为了中间结果而产生的对象构造，保存，备份等处理被回避，整体处理速度得到提升。但是，这样的模板技巧语法晦涩，理解起来比较困难。另外很依赖类型的特化，最终代码尺寸会增大。

TOPType Classification

利用Type Classification，我们可以很方便的知道模板的参数类型。

if (TypeT<T>::IsPtrT) {

} else if (TypeT<T>::IsClassT) {

}

以下是一个例子：

struct One {} ;
struct Two { One a[2]; };
template<typename T> static One testFunction(...);
template<typename T> static Two testFunction(T (*)[1] );
template<typename T> static One testClass(...);
template<typename T> static Two testClass(char T::*);

template<typename T,typename C = T>
class IsFunctionT {
public:
    enum { Yes = sizeof(testFunction<T>(0)) == sizeof(One)
        &&  sizeof(testClass<T>(0)) == sizeof(One)  };
    enum { No = !Yes };
};

template<typename T>
class IsFunctionT<T&> {
public:
    enum { Yes = 0 };
    enum { No = !Yes };
};

template<>
class IsFunctionT<void> {
public:
    enum { Yes = 0 };
    enum { No = !Yes };
};

template<>
class IsFunctionT<void const> {
public:
    enum { Yes = 0 };
    enum { No = !Yes };
};

template<typename T>
void checkT(T* t) {
    if (IsFunctionT<T>::Yes) {
        printf("--------------IsFunction\n");
    }
    else {
        printf("--------------IsNotFunction\n");
    }
}

int foo(int,int) {
    return 0;
}

typedef int (*FUNC)(int,int);
typedef void (*FUNC2)();

template<typename T,typename C>
void checkT(T C::* t) {
    if (IsFunctionT<T>::Yes) {
        printf("--------------IsFunction\n");
    }
    else {
        printf("--------------IsNotFunction\n");
    }
}

struct B {
    char a;
};
typedef void (B::* ClassFunc)(int,int);
typedef char (B::* ClassCharMember);

int main() {
    FUNC p = foo;
    FUNC2 p2 = NULL;
    ClassFunc p3 = NULL;
    ClassCharMember p4 = &B::a;
    int* a = 0;
    B* b = 0;
    checkT(p);
    checkT(a);
    checkT(p2);
    checkT(b);
    checkT(p3);
    checkT(p4);
    checkT(foo);
    return 0;
}

TOPFunction Objects and Callbacks

STL中，根据function object的功能，可以分三类：Arithmetic、Rational、Logical。

Arithmetic的例子：

//  具有一个参数的基类
template <class _Arg, class _Result>
struct unary_function {
    typedef _Arg argument_type;
    typedef _Result result_type;
};

//  具有二个参数的基类
template <class _Arg1, class _Arg2, class _Result>
struct binary_function {
    typedef _Arg1 first_argument_type;
    typedef _Arg2 second_argument_type;
    typedef _Result result_type;
};

// 一个参数时的函数对象
template <class _Tp>
struct plus : public binary_function<_Tp,_Tp,_Tp> {
    _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x + __y; }
};

template <class _Tp>
struct minus : public binary_function<_Tp,_Tp,_Tp> {
    _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x - __y; }
};

template <class _Tp>
struct multiplies : public binary_function<_Tp,_Tp,_Tp> {
    _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x * __y; }
};

template <class _Tp>
struct divides : public binary_function<_Tp,_Tp,_Tp> {
    _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x / __y; }
};

template <class _Tp> inline _Tp identity_element(plus<_Tp>) {
    return _Tp(0);
}

template <class _Tp> inline _Tp identity_element(multiplies<_Tp>) {
    return _Tp(1);
}

template <class Iter, class T>
void   arithmetic(Iter first, Iter last, T value, typename plus<T> functorobj) {
    while(first < last) {
        *first = functorobj(*first,value);
        first++;
    }
}

int  main() {
  int array[4] = { 0, 3, 6, 9 };
  arithmetic(array, array+4, 100, plus<int>());
  return 0;
}

TOPTemplate metaprogramming

这是一个大东东，慢慢来，先看一个例子，也是最经典的：

#include <iostream>

using namespace std;

template<int N>
struct Factorial
{
    enum {V = N * Factorial<N-1>::V};
};

template<>
struct Factorial<1>
{
    enum {V = 1};
};

int main(int argc, char* argv[])
{
    cout << Factorial<12>::V;
    return 0;
}

1. 参考《C++ Templates - The Complete Guide》, 《Modern C++ Design》

EMACS & 程序 编程点滴...

Quick Links

泛型编程

TOP泛型编程