极客时间已完结课程限时免费阅读

18 | 应用可变模板和tuple的编译期技巧

18 | 应用可变模板和tuple的编译期技巧-极客时间

18 | 应用可变模板和tuple的编译期技巧

讲述:吴咏炜

时长11:07大小10.16M

你好,我是吴咏炜。
今天我们讲一个特殊的专题,如何使用可变模板和 tuple 来完成一些常见的功能,尤其是编译期计算。

可变模板

可变模板 [1] 是 C++11 引入的一项新功能,使我们可以在模板参数里表达不定个数和类型的参数。从实际的角度,它有两个明显的用途:
用于在通用工具模板中转发参数到另外一个函数
用于在递归的模板中表达通用的情况(另外会有至少一个模板特化来表达边界情况)
我们下面就来分开讨论一下。

转发用法

以标准库里的 make_unique 为例,它的定义差不多是下面这个样子:
template <typename T,
typename... Args>
inline unique_ptr<T>
make_unique(Args&&... args)
{
return unique_ptr<T>(
new T(forward<Args>(args)...));
}
这样,它就可以把传递给自己的全部参数转发到模板参数类的构造函数上去。注意,在这种情况下,我们通常会使用 std::forward,确保参数转发时仍然保持正确的左值或右值引用类型。
稍微解释一下上面三处出现的 ...
typename... Args 声明了一系列的类型——class...typename... 表示后面的标识符代表了一系列的类型。
Args&&... args 声明了一系列的形参 args,其类型是 Args&&
forward<Args>(args)... 会在编译时实际逐项展开 Argsargs ,参数有多少项,展开后就是多少项。
举一个例子,如果我们需要在堆上传递一个 vector<int>,假设我们希望初始构造的大小为 100,每个元素都是 1,那我们可以这样写:
make_unique<vector<int>>(100, 1)
模板实例化之后,会得到相当于下面的代码:
template <>
inline unique_ptr<vector<int>>
make_unique(int&& arg1, int&& arg2)
{
return unique_ptr<vector<int>>(
new vector<int>(
forward<int>(arg1),
forward<int>(arg2)));
}
如前所述,forward<Args>(args)... 为每一项可变模板参数都以同样的形式展开。项数也允许为零,那样,我们在调用构造函数时也同样没有任何参数。

递归用法

我们也可以用可变模板来实现编译期递归。下面就是个小例子:
template <typename T>
constexpr auto sum(T x)
{
return x;
}
template <typename T1, typename T2,
typename... Targ>
constexpr auto sum(T1 x, T2 y,
Targ... args)
{
return sum(x + y, args...);
}
在上面的定义里,如果 sum 得到的参数只有一个,会走到上面那个重载。如果有两个或更多参数,编译器就会选择下面那个重载,执行一次加法,随后你的参数数量就少了一个,因而递归总会终止到上面那个重载,结束计算。
要使用上面这个模板,我们就可以写出像下面这样的函数调用:
auto result = sum(1, 2, 3.5, x);
模板会这样依次展开:
sum(1 + 2, 3.5, x)
sum(3 + 3.5, x)
sum(6.5 + x)
6.5 + x
注意我们都不必使用相同的数据类型:只要这些数据之间可以应用 +,它们的类型无关紧要……
再看另一个复杂些的例子,函数的组合 [2]。如果我们有函数 和 函数 ,要得到函数的联用 ,其满足:
我们能不能用一种非常简单的方式,写不包含变量 的表达式来表示函数组合呢?答案是肯定的。
跟上面类似,我们需要写出递归的终结情况,单个函数的“组合”:
template <typename F>
auto compose(F f)
{
return [f](auto&&... x) {
return f(
forward<decltype(x)>(x)...);
};
}
上面我们仅返回一个泛型 lambda 表达式,保证参数可以转发到 f。记得我们在[第 16 讲] 讲过泛型 lambda 表达式,本质上就是一个模板,所以我们按转发用法的可变模板来理解上面的 ... 部分就对了。
下面是正常有组合的情况:
template <typename F,
typename... Args>
auto compose(F f, Args... other)
{
return [f,
other...](auto&&... x) {
return f(compose(other...)(
forward<decltype(x)>(x)...));
};
}
在这个模板里,我们返回一个 lambda 表达式,然后用 f 捕捉第一个函数对象,用 args... 捕捉后面的函数对象。我们用 args... 继续组合后面的部分,然后把结果传到 f 里面。
上面的模板定义我实际上已经有所简化,没有保持值类别。完整的包含完美转发的版本,请看参考资料 [3] 中的 functional.h 实现。
下面我们来试验一下使用这个 compose 函数。我们先写一个对输入范围中每一项都进行平方的函数对象:
auto square_list =
[](auto&& container) {
return fmap(
[](int x) { return x * x; },
container);
};
我们使用了[第 13 讲] 中给出的 fmap,而不是标准库里的 transform,是因为后者接口非函数式,无法组合——它要求参数给出输出位置的迭代器,会修改迭代器指向的内容,返回结果也只是单个的迭代器;函数式的接口则期望不修改参数的内容,结果完全在返回值中。
我们这儿用了泛型 lambda 表达式,是因为组合的时候不能使用模板,只能是函数对象或函数(指针)——如果我们定义一个 square_list 模板的话,组合时还得显式实例化才行(写成 square_list<const vector<int>&> 的样子),很不方便。
我们再写一个求和的函数对象:
auto sum_list =
[](auto&& container) {
return accumulate(
container.begin(),
container.end(), 0);
};
那先平方再求和,就可以这样简单定义了:
auto squared_sum =
compose(sum_list, square_list);
我们可以验证这个定义是可以工作的:
vector v{1, 2, 3, 4, 5};
cout << squared_sum(v) << endl;
我们会得到:
55

tuple

上面的写法虽然看起来还不错,但实际上有个缺陷:被 compose 的函数除了第一个(最右边的),其他的函数只能接收一个参数。要想进一步推进类似的技巧,我们得首先解决这个问题。
在 C++ 里,要通用地用一个变量来表达多个值,那就得看多元组——tuple 模板了 [4]tuple 算是 C++98 里的 pair 类型的一般化,可以表达任意多个固定数量、固定类型的值的组合。下面这段代码约略地展示了其基本用法:
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
// 整数、字符串、字符串的三元组
using num_tuple =
tuple<int, string, string>;
ostream&
operator<<(ostream& os,
const num_tuple& value)
{
os << get<0>(value) << ','
<< get<1>(value) << ','
<< get<2>(value);
return os;
}
int main()
{
// 阿拉伯数字、英文、法文
vector<num_tuple> vn{
{1, "one", "un"},
{2, "two", "deux"},
{3, "three", "trois"},
{4, "four", "quatre"}};
// 修改第 0 项的法文
get<2>(vn[0]) = "une";
// 按法文进行排序
sort(vn.begin(), vn.end(),
[](auto&& x, auto&& y) {
return get<2>(x) <
get<2>(y);
});
// 输出内容
for (auto&& value : vn) {
cout << value << endl;
}
// 输出多元组项数
constexpr auto size = \
tuple_size_v<num_tuple>;
cout << "Tuple size is " << size << endl;
}
输出是:
2,two,deux
4,four,quatre
3,three,trois
1,one,une
Tuple size is 3
我们可以看到:
tuple 的成员数量由尖括号里写的类型数量决定。
可以使用 get 函数对 tuple 的内容进行读和写。(当一个类型在 tuple 中出现正好一次时,我们也可以传类型取内容,即,对我们上面的三元组,get<int> 是合法的,get<string> 则不是。)
可以用 tuple_size_v (在编译期)取得多元组里面的项数。
如果我们要用一个三项的 tuple 去调用一个函数,我们可以写类似这样的代码:
template <class F, class Tuple>
constexpr decltype(auto) apply(
F&& f, Tuple&& t)
{
return f(
get<0>(forward<Tuple>(t)),
get<1>(forward<Tuple>(t)),
get<2>(forward<Tuple>(t)));
}
这似乎已经挺接近我们需要的形式了,但实际调用函数的参数项数会变啊……
我们已经有了参数的项数(使用 tuple_size_v),所以我们下面要做的是生成从 0 到项数减一之间的整数序列。标准库里已经定义了相关的工具,我们需要的就是其中的 make_index_sequence [5],其简化实现如下所示:
template <class T, T... Ints>
struct integer_sequence {};
template <size_t... Ints>
using index_sequence =
integer_sequence<size_t, Ints...>;
template <size_t N, size_t... Ints>
struct index_sequence_helper {
typedef
typename index_sequence_helper<
N - 1, N - 1, Ints...>::type
type;
};
template <size_t... Ints>
struct index_sequence_helper<
0, Ints...> {
typedef index_sequence<Ints...>
type;
};
template <size_t N>
using make_index_sequence =
typename index_sequence_helper<
N>::type;
正如一般的模板代码,它看起来还是有点绕的。其要点是,如果我们给出 make_index_sequence<N>,则结果是 integer_sequence<size_t, 0, 1, 2, …, N - 1>(一下子想不清楚的话,可以拿纸笔来模拟一下模板的展开过程)。而有了这样一个模板的帮助之后,我们就可以写出下面这样的函数(同样,这是标准库里的 apply 函数模板 [6] 的简化版本):
template <class F, class Tuple,
size_t... I>
constexpr decltype(auto)
apply_impl(F&& f, Tuple&& t,
index_sequence<I...>)
{
return f(
get<I>(forward<Tuple>(t))...);
}
template <class F, class Tuple>
constexpr decltype(auto)
apply(F&& f, Tuple&& t)
{
return apply_impl(
forward<F>(f),
forward<Tuple>(t),
make_index_sequence<
tuple_size_v<
remove_reference_t<
Tuple>>>{});
}
我们如果有一个三元组 t,类型为 tuple<int, string, string>,去 apply 到一个函数 f,展开后我们得到 apply_impl(f, t, index_sequence<0, 1, 2>{}),再展开后我们就得到了上面那个有 get<0>get<1>get<2> 的函数调用形式。换句话说,我们利用一个计数序列的类型,可以在编译时展开 tuple 里的各个成员,并用来调用函数。

数值预算

上面的代码有点复杂,而且似乎并没有完成什么很重要的功能。我们下面看一个源自实际项目的例子。需求是,我们希望快速地计算一串二进制数中 1 比特的数量。举个例子,如果我们有十进制的 31 和 254,转换成二进制是 00011111 和 11111110,那我们应该得到 5 + 7 = 12。
显然,每个数字临时去数肯定会慢,我们应该预先把每个字节的 256 种情况记录下来。因而,如何得到这些计数值是个问题。在没有编译期编程时,我们似乎只能用另外一个程序先行计算,然后把结果填进去——这就很不方便很不灵活了。有了编译期编程,我们就不用写死,而让编译器在编译时帮我们计算数值。
利用 constexpr 函数,我们计算单个数值完全没有问题。快速定义如下:
constexpr int
count_bits(unsigned char value)
{
if (value == 0) {
return 0;
} else {
return (value & 1) +
count_bits(value >> 1);
}
}
可 256 个,总不见得把计算语句写上 256 遍吧?这就需要用到我们上面讲到的 index_sequence 了。我们定义一个模板,它的参数是一个序列,在初始化时这个模板会对参数里的每一项计算比特数,并放到数组成员里。
template <size_t... V>
struct bit_count_t {
unsigned char
count[sizeof...(V)] = {
static_cast<unsigned char>(
count_bits(V))...};
};
注意上面用 sizeof...(V) 可以获得参数的个数(在 tuple_size_v 的实现里实际也用到它了)。如果我们模板参数传 0, 1, 2, 3,结果里面就会有个含 4 项元素的数组,数值分别是对 0、1、2、3 的比特计数。
然后,我们当然就可以利用 make_index_sequence 来展开计算了,想产生几项就可以产生几项。不过,要注意到 make_index_sequence 的结果是个类型,不能直接用在 bit_count_t 的构造中。我们需要用模板匹配来中转一下:
template <size_t... V>
constexpr bit_count_t<V...>
get_bit_count(index_sequence<V...>)
{
return bit_count_t<V...>();
}
auto bit_count = get_bit_count(
make_index_sequence<256>());
得到 bit_count 后,我们要计算一个序列里的比特数就只是轻松查表相加了,此处不再赘述。

内容小结

今天我们讨论了在编译期处理不确定数量的参数和类型的基本语言特性,可变模板,以及可以操控可变模板的重要工具——tupleindex_sequence。用好这些工具,可以让我们轻松地完成一些编译期计算的工作。

课后思考

请考虑一下:
我展示了 compose 带一个或更多参数的情况。你觉得 compose 不带任何参数该如何定义?它有意义吗?
有没有可能不用 index_sequence 来初始化 bit_count?如果行,应该如何实现?
作为一个挑战,你能自行实现出 make_integer_sequence 吗?
期待你的答案。

参考资料

[1] cppreference.com, “Parameter pack”. https://en.cppreference.com/w/cpp/language/parameter_pack
[1a] cppreference.com, “形参包”. https://zh.cppreference.com/w/cpp/language/parameter_pack
[2] Wikipedia, “Function composition”. https://en.wikipedia.org/wiki/Function_composition
[2a] 维基百科, “复合函数”. https://zh.wikipedia.org/zh-cn/ 复合函数
[3] 吴咏炜, nvwa. https://github.com/adah1972/nvwa
[4] cppreference.com, “std::tuple”. https://en.cppreference.com/w/cpp/utility/tuple
[4a] cppreference.com, “std::tuple”. https://zh.cppreference.com/w/cpp/utility/tuple
[5] cppreference.com, “std::integer_sequence”. https://en.cppreference.com/w/cpp/utility/integer_sequence
[5a] cppreference.com, “std::integer_sequence”. https://zh.cppreference.com/w/cpp/utility/integer_sequence
[6] cppreference.com, “std::apply”. https://en.cppreference.com/w/cpp/utility/apply
[6a] cppreference.com, “std::apply”. https://zh.cppreference.com/w/cpp/utility/apply
分享给需要的人,Ta购买本课程,你将得18
生成海报并分享

赞 2

提建议

上一篇
17 | 函数式编程:一种越来越流行的编程范式
下一篇
19 | thread和future:领略异步中的未来
 写留言

精选留言(25)

  • 李亮亮
    2020-01-06
    N-->(N-1, N-1)-->(N-2, N-2, N-1)-->(1, 1 , 2 ....N-1)-->(0, 0, 1, 2...N-1)

    作者回复: 😁 学得挺快。

    5
  • 泰伦卢
    2020-01-09
    compose那是完全没看懂唉,还有sequence那...

    作者回复: 给个提示,到下面这个网站上看看模板是如何展开的: https://cppinsights.io/

    4
  • Geek_a16bbc
    2020-09-02
    用for loop來計算那256個count_bit()有什麼問題嗎?為什麼一定要在編譯期算好呢?

    作者回复: 没什么一定。这是一个功能,是不是需要用取决于你的具体项目需求。文中只是个例子而已。 如果这个计算时间有点长,超过零点几秒,可能会影响程序启动的体验,也许你就需要预算。 如果其他静态初始化的对象需要用到用到这些数据,那预算也是最简单的方式。因为如果没有额外的代码的话,静态初始化的顺序在不同文件是没有保证的。 ……

    2
  • Geek_845be1
    2020-12-24
    不用 index_sequence 来初始化 bit_count: ``` consteval int count_bits(unsigned char val) { if (val == 0) return 0; return (val & 1) + count_bits(val >> 1); } template <std::size_t N> consteval std::array<unsigned char, N> get_bit_count() { std::array<unsigned char, N> tbl{}; for (auto i = 0; i != N; ++i) tbl[i] = count_bits(i); return tbl; } ```
    展开

    作者回复: 很好。 两个细节注意一下。 1. consteval 是 C++20 的语法。在 C++17 里,我们仍然只能用 constexpr。 2. 在 C++20 里,tbl{} 是可以写成 tbl 的。但在 C++17 里不可以,标准要求所有的 constexpr 对象必须在构造时完成初始化。

    1
  • Geek_a16bbc
    2020-09-05
    template <class T, T... Ints> struct integer_sequence {}; 為什麼需要class T?不能template<T... Ints>? template <size_t... Ints> using index_sequence = integer_sequence<size_t, Ints...>; 同樣的,這裡可以寫成integer_sequence<Ints...>?
    展开

    作者回复: 第一种写法,不可以。你不可以在不声明 T 的情况下,突然蹦出来一个 T。 第二种写法,也不可以,因为这是 integer_sequence 定义的模板形式。不过,你确实可以独立定义一个类似下面形式的模板,不使用 integer_sequence: template <size_t... Ints> struct index_sequence {};

    1
  • 宋强
    2020-03-16
    template <typename F> auto compose(F f) { return [f](auto&&... x) { return f( forward<decltype(x)>(x)...); }; } 老师,请问下auto&&... x没有出现在入参里,这个怎么产生呢?
    展开

    作者回复: 这儿是返回一个函数对象啊。x是这个函数对象的参数。

    1
  • 禾桃
    2020-01-07
    template <typename F> auto compose(F f) { return [f](auto&&... x) { return f(x...); }; } 貌似用compiler(gcc version 4.8.5 20150623) 就会遇到下面编译错误 // In function ‘auto compose(F)’: // error: expansion pattern ‘auto&&’ contains no argument packs // return [f](auto&&... x) { 用compiler(gcc version 8.3.1 20190311)就不会有问题。 如果公司目前只允许用(gcc version 4.8.5 20150623),请问有什么workaround? 谢谢!
    展开

    作者回复: --- 更新 --- 我费了九牛二虎之力,终于把例子改得能在 gcc 4.8 下工作了。我觉得你不想维护这样的代码的。 这儿空间不够。我放在这里: http://wyw.dcweb.cn/download.asp?path=&file=jike_18_gcc48.cpp 我觉得升级 GCC 绝对是更好的主意。 --- 原回复 --- 没啥好办法……泛型lambda至少要求gcc 4.9。只能不用这类功能了。 手写一个函数对象模板也许可以完成这个功能(让 f 成为其数据成员)。你可以试试看。我暂时没时间试验。

    1
  • 布拉姆
    2022-11-03 来自日本
    template<class F, class Tuple, size_t ...I> inline constexpr decltype(auto) apply_impl(F && f, Tuple && t, index_sequence<I...>) { return f( get<I>(forward<Tuple>(t)) ... ); } 这里对于index_sequence<I...>里面 I 有多少项目, 就展开多少项. 假如tuple一共2项, 则展开为: return f(std::get<0UL>(std::forward<std::pair<int, int> >(t)), std::get<1UL>(std::forward<std::pair<int, int> >(t))); 和下面原理一样: template <typename T, typename... Args> inline unique_ptr<T> make_unique(Args&&... args) { return unique_ptr<T>(new T(forward<Args>(args)...)); } forward<Args>(args)... 会在编译时实际逐项展开 Args 和 args ,参数有多少项,展开后就是多少项。
    展开
  • Marc Chan
    2022-03-12
    吴老师,因为我的工作年限比较短,刚满一年。看到第18讲,觉得这么复杂的模板,好像在工作中也没碰到过,就感觉有点离自己太远了的感觉。虽说慢慢看也能够看懂,但是就是会感觉到看完以后也没地方用。 请教一下这些内容往往会在什么地方用的多呢?或者说有没有一些更加适合初级C++ er 看的内容推荐呢?

    作者回复: 最开始学 C++ 的,就找一本好的教材(如《C++ Primer 中文版》)。做练习,确保自己理解。 每一种高级技巧都有应用的场景,但有些应用需要有一定的实际的项目经验。模板是一种抽象机制,主要用在写库、搭框架这样的场景。相信随着项目经验的增加和架构能力的拓展,你会看到它们的用武之地。

  • Peter
    2021-11-30
    怎么证明确实已经在编译期间已经计算过了呢?看反汇编吗?

    作者回复: 看汇编是最终确认方式。不是反汇编。用命令行选项来产生汇编文件。 GCC/Clang 下用 -S,MSVC 下用 /Fa。

  • 常振华
    2021-10-18
    auto bit_count = get_bit_count(make_index_sequence<256>()); <256>后面是不是多了一对圆括号()? make_index_sequence<256>展开之后,代入get_bit_count(index_sequence<V...>)模板,并没有一对圆括号()啊?

    作者回复: make_index_sequence<256> 是一个类型,你不能用类型(比如 int)去调用一个函数的。必须生成一个对象。make_index_sequence<256>() 也可以写成 make_index_sequence<256>{},代表一个默认构造的该类型的对象。 如果换更“普通”的代码为例,那 foo(int) 这样函数原型,你是不能用 foo(int) 这样的写法去调用的。你可以用 foo(42),也可以用 foo(int{})——后者实际相当于 foo(int(0)),也相当于 foo(0)。

  • 常振华
    2021-10-18
    为什么一会儿是大写的Tuple,一会儿又是小写的tuple,C++库里的模板不是小写tuple吗?

    作者回复: 大写的 Tuple 不是小写的 tuple。 大写的 Tuple 代表一个抽象的类名称,你可以把它替换成为任何一个名称,比如全部改成 Tup 或者 T。但因为意图是 tuple,所以采用这种拼法。

  • 宵练2233
    2021-06-28
    贴一个也用到sequence的std::string enum编译期互转的例子 https://tao-fu.gitee.io/2020/11/09/C++%E6%9D%82%E8%B0%88/EnumStringConversion/
  • chang
    2021-06-09
    吴老师,请问怎么查看某些代码是否在编译时计算的?比如以下代码(剽窃了Geek_845be1同学的),怎么确定get_bit_count<8>()是否在编译时计算的? #include <array> #include <iostream> using namespace std; constexpr std::size_t count_bits(std::size_t val) { if (!val) { return 0; } return 1 + count_bits(val & (val - 1)); } template <std::size_t N> constexpr std::array<std::size_t, N> get_bit_count() { std::array<std::size_t, N> counts{}; for (std::size_t i = 0; i < N; ++i) { counts[i] = count_bits(i); } return counts; } int main() { auto counts = get_bit_count<8>(); for (auto n : counts) { cout << n << " "; } cout << endl; }
    展开

    作者回复: 最靠谱的方案是看汇编。另外,如果变量是 constexpr,那就只有编译时能求值编译才能过了。

  • chang
    2021-06-09
    反复看着教程才把make_integer_sequence写出来(应该是半抄半写)。感觉这节已经把模板用得很偏了。个人认为若在现实项目中,最后一个bit_count的例子还是不要用模板好,为了节省运行时时间,却大大降低了代码的可读性及可维护性,不值当。

    作者回复: 可读性也取决于读者的眼睛。这个例子确实运行时计算也没什么大不了,但类似的技巧还是有很多适用场合的。 我目前在项目的公用代码里大量使用此类技巧。不要求大部分开发者来读此类代码,他们会用就行了。 记住,C++的很多功能是给库开发者提供的,不是给应用开发者提供的。

    1
  • 林林
    2021-04-13
    老师,我写了一个能在编译器计算出N以内的素数列表的代码,但在编译时提示“C1202 递归类型或函数依赖项上下文太复杂” (N=1000) , 尝试过N=100时是可以编译成功的。 不知道有没有可以让N=1000也通过的办法(比如让编译器能递归更深的层)?

    作者回复: 试试GCC?GCC的错误信息就会告诉你一个修改编译期递归深度的选项。其他就只能通过搜索引擎去找了。

    共 3 条评论
  • 某某某
    2021-01-31
    Tuple一下让我回到了vc6下写typelist的时代。但是现在的新代码反倒是看不太懂了,bit_count_t里面最后调用count_bits后的...是如何展开的。

    作者回复: 你可以自己看一下工具展开的结果: https://cppinsights.io/s/704e8a55

  • 闲着也是贤者
    2020-07-31
    老师, auto squared_sum = compose(sum_list, square_list);将这两个实参的位置替换后就不能工作呢,这是为什么呢?应该能正常工作,但是却出错了?

    作者回复: sum_list 返回单一数值,不满足 square_list 的参数要求。

  • 中山浪子
    2020-07-10
    写过一些模版,公司代码也涉及到模版,看了老师的模版代码以后,才发现自己还是不懂模版

    作者回复: 模板有简单的用法,也有复杂的用法。简单的用法有时更加实用,也比较容易维护,不容易出问题。

  • 吃鱼
    2020-06-03
    只能大概看懂,最后的例子想尝试编译一下,结果 auto bit_count = get_bit_count(make_index_sequence<256>()); 这一句报错了 匹配不到模板,读到这么晚好伤心。。。

    作者回复: 什么编译器,什么错误?按我要求的编译器和选项,都是可以通过的…… 另外,如果自己输入的话,也有出现小错误的可能。可以看一下我放在 GitHub 上的完整示例: https://github.com/adah1972/geek_time_cpp/tree/master/18