第7章 概念和泛型编程
编程：
你得从感兴趣的算法入手。
– Alex Stepanov
7.1 导言
模板是干嘛用的？换句话说，使用模板对什么样的编程技术更有效？它提供了：
把类型（以及值和模板）作为参数无损传递。这意味着内联的绝佳的机遇， 也是当前编译器实现着重发力的部分。
在实例化期，从各种语境把信息搜罗编排起来的机会。这意味着优化的机遇。
把常量作为参数传递的能力。这意味着编译期计算的能力。
换句话说，模板提供了强大的机制，用于编译期计算、类型操控，并导向紧凑高效的代码。 谨记，类型（类）即包含代码(§6.3.2)又包含值(§6.2.2)。
首要的也是最常见的模板用途，是支持 泛型编程（generic programming） ， 也就是关注于通用算法设计、实现和应用的编程。 此处，“通用”的意思是：算法的设计可接纳很广泛的类型， 只要它们符合算法在参数方面的要求即可。 搭配概束，模板是C++对泛型编程的主力支援。 模板提供了（编译期的）参数化多态。
7.2 概束(Concept)（C++20）
考虑来自 §6.3.1 的 sum()：
它可以针对任何支持begin()和end()的数据结构调用，
以便 区间-for循环 能运行。
这类数据结构包括标准库的vector、list和map。
另外，该数据结构的元素类型在使用方面有限制：该类型必须能够与Value参数相加。
可行的例子有int、double和Matrix（对任何靠谱的Matrix定义而言）。
我们说sum()在两个维度上是通用的：
用于存储元素的数据结构类型（“是个序列(sequence)”），以及元素的类型。
因此sum()要求其第一个模板参数是某种序列，其第二个模板参数是某种数字。
我们把这种要求称为 概束（concept） 。
对概束的支持尚未进入ISO C++， 但已经是一条ISO技术细则（Technical Specification）[ConceptsTS]。 某些编译器实现里已经有所应用，因此， 尽管其细节很可能会变动，尽管还要等几年才能进入生产环境代码， 我依然要冒险在这里推荐它。
7.2.1 概束应用
多数模板参数必须符合特定需求，以便模板能通过编译并生成正确的代码。
就是说，多数模板都是受限模板(§6.2.1)。
类型名称引入符号typename是最松散的约束，仅要求该参数是个类型。
通常仍有改进空间，重新考虑sum()例子：
这样就明确多了。一旦我们定义了概束Sequence和Number的意义，
编辑器仅根据sum()的接口就能驳回错误的调用，而无需再检查其函数体。
这改善了错误报告。
但是，这份sum()接口的细节并不完善：
我“忘了”说，需要把Sequence的元素于Number相加。
可以这样做：
序列的Value_type是序列中元素的类型。Arithmetic<X,Y>是个规则，
指明我们可以对X和Y类型的数字做算术运算。
这让我们避免了给vector<string>或者vector<int*>计算sum()的尝试，
却还能接受vector<int>以及vector<complex<double>>。
在上例中，我们仅需要+=运算，但处于简化及灵活性，不该把模板参数限制的太紧。
具体来说，我们后续可能用+和=，而非+=来实现sum()，
到那时就会庆幸用了更通用的规则（此处是Arithmetic），
而没有把需求缩窄到“可以+=“。
像第一个使用概束的sum()那样，指明部分细节已经很有用了。
如果细节不够完整，那么某些错误只能等到实例化期才能发现。
无论如何，指明部分细节就很有帮助了，它表明了意图，对平缓的增量开发至关重要，
也就是我们未能一开始就认清所有需求的情形。
有了完善的概束库的帮助，初步的规划就将近乎完善。
不难猜到，requires Arithmetic<Value_type<Seq>,Num>
被称为requirements子句。template<Sequence Seq>写法仅仅是显式requires Sequence<Seq>应用的简写。
如果喜欢详尽的方式，可以写出以下等价形式：
另一方面，也可以用与以上两个写法的等价形式这样写：
无论使用哪种形式，在设计模板的时候， 确保模板参数具有语意方面的合理约束是很重要的(§7.2.4)。
7.2.2 基于概束的重载
在妥善声明模板接口后，可以基于其属性进行重载，这与函数重载极其类似。
考虑一下标准库函数advance()(§12.3)的简化版本，它推进迭代器：
编译器会选择参数对需求匹配最紧密的模板。本例中，list仅有前向迭代器，
而vector提供了随机访问迭代器，因此有：
像其它类型的重载一样，这是个编译期机制，就是说没有运行时开销， 在编译器找不到最佳匹配时，会报二义性错误。 基于概束的重载，其规则远比普通重载(§1.3)简单。 首先考虑单个模板参数对应多个可选函数的情况：
如果参数不匹配概束，该备选函数不选。
如果参数仅匹配一个备选函数，选它。
如果参数对两个备选函数匹配程度相等，就是二义性。
如果参数匹配两个备选，但一个概束比另一个更紧密 （满足另一个函数全部需求还有富余），选前者。
某个备选函数想被选中就必须：
满足其全部参数，并且
至少跟其它备选的匹配同样好，并且
至少有一个参数匹配的更好。
7.2.3 代码有效性
有关模板实参是否满足模板对形参的需求这个问题，归根结底是某些表达式有效与否的问题。
使用requires表达式，可以检测一组表达式的有效性。例如：
不，那个requires requires不是笔误。
前面的requires发起了一个requirements从句，
后面的requires发起了一个requires表达式
requires表达式是一个断言，若其内部的表达式是有效代码，
它就为true，无效则为false。
我把requires表达式看作是泛型编程的汇编代码。
像常规的汇编代码那样，requires表达式极其灵活并且没有为编程限定任何规则。
就某种形式而言，它们是大部分重要泛型代码的根基，
就像汇编码是大部分重要常规代码的根基那样。
像汇编码那样，requires表达式不应该在“常规代码”中出现。
如果你的代码里出现了 requires requires，很可能是把它的层级搞得太低了。
advance()中的requires requires用法特意弄得粗劣和耍小聪明。
注意，我“忘记”要求+=，以及该运算所需的返回值类型。
尽量用命名概束，它们的名称暗含了语意方面的意义。勿谓言之不预也。
尽量采用命名良好的概束，它们具有定义准确的语意(§7.2.4)，
然后在定义这些概束的时候使用requires表达式。
7.2.4 概束定义
到头来，我们想找到有用的概束，
比方说程序库尤其是标准库里的Sequence和Arithmetic。
区间技术细则（Ranges Technical Specification）[RangesTS]提供了一套，
用于约束标准库算法(§12.7)。不过，简单的概束不难定义。
概束是一个编译期的谓词，用于规定一个或多个类型该如何使用。 考虑这第一个最简单的例子：
Equality_comparable这个概束的用途是：
确保能够对某个类型的值进行相等或不等比较。
我们直白地说，给定某个类型的两个值，它们必须可以用==和!=进行比较，
并且比较的结果必须能够转化到bool类型。例如：
概束Equality_comparable的定义跟英语描述严格等同，并不冗长。
任何concept的值总是bool类型。
定义Equality_comparable去处理不同类型的比较，几乎同样易如反掌：
typename T2 =T是说，如果没指明第二个模板参数，T2就和T一样，T是 默认模板参数（default template argument） 。
可以这样测试Equality_comparable：
对于更复杂的例子，考虑某个如下的序列：
如果类型S要作为Sequence使用，必须提供Value_type（其元素的类型），
以及一个iterator_type（其迭代器的类型；参见§12.1）。
还要确保具备返回迭代器的begin()和end()函数，以符合标准库容器(§11.3)的惯例。
最后，iterator_type必须是个input_iterator，其元素与S元素的类型相同。
最难定义的概束是表示基本语言概念的那种。总而言之，最好从现存的库里拿一套出来用。 对于一套有用的概束集，参见§12.7。
7.3 泛型编程
C++所支持的 泛型编程（generic programming） 形式，围绕着这样一个思想： 从具体、高效的算法抽象得出泛型算法，再把这个泛型算法跟多种数据形式结合， 继而生成各种有用的软件[Stepanov,2009]。 这种代表了基本运算和数据结构的抽象被称为 概束（concept） ； 它们的表现形式是对模板参数提出的条件。
7.3.1 概束的使用
优秀、好用的概束（concept）是很基础的，多数情况下它们是被发现的，而非出于设计。 比如整数和浮点数（连古典的C语言中都有定义）、序列， 以及更通用的数学概念，例如域和向量空间。 它们代表某个应用领域里的基本概念。 这就是它们被称作“概束（concept）”的原因。 要识别概束并将其形式化，以达到高效泛型编程必要的程度，这极具挑战。
对于基本用法，考虑概束Regular(§12.7)。
某个类型如果是常规（regular）的，就要表现得像int或者float那样。
某个常规类型的对象要：
可被默认构造
可用构造函数或者复制操作复制（以常见的复制语意，产生两个独立且相等的对象）
可用
==和!=进行比较不会因为过度耍小聪明的编程伎俩而招致技术问题
string是另一个常规类型的例子。
像int一样，string也是StrictTotallyOrdered的(§12.7)。
就是说，两个字符串可以用<、<=、>和>=进行语意良好的比较。
概束不仅是一个语法概念，根本上讲它事关语意。
比如说：别把+定义成除法；对于任何合理的数字系统，这都不符合要求。
不幸的是，在表达语意方面，我们尚无任何语言层面的支持，
因此只能依靠专业知识和直觉去获取暗合语意的概束。
不要定义语意上没意义的概束，比如Addable（可相加）和Subtractable（可相减）。
相反的，要在某个应用领域里，依靠该领域内的知识，去定义符合其基本概念的概束。
7.3.2 利用模板进行抽象
良好的抽象是从具体例子中精心培育而来的。 试图给所有假想中的需求和技术做准备，并对其进行“抽象”是个馊主意； 必将导致粗鄙和代码膨胀。 相反，应该以一个——最好是多个——实际使用的具体例子为开端， 并努力去消除那些无关本质的细节。考虑：
显而易见，这是诸多给数值序列求和的方法之一。
考虑一下，是什么让它变得不够通用：
为什么只能是
int？为什么只能是
vector？为什么只能求和成一个
double？为什么只能从
0开始计算？为什么只能是加法？
把具体类型换成模板参数，就可以回答前四个问题，
得出标准库算法accumulate最简单的形式：
这样就得到：
待遍历的数据结构被抽象成一对表示序列的迭代器(§12.1)。
待累加的类型被换成了参数。
初始值从输入获取；累加结果的类型就是初始值的类型。
一个快捷的检验或者——更靠谱的——评测表明， 针对多种数据结构调用生成的代码与手动编码的原版一致。 例如：
保留性能的同时，把一段具体代码（多段就更好了）泛化的过程叫做 提升（lifting） 。 反过来说，开发模板最好的办法通常是：
首先，写一个具体的版本
然后，调试、测试，并评估其性能
最后，用模板参数替换具体类型
自然而然的，不断重复begin()和end()很烦冗，因此可以把用户接口简化一点：
如果要彻底通用化，还可以抽象+=运算；参阅 §14.3。
7.4 可变参数模板
模板可定义成接受任意数量任意类型参数的形式。
这样的模板叫 可变参数模板（variadic template） 。
考虑一个简单的函数，对于具有<<运算符的任意类型，它都能输出该类型的值。
习惯上，实现可变参数模板的时候，要把第一个参数跟其余的分离开来， 然后为参数的尾部递归调用该可变参数模板：
typename...表明Tail是一个类型多样的序列。Tail...表明tail是一系列类型位于Tail中的值。
使用...声明的参数叫做 参数包（parameter pack） 。
此处tail是一个（函数参数的）参数包，
其元素类型可以在（模板参数的）参数包Tail中找到。
因此print()可以接收任意类型、任意数量的参数。
调用print()，会把参数分成头部（第一个）和尾部（其余的）。
头部会被输出，然后再为尾部调用print()。
到最后，理所当然地，tail就空了，于是就需要一个无参版本的print()去处理。
如果想避免 零参数 的情形，可以用一个编译期if去消除它：
我用了 编译期if(§6.4.3)，而非普通的 运行时if，
以避免生成最终那个“永不会被调用的print()”被生成出来。
可变参数模板（有时候称为 变参（variadic） ）的强大之处在于， 能够接收你交给它的任何参数。 其弱点包括：
要把递归的实现搞对，这有点棘手
递归实现在编译期有出其不意的代价
接口的类型检查本身，就是一个疑似过度精细的模板规则
由于其灵活性，可变参数模板被广泛用于标准库中，偶尔甚至被滥用了。
7.4.1 折叠表达式
为简化简短变参模板的实现，C++17提供了一个针对参数包元素进行有限迭代的形式。 例如：
此处，sum()可以接收任意类型的任意多个参数。
假设sum()确实会将其参数相加，则有：
sum的函数体使用了折叠表达式：
此处，(v+...+0)意思是把v的所有元素相加，从初始值0开始执行。
第一个参与加法运算的是“最右边”（下标值最大）的值：(v[0]+(v[1]+(v[2]+(v[3]+(v[4]+0)))))。
就是说，从右边，也就是0那个位置开始。这叫做 右叠（right fold） 。
或者，也可以用 左叠（left fold） ：
这次，最先参与加法运算是“最左边”（下标值最小）的元素：(((((0+v[0])+v[1])+v[2])+v[3])+v[4])。
就是说，从左边，也就是0那个位置开始。
折叠（fold） 是个非常强大的抽象，很明显与标准库的accumulate()有关联，
在不同的编程语言和社区里有多种名称。
在C++中，折叠表达式的使用，目前被限定在可变参数模板的简化方面。
折叠涉及的操作可以不是数值计算。考虑这个著名的例子：
很多用例仅涉及一组值，且可以转化为一个通用类型。 这种情况下，直接把参数复制到一个vector或者期望的容器类型，通常可以简化后续使用：
可以这样使用to_vector：
7.4.2 参数转发
通过接口把参数原封不动传递，是可变参数模板的重要用途。 考虑一个网络输入信道，其中输送具体值的方法是个参数。 不同的传送机制拥有各自的一套构造参数：
标准库函数forward()(§13.2.2)被用于传递参数，
从inputChannel的构造函数原封不动地送给Transport构造函数。
此处的重点是，inputChannel的作者可以构造一个Transport类型的对象，
而无需知晓用于构造特定Transport所需的参数为何。inputChannel的实现者仅需要知道所有Transport的通用接口。
前向操作在基础的函数库中十分常见，在那里通用性和较低运行时消耗是必要的， 而且极具通用性的接口很常见。
7.5 模板编译模型
假定有概束(§7.2)支持，模板参数会针对其概束进行检查。 此处发现的错误会报出来，程序员必须修复这些问题。 目前尚不能检查的部分，比如无约束参数，会推迟到模板会同一组模板参数生成的时候： “在模板实例化期间”。对于有概束支持以前的代码来说，在这里进行所有检查。 在使用概束的时候，只有概束检查通过，编译才能走到这儿。
实例化期间（较迟的）类型检验有个糟糕的副作用： 因为编译器要在信息从程序内多处汇集之后才能发现问题， 所以发现类型错误的时间特别迟，导致错误信息糟糕到令人发指。
模板的实例化期间，类型检查会对模板定义中的参数进行检查。
这提供了一个俗称 鸭子类型（duck type）
（“如果它走路像鸭子，叫声像鸭子，那它就是个鸭子（
If it walks like a duck and it quacks like a duck, it’s a duck）”）
的编译期变种。
或者——用术语说——我们操作的是值，该操作的形式和意义都仅依赖于其操作数。
这有别于另一种观点，即对象具有类型，而类型决定了该操作的形式和意义。
值“居住”在对象里。
这就是C++里对象（也即变量）运作的方式，并且必须是符合该对象需求的值才住得进去。
在编译期用模板搞定的内容，基本不涉及对象，仅有值。
有个例外，是constexpr函数(§1.6)里的局部变量，它在编译器里作为变量使用。
要使用某个无约束模板，其定义（而不仅是其声明）必须位于它被用到的作用域内。
例如，标准库头文件<vector>里有vector的定义。
在实践中，这意味着模板定义一般位于头文件，而非.cpp文件。
这一点在使用模块(§3.3)的时候有些变化。
使用模块时，常规函数和模板函数的源代码的组织方式相同。
在两种情况下，定义都不会受到与文本包含有关问题的干扰。
7.6 忠告
[1] 模板提供了一个编译期编程的通用机制；§7.1。
[2] 设计模板的时候，针对其模板参数，谨慎考虑假定的概束（需求）；§7.3.2。
[3] 设计模板的时候，从一个具体的版本开始实现、调试及评估；§7.3.2。
[4] 把模板作为一个设计工具；§7.3.1。
[5] 为所有的模板参数指定概束；§7.2; [CG: T.10]。
[6] 尽可能使用标准概束（如：区间概束，Ranges concepts）；§7.2.4; [CG: T.11]。
[7] 如果需要个简单的一次性函数对象，用lambda表达式；§6.3.2。
[8] 模板没有分离编译：请在每个用到它的编译单元里
#include模板定义[9] 用模板表示容器和区间；§7.3.2; [CG: T.3]。
[10] 避免缺乏语意意义的“概束”；§7.2; [CG: T.20]。
[11] 为概束定义一组完善的操作；§7.2; [CG: T.21]。
[12] 在需要一个函数接收不同类型不定数量的参数时，采用可变参数模板；§7.4。
[13] 对于类型相同的参数列表，别用可变参数模板（这种情况尽量用初值列表）；§7.4。
[14] 使用模板时，确保其定义（而不仅仅是声明）在作用域内；§7.5。
[15] 模板提供编译期的“鸭子类型”；§7.5。
最后更新于