C++ 模板惯用法

晨曦之光 发布于 2012/05/23 11:01
阅读 1K+
收藏 5

原文:C++ 模板惯用法
作者:Breaker <breaker.zy_AT_gmail>


关于 C++ 模板编程的惯用法,note-to-self + keynote + idiom case + cross-reference 式笔记

目录


模板语法^

称谓:函数模板 (function template) vs. 模板函数 (template function),或 类模板 (class template) vs. 模板类 (template class),见 [CPP TEMP] 7.1

两阶段编译 (two-phase lookup)、第一实例化点 (first point of instantiation),见 [CPP LANG] 13.2.5 [CPP TEMP] 2.1.2

实例化 (instantiation) 和特化(又译专门化)(specialization)、生成的特化 (generated specialization) vs. 显式的特化 (explicit specialization),见 [CPP LANG] 13.2.2, C.13.7 [CPP TEMP] 7.2

不完全实例化 (incomplete instantiation),见 [CPP LANG] 13.2.2 [MODERN CPP] 1.8

完全特化 (complete specialization)、部分特化(又译偏特化)(partial specialization),见 [CPP LANG] 13.5 [CPP TEMP] 3.3, 3.4

特化顺序:更特化 (more specialized)、更泛化 (more general)、原始模板 (primary template),见 [CPP LANG] 13.5.1 [CPP TEMP] 7.2

非类型模板参数,见 [CPP LANG] 13.2.3 [CPP TEMP] 4

函数模板和普通函数间的重载,见 [CPP LANG] 13.3.2 [CPP TEMP] 2.4

函数模板的参数推导 (argument deduction),见 [CPP LANG] 13.3.1, C.13.4 [CPP TEMP] 2.2, 11

默认模板参数,见 [CPP LANG] 13.4.1 [CPP TEMP] 3.5

成员模板 (member template),见 [CPP LANG] 13.6.2 [CPP TEMP] 5.3

模板作为模板参数 (template template parameter),见 [CPP LANG] C.13.3 [CPP TEMP] 5.4

typename 限定词 (typename qualifier),见 [CPP LANG] C.13.5 [CPP TEMP] 5.1 [EFFECT CPP] Item 42

template 限定词 (template qualifier),见 [CPP LANG] C.13.6 [CPP TEMP] 5.1

模板代码组织:包含模型 (inclusion model) vs. 分离模型 (separation model) 又称分别编译 (separate compile),见 [CPP LANG] 13.7 [CPP TEMP] 6.1, 6.3

显式实例化 (explicit instantiation),见 [CPP LANG] C.13.10 [CPP TEMP] 6.2

设计思维:运行时多态 (run-time polymorphism) vs. 编译时多态 (compile-time polymorphism) 又称参数化多态 (parametric polymorphism),见 [CPP LANG] 13.6.1 [EFFECT CPP] Item 41 [CPP TEMP] 14

模板惯用法示例^

堆栈上分配^

on-stack allocation 的 std 案例:tr1::array 模板

使用模板方法的不足之处是使用编译时确定的 buffer size,为了能在运行时动态调整 stack 内存分配数量,可借助 VC CRT 的 _alloca, _malloca 函数

示例:一个 printf 式的生成 std::string 的函数

template <size_t BufSize, class CharT>
inline
std::basic_string<CharT> make_string(const CharT* format, ...)
{
    CharT buf[BufSize];
    va_list args;

    va_start(args, format);
    // vsprintf 是函数模板, 其针对 char 特化调用 vsprintf_s, 针对 wchar_t 特化调用 vswprintf_s
    vsprintf(buf, BufSize, format, args);
    va_end(args);

    // 注意: 返回时构造可让 VC 编译优化为只有一次 string ctor 调用, 没有额外 copy
    return std::basic_string<CharT>(buf);
}

编译优化的开关^

bool 模板参数,或整数模板参数 + 阈值,避免重复代码时借助编译优化

示例:一个支持透明色的 32bit blit 函数

template <bool UseMask>
void blit(int* dst, const int* src, int mask, size_t size)
{
    for (size_t i = 0; i < size; i++, dst++, src++) {
        if (!UseMask || *src != mask)
            *dst = *src;
    }
}

推导数组元素个数^

可由参数推导求出数组的元素个数,要求必须是数组名,而非指向数组的指针或 new[] 数组

示例:VC CRT 的 _countof 计算数组的元素个数

// 以 C++ 方式编译时, _countof 的定义如下
template <typename _CountofType, size_t _SizeOfArray>
char (*__countof_helper(UNALIGNED _CountofType (&_Array)[_SizeOfArray]))[_SizeOfArray];
#define _countof(_Array) (sizeof(*__countof_helper(_Array)) + 0)

示例:多数 VC CRT buffer 操作函数都有 Secure Template Overloads 版本

template <size_t size>
errno_t strcpy_s(char (&strDestination)[size], const char *strSource);

推导常数^

示例:掩码常数 Mask<N>::Value

#define _MASK_VAL(x)    (1 << x)
// 用于代替上面的宏
// 实例化超出 [0:31] 范围的 Mask 时, 产生编译警告 warning C4293
template <unsigned int N>
struct Mask {
    enum { Value = (1 << N) };
};

示例:GCD<N, M>::Value 求解最大公约数

// GCD<N, M> 原始模板
template <unsigned int N, unsigned int M>
struct GCD {
    static const unsigned int Value = GCD<M, N % M>::Value;
};

// GCD<N, 0> 特化, 用以终止递归条件
template <unsigned int N>
struct GCD<N, 0> {
    static const unsigned int Value = N;
};

隐式转换的显式函数 implicit_cast^

见 [CPP LANG] 13.3.1 模板函数参数推导

  1. 因为是 return u,而不是 return (T) u,所以是隐式转换
  2. 可推导的参数放到 template 参数列表的最后
  3. 效率:有两次拷贝(参数、返回值),但通常编译优化可将其减小到一次拷贝
template <class T, class U> T implicit_cast(U u) { return u; }

void func(int i)
{
    implicit_cast<double>(i);       // T 显式指定为 double, U 由参数推导得出 int
    implicit_cast<char, double>(i); // i 先转换为 double, 再隐式转换为 char
    implicit_cast<char*>(i);        // 错误: int 不能隐式转换为 char*
}

推导 callable 可调用物^

  1. 基于函数指针类型

    • 可提取 callable 的参数和返回值类型
    • callable 只接受函数指针
    template <class RetT, class ArgT>
    bool calc_and_check_1(RetT (*calc)(ArgT), ArgT arg, bool (*check)(RetT))
    {
        const RetT& ret = calc(arg);
        return check(ret);
    }
    
  2. 基于直接的类型

    • callable 接受函数指针、函数对象、成员函数
    • std 算法使用这种方法

    提取 callable 的参数和返回值类型时,callable 只能是函数对象:

    • 函数对象类:含 typedef 指明参数和返回值类型,std 约定命名为 [first_|second_]argument_type, result_type,可从 binary_function, unary_function 继承
    • 函数指针:用 std::ptr_fun 转换为函数对象
    • 成员函数:用 std::mem_fun, tr1::bind 转换为函数对象
    template <class Calc, class ArgT, class Check>
    bool calc_and_check_2(Calc calc, ArgT arg, Check check)
    {
        const Calc::result_type& ret = calc(arg);
        return check(ret);
    }
    
  3. 使用 tr1::function 或 boost::function

    • 和第 2 种方法类似,但是 callable 的参数和返回值类型是固定的
    • tr1::function 已放入 std 名字空间
    bool calc_and_check_3(std::function<int (double)> calc, double arg, std::function<bool (int)> check)
    {
        const std::function<int (double)>::result_type& ret = calc(arg);
        return check(ret);
    }
    

用成员模板实现继承隐喻^

见 [CPP LANG] 13.6.3.1

对于 Derived 和 Base class,并不隐喻 T<Derived> 和 T<Base> 之间存在内建的继承关系。更一般的:设 TypeA 到 TypeB 有隐式转换,并不隐喻 T<TypeA> 到 T<TypeB> 存在内建的隐式转换

可用成员模板实现 subclass 转换隐喻。通常隐式转换以这些成员函数表现:copy ctor, assign, operator Type,即实现这些成员函数的模板版本

示例:典型的 std::auto_ptr 实现,auto_ptr<Derived> 可拷贝或赋值给 auto_ptr<Base>

template <class Type>
class auto_ptr {
    // 非模板的 copy ctor, assign 无法从下面的模板版生成, 需要显式写出, 否则将使用编译器生成的
    auto_ptr(auto_ptr& right) throw() : ptr_(right.release()) {}

    // 模板的 copy ctor: 当  T2* => Type* 时, 隐喻 auto_ptr<T2> => auto_ptr<Type>
    // assign 和 operator auto_ptr<T2> 的模板版相似从略
    template <class T2>
    auto_ptr(auto_ptr<T2>& right) throw() : ptr_(right.release()) {}

    Type* release() throw() {
        Type* temp = ptr_;
        ptr_ = 0;
        return temp;
    }

private:
    Type*   ptr_;
};

假设模板基类中的成员^

模板会小小的违背继承规则:Derived<T> 不能访问 Base<T> 的成员,除非告诉编译器假设它存在,即推迟检查到第二阶段编译,见 [EFFECT CPP] Item 43 [CPP TEMP] 9.4.2

假设 Base<T> 的成员 member 存在的方法有:

  1. 用 this->member
  2. 用 using Base<T>::member 导入名字
  3. 用 Base<T>::member,副作用是关闭 virtual member 的动态绑定

CRTP 循环模板模式^

见 [CPP TEMP] 16.3 CRTP: Curiously Recurring Template Pattern

示例:使用类专属的 set_new_handler 和 operator new,见 [EFFECT CPP] Item 49

template <class T>
class NewHandlerSupport;    // 含针对类型 T 的 set_new_handler 和 operator new

class Widget : public NewHandlerSupport<Widget> {};

结合使用函数模板和类模板^

  1. 类模板能以函数对象类的形式保存调用环境,并有模板默认参数,但不能推导参数
  2. 函数模板能推导参数,但不能保存环境和有模板默认参数

两者结合后,用来写生成函数对象的工厂函数

std 案例:用于构造谓词的 binder, adapter 和 negater,见 [CPP LANG] 18.4.4

特化的基本目的^

  1. 解决对于特定类型实例化时的语义错误

    示例:数组字符串的比较

    // 原始模板使用值比较
    template <class T>
    bool less(T l, T r)
    {
        return l < r;
    }
    
    // const char* 应该用 strcmp 比较
    template <>
    bool less(const char* l, const char* r)
    {
        return strcmp(l, r) < 0;
    }
    
  2. 为特定类型实例化提供更高效的实现

    示例:交换 STL 容器 string, vector 等

    // 原始模板使用值交换
    template <class T>
    void swap(T& l, T& r)
    {
        T t(l);
        l = r;
        r = t;
    }
    
    // std::string 最好用 swap 成员函数, 以发挥 pimpl 方式实现(假设)的效能
    template <class CharT>
    void swap(std::basic_string<CharT>& l, std::basic_string<CharT>& r)
    {
        l.swap(r);
    }
    
  3. 主要依靠特化工作,反而原始模板的意义为次,traits 通常使用这种方法

    示例:编译时 assert 断言

    // 静态/编译时 assert 断言, 要求 expr 能在编译时求值
    // 如果 expr = false, 产生编译错误 error C2027
    template <bool expr> struct StaticAssert;
    template <> struct StaticAssert<true> {};
    template <size_t size> struct StaticAssertTest {};
    
    #define STATIC_ASSERT(x)    \
        typedef StaticAssertTest<sizeof(StaticAssert<bool(x)>)>     StaticAssertType##__LINE__
    

解决实例化的代码膨胀^

用提取共性的方法解决实例化产生的目标代码膨胀 (code bloat),见 [EFFECT CPP] Item 44

示例:部分特化转接调用完全特化解决代码膨胀,见 [CPP LANG] 13.5

// 原始模板
template <class T>
class Vector;           // 含最一般的 [] 操作

// Vector<void*> 是针对 void* 的完全特化
template <>
class Vector<void*>;    // 含针对 void* 的 [] 操作

// Vector<T*> 是针对任意类型 T 指针的部分特化
template <class T>
class Vector<T*> : private Vector<void*> {
    typedef Vector<void*> Base;

    // 转接调用完全特化 Vector<void*> 的 [] 操作
    T*& operator[](int i) {
        return reinterpret_cast<T*&>(Base::operator[](i));
    }
};

// 部分特化 Vector<T*> 的实例化
// 代码空间开销: 所有的 Vector<T*> 实际共享一个 Vector<void*> 实现
Vector<Shape*>  vps;    // <T*> 是 <Shape*>, T 是 Shape
Vector<int**>   vppi;   // <T*> 是 <int**>, T 是 int*

traits 特征和 policy 策略^

见 [CPP TEMP] 15 [CPP LANG] 13.4 [MODERN CPP] almost all book

traits 和 policy 使用相同的下层技术,只是在设计目的和作用上不同

  1. traits 的作用倾向于:特征提取,特征主要指类型和标识,以含 typedef, enum, static 著称,经常是空类

    traits 的 std 案例:std::iterator_traits,用法举例:根据 iterator 特征选择算法,如只对 random_access_iterator_tag 使用快速排序

  2. policy 的作用倾向于:行为组合,是编译时 Strategy 模式,以含行为正交的 member function 著称,经常多个 policy 组合而用

    policy 的 std 案例:std::allocator,用法举例:实现自己的 small-block allocator 让 STL 容器针对小块内存分配优化

示例:traits 类型标识

Q: 为什么不用 C++ 内建的 RTTI: typeid()
A: 即便 MyTraits<Type> 的 Type 不是多态类型,typeid() 可在编译时求值,但 type_info::operator== 或 type_info::name() + strcmp() 却很难在编译时求值,导致条件分支没法优化掉,见 [EFFECT CPP] Item 47, 48

struct MyTraitsBase {
    enum {
        TYPE_UNKNOWN,
        TYPE_A,
        TYPE_B
    };
};

template <class Type>
struct MyTraits : public MyTraitsBase {
    static const int TYPE_ID = TYPE_UNKNOWN;
};

template <>
struct MyTraits<TypeA> : public MyTraitsBase {
    static const int TYPE_ID = TYPE_A;
};

template <>
struct MyTraits<TypeB> : public MyTraitsBase {
    static const int TYPE_ID = TYPE_B;
};

template <class Type>
void user(const Type& obj)
{
    // 实际中可用表驱动法替代判断语句
    // 开启编译优化后, 这里的条件分支被优化掉
    if (MyTraits<Type>::TYPE_ID == MyTraitsBase::TYPE_A)
        // 针对 TypeA 类型的处理
    else if (MyTraits<Type>::TYPE_ID == MyTraitsBase::TYPE_B)
        // 针对 TypeB 类型的处理
    else if (MyTraits<Type>::TYPE_ID == MyTraitsBase::TYPE_UNKNOWN)
        //  针对一般类型的处理
}

参考书籍^

  • [CPP LANG] "C++ Programming Language, Special Ed" Ch13 Templates, Appendix C.13 Templates
  • [CPP TEMP] "C++ Templates: The Complete Guide", 2002
  • [EFFECT CPP] "Effective C++, 3Ed"
  • [MODERN CPP] "Modern C++ Design", 2001

原文链接:http://blog.csdn.net/breakerzy/article/details/7426458
加载中
返回顶部
顶部