目录
【C++】小知识之用模板递归优化代码
WS_TSKY
编辑于 2023年04月04日 03:53
收录于文集
共4篇

C++模板入门

函数模板

C++可以重载函数，即可以定义多个函数名相同但是参数不同的函数，使用时编译器会自动选择。

我们可以定义两个分别计算 float 和 int 类型的相加的函数：

代码块
C++
自动换行
复制代码
int add(int a, int b)
{
    return a + b;
}
float add(float a, float b)
{
    return a + b;
}
int main()
{
    cout << add(1, 2) << "\t" << add(3.5f, 2.1f);
    return 0;
}
复制成功

注意定义的浮点字面量后面没有 f 的话是默认为 double 类型。

问题出现了，如果我们想要其它类型也能使用 add 这个函数呢，或者要两个不同类型（如 int 和 float）相加呢？每增加一个类型就需要写一遍函数，太费程序员键盘了。

我们可以定义一个函数模板来解决这个问题：

代码块
C++
自动换行
复制代码
template <typename T1,typename T2>
auto add(T1 a, T2 b)
{
    return a + b;
}

int main()
{
    cout << add(1, 2.5) << "\t" << add(3.5, 2.1f);
    return 0;
}
复制成功

在函数定义上面一行加上 template 关键字，尖括号里的 typename 表示定义的模板是一种类型，T1 是程序员自己定义的标识符，称为模板参数，代表了一个类型，T2 同理，后面就可以使用这个类型了，T1 a 表示 a 是 T1 类型的，T1 具体是哪个类型是调用这个 add 函数的时候确定的。比如 main 函数里的第一个调用，T1 是 int ，T2 是 double，确定模板参数的过程叫实例化。

学了模板就明白刚入门写的 ”hello world“ 原来也是有学问的，cin 和 cout 用的 >> 和 << 也是模板函数，所以能处理各种类型的数据。

返回值类型是 auto ，这也是由编译器自动推断返回类型，C++14的特性，编译时注意使用C++14以上标准，如 g++ 编译时的命令：

代码块
Shell
自动换行
复制代码
g++ main.cpp -std=c++14
复制成功

除了用模板定义类型，还可以定义数据：

代码块
C++
自动换行
复制代码
template <int N>
void print()
{
    for (int i = 0; i < N; i++)
    {
        cout << i << "\n";
    }
}
int main()
{
    print<100>();
    return 0;
}
复制成功

N 是模板参数，它是一个 int 类型的数，这个函数在调用时编译器就没法推断了，我们需要指定 N 是多少，调用处的函数名后面尖括号填入模板参数 100 ，这个函数实现的是控制台打印 0 - 99 。

模板类

我们定义类的时候可以使用模板，模板类使用得较多，STL 当中定义了丰富的模板类。

我们可以定义一个模板类，可以存储任意类型，只有一个成员函数，就是把存储的数据打印出来：

代码块
C++
自动换行
复制代码
template <typename T>
class AnyType
{
private:
    T data;

public:
    AnyType(T a)
    {
        data = a;
    }
    void print()
    {
        cout << data << "\n";
    }
};
int main()
{
    AnyType<string> a = string("hello");
    a.print();

    AnyType<int> b = 123;
    b.print();
    return 0;
}
复制成功

模板类本身是一个类型，使用时需要把模板参数加上，模板参数也可以是数据，而且类成员函数也可以是模板函数。

特化和偏特化

特化是指定特定的模板参数对应的函数体，有点抽象，请看代码：

代码块
C++
自动换行
复制代码
template <int N>
void print()
{
    for (int i = 0; i < N; i++)
    {
        cout << i << "\n";
    }
}

template <>
void print<999>()
{
    cout << "specialization\n";
}

int main()
{
    print<999>();
    print<100>();
    return 0;
}
复制成功

这段程序会先输出一句 "specialization&#​34;，再打印 0 - 99。

语法就是 template<>，尖括号里不写东西，下一行是是函数定义，函数名后面的尖括号写要特化的模板参数，调用的时候用到这个模板时就会调用你新定义的那个函数。模板类的特化就是类名后面写特化的参数了。

偏特化是只对部分模板参数特化，只有模板类支持，模板函数不支持：

代码块
C++
自动换行
复制代码
template <int A, int B>
class Test
{
public:
    Test()
    {
        for (int i = A; i <= B; i++)
        {
            cout << i << "\n";
        }
    }
};
template <int B>
class Test<99, B>
{
public:
    Test()
    {
        cout << "specialization\n";
    }
};

int main()
{
    Test<1, 6> a;
    Test<99, 114514> b;
    return 0;
}
复制成功

我们用构造函数检验模板参数，这段程序会输出 1 - 6，再打印 "specialization&#​34;。

只要其中一个模板参数符合你偏特化的情况，那无论其它模板参数是什么，都会选择特化的那个定义。

上面只演示了模板参数是数值的情况，模板参数是类型其实也是类似的。

总结

所谓模板，是定义一个模子，填入不同的模板参数会生成不同的函数（类），gcc 和 msvc 等编译器就会针对不同的特化生成不同的汇编代码，所以特化越多，生成的代码体积越大。

上面的知识对C++复杂的模板系统来说只是很小一部分，我自己也太菜了，只能介绍这么多了。

前置芝士先到这里，下面点题。

利用模板进行循环展开

模板递归计算阶乘

以下内容应该不是语言层面的，但 gcc，msvc 等编译器应该适用。

上面提到模板的实例化是由编译器完成的，也就是在编译期所有特化的函数内部汇编，什么意思呢，我们实现一个阶乘计算函数：

代码块
C++
自动换行
复制代码
#include <iostream>
using namespace std;

template <int N>
int factorial()
{
    return N * factorial<N - 1>();
}

template <>
int factorial<0>()
{
    return 1;
}

int main()
{
    cout << factorial<5>();
    return 0;
}
复制成功

在线查看生成的汇编，网址：https://godbolt.org/

它会递归地实例化 factorial<5> 到 factorial<0>，factorial<0> 是特化的返回 1，则到这里就停止了。

用模板递归代替循环

上面的阶乘实际上已经实现了类似循环的效果，利用递归的思想，我们设计一个函数从  0 打印到 N ：

代码块
C++
自动换行
复制代码
template <int N>
void print()
{
    print<N - 1>();
    cout << N << "\n";
}

template <>
void print<0>()
{
    cout << 0 << "\n";
}

int main()
{
    print<100>();
    return 0;
}
复制成功

函数会打印 0-100。

和阶乘类似，改变调用时的模板参数可以改变循环上界，改变模板特化的值可以改变循环下界。

现在的问题是，模板函数递归好像和普通递归一样，但根据生成的汇编来看，只不过生成了很多的函数依次调用，并没有降低函数调用开销（存在push、pop和ret等语句说明在调用函数），也就无法实现优化。但是当我们开-O2及以上优化呢？

开启-O2

我们发现和函数调用有关的语句几乎没有了，这些代码大家都可以自己去测试一下。

运行时改变参数

前面的代码的模板参数都是在编译期定好的，现在要我们从控制台输入一个 n，打印 0 到 n 要如何做到呢？我们可以定义一个选择函数 print_it ，用 switch 或者 if 语句判断：

代码块
JavaScript
自动换行
复制代码
void print_it(int n)
{
    switch (n)
    {
    case 0:
        print<0>();
        break;
    case 1:
        print<1>();
        break;
    case 2:
        print<2>();
        break;
    //...
    default:
        break;
    }
}
复制成功

但是又是个费键盘的活，所以我们让 print_it 使用模板递归：

代码块
JavaScript
自动换行
复制代码
template <int N = 0>
void print_it(int n)
{
    if (n > N)
    {
        print_it<N + 1>(n);
        return;
    }
    print<N>();
}

template <>
void print_it<800>(int n){}

int main()
{
    int n = 0;
    cin >> n;
    print_it(n);
    return 0;
}
复制成功

这里模板参数也用了默认参数 N = 0 ，也就是说不填模板参数时，N 默认为 0，再特化一个上限（因为 gcc 允许的模板递归层数为 900），当然，现在的问题是它似乎又回到了普通的递归，所以建议主体函数（在这里就是 print 函数）体执行时间较长使用这个方法，否则 switch 可能会更快。

编程 算法 C++ 性能 优化 模板编程
cv22287849