老所工作室

模板 Template 是 C++ 的高级特性，STL 和 Boost 库大量运用模板，使用泛型算法。同时，Boost 库也对模板运用提供了库支持，比如最基本的 boost.mpl 以及最新的 boost.fusion 等库。很多这样的模板库提供的方法都在编译期就计算好了，和我们平时使用的函数不大一样。这些函数常被叫做元函数，基于这样的库的编程常被叫做元编程（metaprogramming）。在《C++ Template Metaprogramming》这本书的第二章的前半部分，作者通过一个实际的例子向我们介绍了元编程的概念，以及如何在编译期使用 boost 的库来对类型进行计算和判断。

…

…

这里，我将这个例子整个摘取出来，使其一目了然，这样我们就可以更好地体会编译器元编程的作用。在继续阅读之前，最好您有以下知识：

• 了解 C++ 模板的概念和语法；
• 了解模板的特例化（Specialization）与偏特例化（Partial Specialization）的作用；
• 了解迭代器 iterator 的概念；

首先，这个例子的目的是一个叫做 iter_swap 的函数，要求输入两个迭代对象，将他们的 dereference 对象的值互换（关于dereference，我就不翻译了，直接用英文比用怪异的中文来的舒服，关于这个单词的翻译，可以参见这个帖子）。

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

这里首先要注意的是，两个输入的迭代对象是不同类型的，也就是说可能第 i1 为 char* 而 i2 为 long*。然而显然，这段代码是无法编译通过的，因为 T 没有定义。首先我们很容易想到，每个 ForwardIterator 类型里面可以内嵌一个类型，表示该 Iterator 所指的对象的类型：

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

显然，这个设计很不好，因为我们都知道，指针类型也是一种 iterator，但指针类型可没有内嵌的 value_type 类型。解决这个问题的方法是 iterator_traits 与模板的偏特化运用。

template <class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)
{
    typename std::iterator_traits<ForwardIterator1>::value_type tmp = *i1;
    *i1 = *i2;
    *i2 = tmp;
}

iterator_traits 是 STL 里提供的一套 traits ，并且对各种类型都进行了适当的偏特化，比如指针类型等。对于指针类型， STL 里会提供类似这样的偏特化：

template <class T>
struct iterator_traits<T*>
{
    typedef T value_type;
    .....
};

对于普通内嵌类型的 iterator ，STL 里则会有如下这样的特化：

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

这样，无论是指针还是 iterator 对象，我们的 tmp 都会有正确的类型了。

目前为止，一切顺利。现在，让我们考虑一下效率，可以很清楚的看到，iter_swap 实现算法里使用了一个临时变量，而这个变量的触发了一次拷贝构造函数，这个过程将会涉及到一系列的内存分配和拷贝，效率很低。设想，如果我们的输入的是类似 std::list<std::vector<std::string> > 这样的容器的迭代器，那么 tmp 对象的类型就是 std::vector< std::string >，那么一个临时对象的创建将会有 n 个字符串对象的创建和拷贝。

最好是根据不同的容器，对该函数进行特化，创造出适合各种容器的效率最高的 iter_wrap 版本，当然，这个工作量是巨大的，不过不用担心，STL 库已经为我们提供了这样一个方法： swap。并且，根据文档中所说：

Because this function template is used as a primitive operation by many other algorithms, it is highly recommended that large data types overload their own specialization of this function. Notably, all STL containers define such specializations (at least for the standard allocator), in such a way that instead of swapping their entire data content, only the values of a few internal pointers are swapped, making this operation to operate in real constant time with them.

所以，我们可以不再担心该函数的效率问题。不过，有了这个 swap 为什么还需要我们的 iter_swap 呢，其一：我们接受的是迭代器对象作为输入，而 std::swap 接受的是对象的引用；其二，iter_swap 交换的两个对象可以是不同类型的，而 std::swap 必须是同一类型之间的交换。我们看看其定义：

template <class T> void swap ( T& a, T& b );

只有一个 T，所以当两个输入是同一类型的时候，我们可以直接调用 std::swap 来完成我们的工作，如果不是同一类型，就继续使用我们目前这个效率低下但却通用的算法：

// Generalized (slow) version
template <class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)
{
    typename std::iterator_traits<ForwardIterator1>::value_type tmp = *i1;
    *i1 = *i2;
    *i2 = tmp;
}

// A better match when the two iterators are the same type
template <class ForwardIterator>
void iter_swap(ForwardIterator i1, ForwardIterator i2)
{
    std::swap(*i1, *i2); // sometimes faster
}

这种方法，实际上是利用了C++的函数参数重载来实现的。不过，仔细琢磨，还有两个问题。

第一个问题，考虑我们的 iterator1 是 std::vector<std::string> 的迭代器，而 iterator2 是 std::list<std::string> 的迭代器。显然，iterator1和iterator2的类型是不同的，无法匹配到快速swap版本；然而，他们两个的 value_type 却都是 std::string ，这完全适合运用高速版 swap。

第二个问题，考虑到 vector<bool> 这个特例，其 iterator 的 operator * 返回的不是 value_type，而是一个代理引用，也就是说有类似如下的定义：

struct bit_iterator
{
    typedef bool value_type;
    typedef proxy reference;
    .....
    proxy operator*() const;
    ....
};

这主要是因为 vector<bool> 为了考虑到性能，将其特化为使用 bit 来保存 bool，然而，没有类型来表示 bit，所以只能额外的添加一个 proxy 代理对象来代理对这种 bit 的引用。

关于具体的 vector<bool> 的那些琐事，我们可以不用太关注（也可以去google），我们目前需要知道，要使用 std::swap 高速版实现的话，我们必须满足：

• iterator1::value_type 和 iterator2::value_type 相同，即迭代器所指的类型相同；
• 对于 iterator1 和 iterator2，他们经过 operator * 操作后，返回的应该是对 value_type 的引用，而不是什么其他对象，比如 proxy reference；

而这两个条件，可以使用 boost 提供的两个元函数 : is_same 和 is_reference 来判断，而且，这个判断是在编译期的。使用它们的完整代码如下：

#include <boost/type_traits/is_reference.hpp>
#include <boost/type_traits/is_same.hpp>
#include <iterator>     // for iterator_traits
#include <utility>      // for swap
#include <iostream>
#include <list>
#include <vector>

namespace foo
{
    // this template struct should be specialized into true and false
    template <bool use_swap>
    struct iter_swap_impl;

    template <>
    struct iter_swap_impl<true>     // the "fast" one
    {
        // the iterator might be different type
        // but *iterator1 and *iterator2 must be the same type
        template <class ForwardIterator1, class ForwardIterator2>
        static void do_it(ForwardIterator1 i1, ForwardIterator2 i2)
        {
            std::cout << "using the fast one..." << std::endl;
            std::swap(*i1, *i2);
        }
    };

    template <>
    struct iter_swap_impl<false>    // the one that always works
    {
        template <class ForwardIterator1, class ForwardIterator2>
        static void do_it(ForwardIterator1 i1, ForwardIterator2 i2)
        {
            std::cout << "using the one that always works" << std::endl;
            typedef typename std::iterator_traits<ForwardIterator1>::value_type v1;
            typedef typename std::iterator_traits<ForwardIterator2>::value_type v2;
            v1 tmp = *i1;
            *i1 = v1(*i2);
            *i2 = v2(tmp);
        }
    };

    template <class ForwardIterator1, class ForwardIterator2>
    void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)
    {
        typedef std::iterator_traits<ForwardIterator1> traits1;
        typedef typename traits1::value_type v1;
        typedef typename traits1::reference r1;

        typedef std::iterator_traits<ForwardIterator2> traits2;
        typedef typename traits2::value_type v2;
        typedef typename traits2::reference r2;

        bool const use_swap = boost::is_same<v1, v2>::value
            && boost::is_reference<r1>::value
            && boost::is_reference<r2>::value;

        iter_swap_impl<use_swap>::do_it(i1, i2);
    }

}

using namespace std;

int main(int, char**)
{
    cout << endl;

    {
        cout << "int * vs float *" << std::endl;
        int a = 50;
        float b = 88.8f;
        cout << "before:" << endl;
        cout << "a = " << a << endl;
        cout << "b = " << b << endl;
        cout << "--------" << endl;
        foo::iter_swap(&a, &b);
        cout << "--------" << endl;
        cout << "after:" << endl;
        cout << "a = " << a << endl;
        cout << "b = " << b << endl;
    }

    cout << endl;

    {
        cout << "float * vs float *" << endl;
        float a = 23.2;
        float b = 25.1;
        foo::iter_swap(&a, &b);
    }

    std::cout << std::endl;

    {
        cout << "vector<string>::iterator vs list<string>::iterator" << endl;
        vector<string> a(5, "I'm a");
        list<string> b(5, "I'm b");
        foo::iter_swap(a.begin(), b.begin());
        cout << "a = " << (*a.begin()) << endl;
        cout << "b = " << (*b.begin()) << endl;
    }

    std::cout << std::endl;

    {
        cout << "vector<float>::iterator vs vector<double>::iterator" << endl;
        vector<float> a(5, 8.88f);
        vector<double> b(5, 2.22f);
        foo::iter_swap(a.begin(), b.begin());
        cout << "a = " << (*a.begin()) << endl;
        cout << "b = " << (*b.begin()) << endl;
    }

    return 0;
}

这里，use_swap这个布尔值并不是在运行时计算的，而是在编译时就计算好的，所以它必须是const的。运行结果如下：

int * vs float *
before:
a = 50
b = 88.8
--------
using the one that always works
--------
after:
a = 88
b = 50

float * vs float *
using the fast one...

vector<string>::iterator vs list<string>::iterator
using the fast one...
a = I'm b
b = I'm a

vector<float>::iterator vs vector<double>::iterator
using the one that always works
a = 2.22
b = 8.88

在这个例子中，boost::is_same<V1, V2>::value 和 boost::is_reference<R1>::value 就是两个元函数。实际上，标准的原函数的定义应该是：metafunction-name<type-arguments...>::type，和普通函数不同的是，其参数是用尖括号括起来的，而不是圆括号，并且其计算是发生在编译器编译的时候，而不是在程序运行的时候。其次，元函数总是返回一个类型，用 ::type 来获得这个嵌套类型。有的元函数实际上是进行了计算，比如我们这个例子里，返回的 ::type 应该是用来表示一个布尔值的，比如如下定义：

struct true
{
    static bool const value = true;
    ......
};

所以，如果按照标准，使用 is_same 元函数的调用应该是：

bool const result = boost::is_same<T1, T2>::type::value;

但考虑到方便，boost 在这种明显是计算值的元函数结果中除了嵌套一个结果type，也同时嵌套一个 value 值。

当然，这个例子只是一个非常简单的使用元编程的例子，而真实的 boost 库里几乎处处都是这种元编程的影子。

is_reference, is_same, metaprogramming, 元编程