泛型编程：从基础到应用

# 泛型编程：模板、算法与概念的深入解析 ## 1. 引言 模板在编程中具有重要作用，它能提供以下能力： - 无信息损失地传递类型（以及值和模板）作为参数，这为内联提供了绝佳机会，当前的实现也充分利用了这一点。 - 延迟类型检查（在实例化时进行），这意味着可以整合来自不同上下文的信息。 - 以参数形式传递常量值，从而实现编译时计算。 模板为编译时计算和类型操作提供了强大的机制，可生成紧凑高效的代码。类型（类）可以包含代码和值。模板最常见的用途是支持泛型编程，即专注于通用算法的设计、实现和使用。泛型编程强调使用模板实现通用算法。而更注重生成技术（将模板视为类型和函数生成器）并依赖类型函数表达编译时计算的则是模板元编程。 模板的类型检查是检查模板定义中参数的使用，而非针对显式接口（在模板声明中），这类似于编译时的“鸭子类型”。泛型编程、元编程以及模板的所有应用的一个关键方面是统一处理内置类型和用户定义类型。例如，`accumulate()` 操作不关心相加的值的类型，只关心能否使用 `+` 运算符。 泛型编程主要关注两个方面： - 提升（Lifting）：将算法泛化，以允许最大（合理）范围的参数类型，即限制算法（或类）对属性的依赖为必要的部分。 - 概念（Concepts）：仔细精确地指定算法（或类）对其参数的要求。 ## 2. 算法与提升 函数模板是普通函数的泛化，它可以对各种数据类型执行操作，并使用作为参数传递的各种操作来实现这些操作。算法是解决问题的过程或公式，因此函数模板常被称为算法。 从对特定数据执行特定操作的函数转变为对各种数据类型执行更通用操作的算法，最有效的方法是从一个（最好是多个）具体示例进行泛化，这种泛化称为提升。以下是一个具体示例： ```cpp double add_all(double* array, int n) { double s {0}; for (int i = 0; i < n; ++i) s = s + array[i]; return s; } struct Node { Node* next; int data; }; int sum_elements(Node* first, Node* last) { int s = 0; while (first != last) { s += first->data; first = first->next; } return s; } ``` 这两个代码片段分别计算数组中双精度浮点数的总和以及单链表中整数的总和。我们可以尝试从这两个具体示例逐步开发一个通用算法。首先抽象出数据类型，写出伪代码： ```plaintext // 伪代码: T sum(data) { T s = 0 while (not at end) { s = s + current value get next data element } return s } ``` 要将其变为具体代码，需要三个操作来访问“容器”数据结构： - 未到末尾 - 获取当前值 - 获取下一个数据元素 对于实际数据，还需要三个操作： - 初始化为零 - 相加 - 返回结果 将伪代码转换为具体的类似 STL 的代码： ```cpp template<typename Iter, typename Val> Val sum(Iter first, Iter last) { Val s = 0; while (first != last) { s = s + *first; ++first; } return s; } ``` 这里使用了迭代器来表示序列，迭代器支持三个操作： - `*` 用于访问当前值 - `++` 用于前进到下一个元素 - `!=` 用于比较迭代器以检查是否到达序列末尾 这个算法可以用于数组和链表，以及整数和双精度浮点数。对于手工制作的单链表，需要为其提供迭代器： ```cpp struct Node { Node* next; int data; }; Node* operator++(Node* p) { return p->next; } int operator*(Node* p) { return p->data; } Node* end(lst) { return nullptr; } void test(Node* lst) { int s = sum<int*>(lst, end(lst)); } ``` `sum()` 函数还可以进一步泛化。例如，让调用者提供初始值并推导 `Val` 类型： ```cpp template<typename Iter, typename Val> Val accumulate(Iter first, Iter last, Val s) { while (first != last) { s = s + *first; ++first; } return s; } ``` 还可以进一步泛化，允许使用不同的操作： ```cpp template<typename Iter, typename Val, typename Oper> Val accumulate(Iter first, Iter last, Val s, Oper op) { while (first != last) { s = op(s, *first); ++first; } return s; } ``` 提升是一项需要应用领域知识和经验的技能。设计算法的最重要指导是从具体示例中提升，而不添加会影响其使用的特性（符号或运行时成本）。 ### 2.1 提升过程流程图 ```mermaid graph TD; A[具体函数] --> B[抽象数据类型]; B --> C[写出伪代码]; C --> D[确定操作需求]; D --> E[转换为具体代码]; E --> F[进一步泛化]; ``` ## 3. 概念 模板对其参数有哪些要求？模板代码对其参数类型有哪些假设？或者相反，一个类型必须提供什么才能作为模板的参数被接受？由于可以构建具有任意属性的类和模板，可能性是无限的。例如： - 提供 `-` 但不提供 `+` 的类型。 - 可以复制但不能移动值的类型。 - 复制操作不复制的类型。 - 使用 `==` 比较相等性的类型和使用 `compare()` 进行比较的类型。 - 将加法定义为成员函数 `plus()` 的类型和将其定义为非成员函数 `operator+()` 的类型。 如果每个类都有独特的接口，编写能接受多种不同类型的模板会变得困难；反之，如果每个模板的要求都独特，定义能用于多个模板的类型也会变得困难。因此，需要识别少量可用于多个模板和多个类型作为参数的概念（需求集），理想情况是实现类似物理世界的“插头兼容性”。 ### 3.1 发现概念 以 `String` 类模板为例，考虑类型 `X` 作为 `String<X>` 的参数需要满足什么条件。可以通过三个阶段的分析来回答这个问题： 1. 首先，查看初始实现，确定它从参数类型使用的属性（操作、函数、成员类型等）以及这些操作的含义，得到该模板实现的最小要求列表。 2. 其次，查看可能的替代模板实现，并列出它们对模板参数的要求。可能会决定对模板参数施加更多或更严格的要求，或者选择要求更少、更简单的实现。 3. 最后，查看得到的所需属性列表，并将其与用于其他模板的要求列表（概念）进行比较，尝试找到简单、最好是常见的概念来表达原本可能是许多长列表的要求。 对于 `String<C>`，其实现对参数 `C` 执行的操作是该实现的最小要求集： 1. `C` 通过复制赋值和复制初始化进行复制。 2. `String` 使用 `==` 和 `!=` 比较 `C`。 3. `String` 创建 `C` 的数组（这意味着 `C` 的默认构造）。 4. `String` 获取 `C` 的地址。 5. 当 `String` 销毁时，`C` 被销毁。 6. `String` 有 `>>` 和 `<<` 运算符，必须以某种方式读写 `C`。 编写概念时，需要注意以下几点： - 概念不是任意属性的集合，需要反映应用领域的基本属性。 - 概念应具有通用性、稳定性、跨多个算法的可用性和语义一致性等特点。 - 许多简单的约束可能不符合概念的标准，可称为约束或临时概念。 - 可以通过编写 constexpr 函数来实现概念，并使用 static_assert 进行检查。 - 概念可以涉及多个参数、数值参数等。 - 使用概念作为设计和测试的指导，确保模板实现不依赖于概念未指定的属性。 ### 3.2 概念与约束 概念不是任意属性的集合，大多数类型（或一组类型）的属性列表并不能定义一个连贯有用的概念。一个有用的概念列表必须反映一组算法或模板类的一组操作的需求。许多领域都有描述该领域基本概念的概念，如代数中的单子、域和环，STL 中的前向迭代