模板

模板特化

下面是求最大公因数的算法模板

template <typename T>
T gcd(T a, T b)
{
    while(b != T(0)){
        T t = a % b;
        a = b;
        b = t;
    }
    return a;
}

要求是：

  • 可以通过常量 0 来构造
  • 可以拷贝（构造和赋值）
  • 可以作不等于的比较
  • 可以进行取余数的操作

标准的 int、long、long long 等类型及其对应的无符号类型，以上代码都能正常工作，并能得到正确的结果。

这里有一个自建类型

class m_number{
public:
    m_number() noexcept{}
    m_number(size_t _val) noexcept:val(_val){}
    m_number(const m_number& m){val = m.val;}

    bool operator==(const m_number& m) noexcept
    {
        return val == m.val;
    }

    bool operator!=(const m_number& m) noexcept
    {
        return !(*this==m);
    }

    m_number& operator=(const m_number& m) noexcept
    {   
        val = m.val;
        return *this;
    }

    size_t operator*() const noexcept
    {
        return val;
    }

private:
    size_t val{0};

};

直接调用gcd(m_number(18), m_number(24);会报错：

error: no match for 'operator%' (operand types are 'm_number' and 'm_number') T t = a % b;

1、添加 operator% 的实现在m_number内部：

m_number& operator%(const m_number& m) noexcept
{   
    val %= m.val;
    return *this;
}

2、添加 operator% 的实现在外部：

m_number operator%(const m_number& m, const m_number& n)
{
    return {*m % *n};
}

3、将gcd的a%b改为m_mod(a,b)，并进行重载：

template <typename T>
T m_mod(const T& a, const T& b)
{
    return a % b;
}

m_number m_mod(const m_number& a, const m_number& b)
{
    return {*a % *b};
}

template <typename T>
T gcd(T a, T b)
{
    while(b != T(0)){
        T t = m_mod(a, b);
        a = b;
        b = t;
    }
    return a;
}

4、重载改为特化：

template <>
m_number m_mod<m_number>(const m_number& a, const m_number& b)
{
    return {*a % *b};
}

特化和重载在行为上没有本质的区别。就一般而言，特化是一种更通用的技巧，最主要的原因是特化可以用在类模板和函数模板上，而重载只能用于函数。

通用而言，Herb Sutter 给出了明确的建议：对函数使用重载，对类模板进行特化。

动态多态和静态多态的对比

面向对象的动态多态，C++ 基于泛型编程的静态多态，两者解决的实际上是不太一样的问题。

动态多态解决的是运行时的行为变化，选择了一个形状后，再在某个地方绘制该形状，这是无法在编译时确定的。

静态多态或者泛型，让适用于不同类型的同构算法可以用同一套代码来实现，实际上强调的是对代码的复用。

以排序为例，C++ 里的标准 sort 算法（以两参数的重载为例）只要求：

  • 参数满足随机访问迭代器的要求。
  • 迭代器指向的对象之间可以使用 < 来比较大小，满足严格弱序关系。
  • 迭代器指向的对象可以被移动。

它的性能超出 C 的 qsort，因为编译器可以内联（inline、可以看作C里面的宏定义）对象的比较操作；而在 C 里面比较只能通过一个额外的函数调用来实现。C 的 qsort 函数要求数组指向的内容是可按比特复制的，C++ 的 sort 则要求迭代器指向的内容是可移动的，可适用于更广的情况。

C++ 里目前有大量的泛型算法：

  • sort：排序
  • reverse：反转
  • count：计数
  • find：查找
  • max：最大值
  • min：最小值min
  • max：最小值和最大值
  • next_permutation：下一个排列
  • gcd：最大公约数
  • lcm：最小公倍数

编译期计算

C++ 模板是图灵完全的，使用 C++ 模板，你可以在编译期间模拟一个完整的图灵机，可以完成任何的计算任务。

// 先定义，再特化
template <int n>
struct factorial
{
    
    static const int value = n * factorial<n - 1>::value;
};

template <>
struct factorial<0> 
{
    static const int value = 1;
};

int main()
{   
    cout << factorial<-1>::value<< endl;
    return 0;
}

x86-64 下的编译结果：


.LC0:
        .string "%d\n"
main:
        push    rbp
        mov     rbp, rsp
        mov     esi, 3628800
        mov     edi, OFFSET FLAT:.LC0
        mov     eax, 0
        call    printf
        mov     eax, 0
        pop     rbp
        ret

传递一个负数给 factorial 应该是编译期间的递归溢出。

fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)

通用的解决方案是使用 static_assert，确保参数永远不会是负数。

template <int n>
struct factorial
{
    static_assert(n >= 0, "require non-negativ number!");
    static const int value = n * factorial<n - 1>::value;
};

要进行编译期编程，最主要的一点，是需要把计算转变成类型推导。

条件语句：提供了两个特化。真的情况，定义结果 type 为 Then 分支；假的情况，定义结果 type 为 Else 分支。

template <bool _flag, typename Then, typename Else>
struct If;

template <typename Then, typename Else>
struct If<true, Then, Else>
{
    typedef Then type;	
};

template <typename Then, typename Else>
struct If<false, Then, Else>
{
    typedef Else type;
};

int f(int i)
{
    if (i & 1) return 0;
    else return 1;
}

// m_integral_constant 模板同时包含了整数的类型和数值。
template <typename T, T v>
struct m_integral_constant {
    static const T value = v;
    typedef T value_type;
    typedef m_integral_constant type;
};

template <int i>
struct F {
    typedef typename If<i & 1, m_integral_constant<int, 0>, m_integral_constant<int, 1>>::type type;
};

int main() 
{
    cout << f(1) << endl;               // 1
    cout << F<1>::type::value << endl;  // 1
    return 0;
}

循环语句：WhileLoop有两个模板参数，同样用特化来决定走递归分支还是退出循环分支。While 模板则只需要循环体一个参数，方便使用。

用 :: 取一个成员类型、并且 :: 左边有模板参数的话，得额外加上 typename 关键字来标明结果是一个类型。上面循环模板的定义里就出现了多次这样的语法。MSVC 在这方面往往比较宽松，不写 typename 也不会报错，但这是不符合 C++ 标准的用法。

下面为如何使用循环模板来完成从 1 加到 n 的计算：

template <bool condition, typename Body>
struct WhileLoop;

template <typename Body>
struct WhileLoop<true, Body> 
{
    typedef typename WhileLoop<Body::cond_value, typename Body::next_type>::type type;
};

template <typename Body>
struct WhileLoop<false, Body> 
{
    typedef typename Body::res_type type;
};

template <typename Body>
struct While 
{
    typedef typename WhileLoop<Body::cond_value, Body>::type type;
};

template <class T, T v>
struct m_integral_constant {
    static const T value = v;
    typedef T value_type;
    typedef m_integral_constant type;
};

template <int result, int n>
struct SumLoop {
    // 代表循环的条件（真或假）
    static const bool cond_value = n != 0;
    static const int res_value = result;
    // 退出循环时的状态
    typedef m_integral_constant<int, res_value> res_type;
    // 下面循环执行一次时的状态
    typedef SumLoop<result + n, n - 1> next_type;
};

template <int n>
struct Sum {
    typedef SumLoop<0, n> type;
};

int main()
{
    cout << While<Sum<10>::type>::type::value << endl; //55
    return 0;
}

编译期类型推导

C++ 标准库在<type_traits>里定义了很多工具类模板，用来提取某个类型（type）在某方面的特点（trait）

针对布尔值有两个额外的类型定义：

typedef std::integral_constant<bool, true> true_type;
typedef std::integral_constant<bool, false> false_type;

true_type 和 false_type 经常可以在函数重载中见到。

template <typename T>
class SomeContainer {
public:
  static void destroy(T* ptr)
  {
    _destroy(ptr, is_trivially_destructible<>());
  }

private:
  static void _destroy(T* ptr, true_type){}
  
  static void _destroy(T* ptr, false_type){ptr->~T();}
};

很多容器类里会有一个 destroy 函数，通过指针来析构某个对象。为了确保最大程度的优化，常用的一个技巧就是用 is_trivially_destructible 模板来判断类是否是可平凡析构的，即不调用析构函数，不会造成任何资源泄漏问题。模板返回的结果还是一个类（ true_type或false_type）。要得到布尔值使用 is_trivially_destructible::value 就可以，但此处需要的是使用 () 调用该类型的构造函数，让编译器根据数值类型来选择合适的重载。在优化编译的情况下，编译器可以把不需要的析构操作彻底全部删除。

类似的还有：

  • is_array
  • is_enum
  • is_function
  • is_pointer
  • is_reference
  • is_const
  • has_virtual_destructor

一个常见的模板 remove_const 的定义如下：（用来去除类型里的 const 修饰）

template <class T>
struct remove_const 
{
	typedef T type;
};

template <class T>
struct remove_const<const T> 
{
	typedef T type;
};

利用模板的特化，针对 const 类型去掉相应的修饰。

对 const string& 应用 remove_const，就会得到 string&，即remove_const::type 等价于 string&。

如果对 const char* 应用 remove_const 的话，结果还是 const char*。原因是const char* 是指向 const char 的指针，而不是指向 char 的 const 指针。如果对 char * const 应用 remove_const 的话，可以得到 char* 。

is_trivially_destructible::value 和 remove_const::type 非常啰嗦，C++ 标准里，前者有增加 _v 的编译时常量，后者有增加 _t 的类型别名。

template <class T>
inline constexpr bool is_trivially_destructible_v = is_trivially_destructible<T>::value;
template <class T>
using remove_const_t = typename remove_const<T>::type;

通用 fmap 函数模板

// default return container : vector
template <template <typename, typename>class OutContainer =  std::vector, typename F, class R>
auto fmap(F&& fun, R&& input)
{
     // decltype 来获得用 f 来调用 inputs 元素的类型
     // decay_t 来把获得的类型变成一个普通的值类型
    typedef std::decay_t<decltype(fun(*input.begin()))> res_type;

    OutContainer<res_type, allocator<res_type>> res;

    // 存放结果的容器需要支持 push_back 成员函数
    // 这里是转发引用
    for (auto&& item : input) {
        res.push_back(fun(item));
    }
    return res;
}

int main()
{
    vector<int> v{1,3,5};
    auto res = fmap([](int a) {return 2 * a; }, v);
    m_print_single(res); // 2 6 10
    return 0;
}

SFINAE

替换失败非错（substitution failure is not an error），英文简称为 SFINAE。

当一个函数名称和某个函数模板名称匹配时，重载决议过程大致如下：

  • 根据名称找出所有适用的函数和函数模板对于适用的函数模板，要根据实际情况对模板形参进行替换
  • 替换过程中如果发生错误，这个模板会被丢弃
  • 在上面两步生成的可行函数集合中，编译器会寻找一个最佳匹配，产生对该函数的调用
  • 如果没有找到最佳匹配，或者找到多个匹配程度相当的函数，则编译器需要报错
 struct Obj
 {
     typedef int obj_type;
 };

 template <typename T>
 void f(typename T::obj_type)
 {
     cout << "typename T::obj_type" << endl;
 }

 template <typename T>
 void f(T)
 {
     cout << "T" << endl;
 }

int main()
{
    f<Obj>(0);  // typename T::obj_type
    f<int>(0);  // T
    return 0;
}

对于f<Obj>(0);，有两个模板符合名字 f，替换结果为 f(Obj::obj_type) 和 f(Obj)，只有f(Obj::obj_type) 可以匹配参数0。

对于f<int>(0);，有两个模板符合名字 f，替换结果为 f(int::obj_type) 和 f(int)，int::obj_type不是正确的类型，只有f(int)可以匹配参数0。

SFINAE 设计的最初用法：如果模板实例化中发生了失败，没有理由编译就此出错终止，因为还是可能有其他可用的函数重载的。这儿的失败仅指函数模板的原型声明，即参数和返回值。

函数体内的失败不考虑在内。如果重载决议选择了某个函数模板，而函数体在实例化的过程中出错，那我们仍然会得到一个编译错误。

编译期成员检测

SFINAE可以根据某个实例化的成功或失败来在编译期检测类的特性。

 template <typename T>
 struct has_reserve {
     // 定义了两个结构 good 和 bad，其大小必须不一样。
     struct good { char _c; };
     struct bad { char _c[2]; };

     // 定义了一个 SFINAE 模板，内容不重要。
     // 模板的第二个参数需要是第一个参数的成员函数指针，并且参数类型是 size_t，返回值是 void。
     template <class V, void (V::*)(size_t)>
     struct SFINAE {};

     // 定义了一个要求 SFINAE* 类型的 reserve 成员函数模板，返回值是 good。
     template <class V>
     static good reserve(SFINAE<V, &V::reserve>*);

     // 定义了一个对参数类型无要求的 reserve 成员函数模板，返回值是 bad。
     template <class V>
     static bad reserve(...);

     // 定义常整型布尔值 value，结果是 true 还是 false,  取决于 nullptr 能不能和 SFINAE* 匹配成功。
     // 这又取决于模板参数 T 有没有返回类型是 void、接受一个参数并且类型为 size_t 的成员函数 reserve。
     static const bool value = sizeof(reserve<T>(nullptr)) == sizeof(good);     
 };

int main()
{
    cout << has_reserve<vector<int>>::value << endl;    // 1
    cout << has_reserve<Obj>::value << endl;            // 0
    return 0;
}

C++11 开始，标准库有了一个 enable_if 的模板（定义在<type_traits>），可用它来选择性地启用某函数重载。

设我们有一个函数，用来往一个容器尾部追加元素。容器有没有 reserve 成员函数，是对性能有影响的。

如果有的话，我们通常应该预留好内存空间，以免产生不必要的对象移动甚至拷贝操作。

template <typename C, typename T>
enable_if_t<has_reserve<C>::value, void>
append(C& container, T* ptr, size_t size)
{
    container.reserve(container.size() + size);
    for (size_t i = 0; i < size; ++i) {
    	container.push_back(ptr[i]);
    }
}

template <typename C, typename T>
enable_if_t<!has_reserve<C>::value,void>
append(C& container, T* ptr, size_t size)
{
	for (size_t i = 0; i < size;  ++i) {
        container.push_back(ptr[i]); 
    }
}

对于某个 type trait，添加 _t 的后缀等价于其 type 成员类型。因此可以用 enable_if_t 来取到结果的类型。enable_if_t<has_reserve<C>::value, void> 指如果类型 C 有 reserve 成员的话，那启用下面的成员函数，返回类型为 void。

decltype 返回值

如果只需要在某个操作有效的情况下启用某个函数，而不需要考虑相反的情况的话，有另外一个技巧可以用。

如果我们想限制只有具有 reserve 成员函数的类可以使用这个重载，可以把代码简化成：

template <typename C, typename T>
auto append(C& container, T* ptr, size_t size)->decltype(declval<C&>().reserve(1U), void()    
{
    container.reserve(container.size() + size);
    for (size_t i = 0; i < size; ++i) {
        container.push_back(ptr[i]);
    }
}

declval 这个模板用来声明一个某个类型的参数，但这个参数只是用来参加模板的匹配，不允许实际使用。使用这个模板，我们可以在某类型没有默认构造函数的情况下，假想出一个该类的对象来进行类型推导。

declval<C&>().reserve(1U)用来测试 C& 类型的对象是不是可以拿 1U 作为参数来调用 reserve 成员函数。

C++ 里的逗号表达式的意思是按顺序逐个估值，并返回最后一项。上面这个函数的返回值类型是 void。

void_t

void_t 是 C++17 新引入的一个模板，定义如下：

template <typename...>
using void_t = void;

这个类型模板会把任意类型映射到 void。在这个过程中，编译器会检查任意类型的有效性。

利用 decltype、declval 和模板特化，可以简化 has_reserve 的定义。

template <typename T, typename = void_t<>>
struct has_reserve : false_type {};
   
template <typename T>
struct has_reserve<T, void_t<decltype(declval<T&>().reserve(1U))>> : true_type {};   

int main()
{
    cout << has_reserve<vector<int>>::value << endl;    // 1
    cout << has_reserve<Obj>::value << endl;            // 0
    return 0;
}

这里第二个 has_reserve 模板的定义实际上是一个偏特化。偏特化是类模板的特有功能，跟函数重载有些相似。编译器会找出所有的可用模板，然后选择其中最特别的一个。

像上面的例子，所有类型都能满足第一个模板，但不是所有的类型都能满足第二个模板，所以第二个更特别。当第二个模板能被满足时，编译器就会选择第二个特化的模板；而只有第二个模板不能被满足时，才会回到第一个模板的通用情况

标签分发

用 true_type 和 false_type 来选择合适的重载，即标签分发（tag dispatch）。

template <typename T>
struct has_reserve {
    // 定义了两个结构 good 和 bad，其大小必须不一样。
    struct good { char _c; };
    struct bad { char _c[2]; };

    // 定义了一个 SFINAE 模板，内容也同样不重要。
    // 模板的第二个参数需要是第一个参数的成员函数指针，并且参数类型是 size_t，返回值是 void。
    template <class V, void (V::*)(size_t)>
    struct SFINAE {};

    // 定义了一个要求 SFINAE* 类型的 reserve 成员函数模板，返回值是 good。
    template <class V>
    static good reserve(SFINAE<V, &V::reserve>*);

    // 定义了一个对参数类型无要求的 reserve 成员函数模板，返回值是 bad。
    template <class V>
    static bad reserve(...);

    // 定义常整型布尔值 value，结果是 true 还是 false,  取决于 nullptr 能不能和 SFINAE* 匹配成功。
    // 而这又取决于模板参数 T 有没有返回类型是 void、接受一个参数并且类型为 size_t 的成员函数 reserve。
    static const bool value = sizeof(reserve<T>(nullptr)) == sizeof(good);     
};

template <typename C, typename T>
void _append(C& container, T* ptr, size_t size, true_type)  
{
    container.reserve(container.size() + size);
    for (size_t i = 0; i < size; ++i) {
        container.push_back(ptr[i]);
    }
}

template <typename C, typename T>
void _append(C& container, T* ptr, size_t size, false_type)
{
    for (size_t i = 0; i < size; ++i) {
        container.push_back(ptr[i]);
    }
}

template <typename C, typename T>
void append(C& container, T* ptr, size_t size) 
{ 
    _append(container, ptr, size, integral_constant<bool, has_reserve::value>{}); 
}

如果用void_t会简单一点

template <typename T, typename = void_t<>>
struct has_reserve : false_type {};

template <typename T>
struct has_reserve<T, void_t<decltype(declval<T&>().

template <typename C, typename T>
void _append(C& container, T* ptr, size_t size, true
   
{
    container.reserve(container.size() + size);
    for (size_t i = 0; i < size; ++i) {
        container.push_back(ptr[i]);
    }
}

template <typename C, typename T>
void _append(C& container, T* ptr, size_t size, fals
{
    for (size_t i = 0; i < size; ++i) {
        container.push_back(ptr[i]);
    }
}

template <typename C, typename T>
void append(C& container, T* ptr, size_t size) 
{ 
    _append(container, ptr, size, has_reserve<C>{});
}

静态多态的限制

下面的代码的问题

template <typename C, typename T>
void append(C& container, T* ptr, size_t size)
{
    if (has_reserve<C>::value) {
        container.reserve(container.size() + size);
    }
    for (size_t i = 0; i < size; ++i) {
        container.push_back(ptr[i]);
    }
}

C 类型没有 reserve 成员函数的情况下，编译是不能通过的，会报错。这是因为 C++ 是静态类型的语言，所有的函数、名字必须在编译时被成功解析、确定。在动态类型的语言里，只要语法没问题，缺成员函数要执行到那一行上才会被发现。这赋予了动态类型语言相当大的灵活性；只不过，不能在编译时检查错误，同样也是很多人对动态类型语言的抱怨所在。

可以用if constexpr代替if实现。因为一般的 if 是运行期条件语句；if constexpr 是编译期条件语句。