7

概束和泛型编程

编程：

你得从感兴趣的算法入手。

– Alex Stepanov1

7.1 导言

模板是干嘛用的？换句话说，使用模板对什么样的编程技术更有效？它提供了：

  • 把类型（以及值和模板）作为参数无损传递。这意味着内联的绝佳的机遇， 也是当前编译器实现着重发力的部分。
  • 在实例化期，从各种语境把信息搜罗编排起来的机会。这意味着优化的机遇。
  • 把常量作为参数传递的能力。这意味着编译期计算的能力。

换句话说，模板提供了强大的机制，用于编译期计算、类型操控，并导向紧凑高效的代码。 谨记，类型（类）即包含代码(§6.3.2)又包含值(§6.2.2)。

首要的也是最常见的模板用途，是支持泛型编程（generic programming）， 也就是关注于通用算法设计、实现和应用的编程。 此处，“通用”的意思是：算法的设计可接纳很广泛的类型， 只要它们符合算法在参数方面的要求即可。 搭配概束，模板是C++对泛型编程的主力支援。 模板提供了（编译期的）参数化多态。

7.2 概束(Concept)（C++20）

考虑来自 §6.3.1 的 sum()：

template<typename Seq, typename Num>
Num sum(Seq s, Num v)
{
    for (const auto& x : s)
        v+=x;
    return v;
}

它可以针对任何支持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()例子：

template<Sequence Seq, Number Num>
Num sum(Seq s, Num v)
{
    for (const auto& x : s)
        v+=x;
    return v;
}

这样就明确多了。一旦我们定义了概束Sequence和Number的意义， 编辑器仅根据sum()的接口就能驳回错误的调用，而无需再检查其函数体。 这改善了错误报告。

但是，这份sum()接口的细节并不完善： 我“忘了”说，需要把Sequence的元素于Number相加。 可以这样做：

template<Sequence Seq, Number Num>
    requires Arithmetic<Value_type<Seq>,Num>
Num sum(Seq s, Num n);

序列的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>应用的简写。 如果喜欢详尽的方式，可以写出以下等价形式：

template<typename Seq, typename Num>
    requires Sequence<Seq> && Number<Num> && Arithmetic<Value_type<Seq>,Num>
Num sum(Seq s, Num n);

另一方面，也可以用与以上两个写法的等价形式这样写：

template<Sequence Seq, Arithmetic<Value_type<Seq>> Num>
Num sum(Seq s, Num n);

无论使用哪种形式，在设计模板的时候， 确保模板参数具有语意方面的合理约束是很重要的(§7.2.4)。

7.2.2 基于概束的重载

在妥善声明模板接口后，可以基于其属性进行重载，这与函数重载极其类似。 考虑一下标准库函数advance()(§12.3)的简化版本，它推进迭代器：

template<Forward_iterator Iter>
void advance(Iter p, int n) // 将p向前移动n个元素
{
    while (n--)
        ++p;                // 前向迭代器可以++，但不能+或+=
}

template<Random_access_iterator Iter>
void advance(Iter p, int n) // 将p向前移动n个元素
{
    p+=n;                   // 随机访问迭代器可以+=
}

编译器会选择参数对需求匹配最紧密的模板。本例中，list仅有前向迭代器， 而vector提供了随机访问迭代器，因此有：

void user(vector<int>::iterator vip, list<string>::iterator lsp)
{
    advance(vip,10); // 应用快速的 advance()
    advance(lsp,10); // 应用缓慢的 advance()
}

像其它类型的重载一样，这是个编译期机制，就是说没有运行时开销， 在编译器找不到最佳匹配时，会报二义性错误。 基于概束的重载，其规则远比普通重载(§1.3)简单。 首先考虑单个模板参数对应多个可选函数的情况：

  • 如果参数不匹配概束，该备选函数不选。
  • 如果参数仅匹配一个备选函数，选它。
  • 如果参数对两个备选函数匹配程度相等，就是二义性。
  • 如果参数匹配两个备选，但一个概束比另一个更紧密 （满足另一个函数全部需求还有富余），选前者。

某个备选函数想被选中就必须：

  • 满足其全部参数，并且
  • 至少跟其它备选的匹配同样好，并且
  • 至少有一个参数匹配的更好。

7.2.3 代码有效性

有关模板实参是否满足模板对形参的需求这个问题，归根结底是某些表达式有效与否的问题。

使用requires表达式，可以检测一组表达式的有效性。例如：

template<Forward_iterator Iter>
void advance(Iter p, int n) // 将p向前移动n个元素
{
    while (n--)
        ++p;                // 前向迭代器可以++，但不能+或+=
}


template<Forward_iterator Iter, int n>
    requires requires(Iter p, int i) { p[i]; p+i; } // Iter有取下标和加法操作
void advance(Iter p, int n) // 将p向前移动n个元素
{
    p+=n;                   // 随机访问迭代器可以+=
}

不，那个requires requires不是笔误。 前面的requires发起了一个requirements从句， 后面的requires发起了一个requires表达式

requires(Iter p, int i) { p[i]; p+i; }

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)。不过，简单的概束不难定义。

概束是一个编译期的谓词，用于规定一个或多个类型该如何使用。 考虑这第一个最简单的例子：

template<typename T>
concept Equality_comparable =
    requires (T a, T b) {
        { a == b } -> bool; // 用==比较两个T
        { a != b } -> bool; // 用!=比较两个T
    };

Equality_comparable这个概束的用途是： 确保能够对某个类型的值进行相等或不等比较。 我们直白地说，给定某个类型的两个值，它们必须可以用==和!=进行比较， 并且比较的结果必须能够转化到bool类型。例如：

static_assert(Equality_comparable<int>);    // 成功
struct S { int a; };
static_assert(Equality_comparable<S>);      // 失败，因为结构体不会自动获得==和!=

概束Equality_comparable的定义跟英语描述严格等同，并不冗长。 任何concept的值总是bool类型。

定义Equality_comparable去处理不同类型的比较，几乎同样易如反掌：

template<typename T, typename T2 =T>
concept Equality_comparable =
    requires (T a, T2 b) {
        { a == b } -> bool; // 把一个 T 和一个 T2 用 == 进行比较
        { a != b } -> bool; // 把一个 T 和一个 T2 用 != 进行比较
        { b == a } -> bool; // 把一个 T2 和一个 T 用 == 进行比较
        { b != a } -> bool; // 把一个 T2 和一个 T 用 != 进行比较
    };

typename T2 =T是说，如果没指明第二个模板参数，T2就和T一样， T是默认模板参数（default template argument）。

可以这样测试Equality_comparable：

static_assert(Equality_comparable<int,double>); // 成功
static_assert(Equality_comparable<int>);        // 成功(T2默认是int)
static_assert(Equality_comparable<int,string>); // 失败

对于更复杂的例子，考虑某个如下的序列：

template<typename S>
concept Sequence = requires(S a) {
    typename Value_type<S>;             // S必须具备一个值类型
    typename Iterator_type<S>;          // S必须具备一个迭代器类型

    { begin(a) } -> Iterator_type<S>;   // begin(a) 必须返回一个迭代器
    { end(a) } -> Iterator_type<S>;     // end(a) 必须返回一个迭代器

    requires Same_type<Value_type<S>,Value_type<Iterator_type<S>>>;
    requires Input_iterator<Iterator_type<S>>;
};

如果类型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 利用模板进行抽象

良好的抽象是从具体例子中精心培育而来的。 试图给所有假想中的需求和技术做准备，并对其进行“抽象”是个馊主意； 必将导致粗鄙和代码膨胀。 相反，应该以一个——最好是多个——实际使用的具体例子为开端， 并努力去消除那些无关本质的细节。考虑：

double sum(const vector<int>& v)
{
    double res = 0;
    for (auto x : v)
        res += x;
    return res;
}

显而易见，这是诸多给数值序列求和的方法之一。

考虑一下，是什么让它变得不够通用：

  • 为什么只能是int？
  • 为什么只能是vector？
  • 为什么只能求和成一个double？
  • 为什么只能从0开始计算？
  • 为什么只能是加法？

把具体类型换成模板参数，就可以回答前四个问题， 得出标准库算法accumulate最简单的形式：

template<typename Iter, typename Val>
Val accumulate(Iter first, Iter last, Val res)
{
    for (auto p = first; p!=last; ++p)
        res += *p;
    return res;
}

这样就得到：

  • 待遍历的数据结构被抽象成一对表示序列的迭代器(§12.1)。
  • 待累加的类型被换成了参数。
  • 初始值从输入获取；累加结果的类型就是初始值的类型。

一个快捷的检验或者——更靠谱的——评测表明， 针对多种数据结构调用生成的代码与手动编码的原版一致。 例如：

void use(const vector<int>& vec, const list<double>& lst)
{
    auto sum = accumulate(begin(vec),end(vec),0.0); // 累加在一个double上
    auto sum2 = accumulate(begin(lst),end(lst),sum);
    //
}

保留性能的同时，把一段具体代码（多段就更好了）泛化的过程叫做提升（lifting）。 反过来说，开发模板最好的办法通常是：

  • 首先，写一个具体的版本
  • 然后，调试、测试，并评估其性能
  • 最后，用模板参数替换具体类型

自然而然的，不断重复begin()和end()很烦冗，因此可以把用户接口简化一点：

template<Range R, Number Val>   // Range是具有begin()和end()的东西
Val accumulate(const R& r, Val res = 0)
{
    for (auto p = begin(r); p!=end(r); ++p)
        res += *p;
    return res;
}

如果要彻底通用化，还可以抽象+=运算；参阅 §14.3。

7.4 可变参数模板

模板可定义成接受任意数量任意类型参数的形式。 这样的模板叫可变参数模板（variadic template）。 考虑一个简单的函数，对于具有<<运算符的任意类型，它都能输出该类型的值。

void user()
{
    print("first: ", 1, 2.2, "hello\n"s); // first: 1 2.2 hello

    print("\nsecond: ", 0.2, 'c', "yuck!"s, 0, 1, 2, '\n'); // second: 0.2 c yuck! 0 1 2
}

习惯上，实现可变参数模板的时候，要把第一个参数跟其余的分离开来， 然后为参数的尾部递归调用该可变参数模板：

void print()
{
    // 对于无参数的这份：什么都不做
}

template<typename T, typename... Tail>
void print(T head, Tail... tail)
{
    // 为每一个参数执行的，例如：
    cout << head << ' ';
    print(tail...);
}

typename...表明Tail是一个类型多样的序列。 Tail...表明tail是一系列类型位于Tail中的值。 使用...声明的参数叫做参数包（parameter pack）。 此处tail是一个（函数参数的）参数包， 其元素类型可以在（模板参数的）参数包Tail中找到。 因此print()可以接收任意类型、任意数量的参数。

调用print()，会把参数分成头部（第一个）和尾部（其余的）。 头部会被输出，然后再为尾部调用print()。 到最后，理所当然地，tail就空了，于是就需要一个无参版本的print()去处理。 如果想避免 零参数 的情形，可以用一个编译期if去消除它：

template<typename T, typename... Tail>
void print(T head, Tail... tail)
{
    cout << head << ' ';
    if constexpr(sizeof...(tail)> 0)
        print(tail...);
}

我用了 编译期if(§6.4.3)，而非普通的 运行时if， 以避免生成最终那个“永不会被调用的print()”被生成出来。

可变参数模板（有时候称为变参（variadic））的强大之处在于， 能够接收你交给它的任何参数。 其弱点包括：

  • 要把递归的实现搞对，这有点棘手
  • 递归实现在编译期有出其不意的代价
  • 接口的类型检查本身，就是一个疑似过度精细的模板规则

由于其灵活性，可变参数模板被广泛用于标准库中，偶尔甚至被滥用了。

7.4.1 折叠表达式

为简化简短变参模板的实现，C++17提供了一个针对参数包元素进行有限迭代的形式。 例如：

template<typename... T>
int sum(T... v)
{
    return (v + ... + 0);   // 以0为初值，把v的所有元素相加
}

此处，sum()可以接收任意类型的任意多个参数。 假设sum()确实会将其参数相加，则有：

int x = sum(1, 2, 3, 4, 5); // x 成为 15
int y = sum('a', 2.4, x);   // y 成为 114（2.4被截断了，'a'的值是97）

sum的函数体使用了折叠表达式：

return (v + ... + 0);   // 以0为初值，把v的所有元素相加

此处，(v+...+0)意思是把v的所有元素相加，从初始值0开始执行。 第一个参与加法运算的是“最右边”（下标值最大）的值： (v[0]+(v[1]+(v[2]+(v[3]+(v[4]+0)))))。 就是说，从右边，也就是0那个位置开始。这叫做右叠（right fold）。 或者，也可以用左叠（left fold）：

template<Number... T>
int sum2(T... v)
{
    return (0 + ... + v);   // 把v的所有元素加到0上
}

这次，最先参与加法运算是“最左边”（下标值最小）的元素： (((((0+v[0])+v[1])+v[2])+v[3])+v[4])。 就是说，从左边，也就是0那个位置开始。

折叠（fold）是个非常强大的抽象，很明显与标准库的accumulate()有关联， 在不同的编程语言和社区里有多种名称。 在C++中，折叠表达式的使用，目前被限定在可变参数模板的简化方面。 折叠涉及的操作可以不是数值计算。考虑这个著名的例子：

template<typename ...T>
void print(T&&... args)
{
    (std::cout << ... << args) << '\n'; // 输出所有参数
}
print("Hello!"s,' ',"World ",2017); // (((((std::cout << "Hello!"s) << ’ ’) << "World ") << 2017) << ’\n’);

很多用例仅涉及一组值，且可以转化为一个通用类型。 这种情况下，直接把参数复制到一个vector或者期望的容器类型，通常可以简化后续使用：

template<typename Res, typename... Ts>
vector<Res> to_vector(Ts&&... ts)
{
    vector<Res> res; (res.push_back(ts) ...);   // 不需要初始值
    return res;
}

可以这样使用to_vector：

auto x = to_vector<double>(1,2,4.5,'a');

template<typename... Ts>
int fct(Ts&&... ts)
{
    auto args = to_vector<string>(ts...);   // args[i]是第i个参数
    // ... 在这里使用 args ...
}

int y = fct("foo", "bar", s);

7.4.2 参数转发

通过接口把参数原封不动传递，是可变参数模板的重要用途。 考虑一个网络输入信道，其中输送具体值的方法是个参数。 不同的传送机制拥有各自的一套构造参数：

template<typename Transport>
    requires concepts::InputTransport<Transport>
class InputChannel {
public:
    // ...
    InputChannel(TransportArgs&&... transportArgs)
        : _transport(std::forward<TransportArgs>(transportArgs)...) {}
    // ...
    Transport _transport;
};

标准库函数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。
1. 出自一份意大利杂志《INFOMEDIA》对 Alexander A. Stepanov 的访谈录，访谈内容全文位于 http://www.stlport.org/resources/StepanovUSA.html。—— 译者注 ↩

results matching ""

    No results matching ""