分销网站建立,杭州建设网 信用等级查询,机械加工网红订单,名匠装饰多少钱一平方泛型编程(Generic Programming)
目录
24.1 引言(Introduction)
24.2 算法和(通用性的)提升(Algorithms and Lifting)
24.3 概念(此指模板参数的插件)(Concepts)
24.3.1 发现插件集(Discovering a Concept)
24.3.2 概念与约束(Concepts and Constraints)
24.4 具体化…泛型编程(Generic Programming)
目录
24.1 引言(Introduction)
24.2 算法和(通用性的)提升(Algorithms and Lifting)
24.3 概念(此指模板参数的插件)(Concepts)
24.3.1 发现插件集(Discovering a Concept)
24.3.2 概念与约束(Concepts and Constraints)
24.4 具体化概念(Making Concepts Concrete)
24.4.1 公理(Axioms)
24.4.2 多参数概念(Multi-argument Concepts)
24.4.3 值概念(Value Concepts)
24.4.4 约束检查(Constraints Checks)
24.4.5 模板定义检查(Template Definition Checking)
24.5 建议(Advice) 24.1 引言(Introduction) 模板有什么用换句话说使用模板时哪些编程技术是有效的模板提供
• 能够将类型(以及值和模板)作为参数传递而不会丢失信息。这意味着内联的绝佳机会当前的实现充分利用了这一点。
• 延迟类型检查(在实例化时完成)。这意味着有机会将来自不同上下文的信息编织在一起。
• 能够将常量值作为参数传递。这意味着能够进行编译时计算。 换句话说模板为编译时计算和类型操作提供了一种强大的机制可以产生非常紧凑和高效的代码。请记住类型(类)可以包含代码和值。 模板的第一个也是最常见的用途是支持泛型编程即专注于通用算法的设计、实现和使用的编程。这里的“通用(general)”意味着算法可以设计为接受各种各样的类型只要它们满足算法对其参数的要求。模板是 C 对泛型编程的主要支持。模板提供(编译时)参数多态性。 “泛型编程”有很多定义。因此该术语可能会令人困惑。然而在 C 的语境中“泛型编程”意味着强调使用模板实现的通用算法的设计。 更多地关注生成技术(将模板视为类型和函数生成器)并依靠类型函数来表达编译时计算被称为模板元编程这是第 28 章的主题。 为模板提供的类型检查检验模板定义中参数的使用而不是针对显式接口(在模板声明中)。这提供了通常称为鸭子类型(duck typing)的编译时变体(“如果它走路像鸭子叫起来像鸭子那么它就是鸭子”)。或者——使用更专业的术语——我们对值进行操作操作的存在性和含义完全取决于其操作数值。这与对象具有类型的替代观点不同类型决定了操作的存在和含义。值“存在于”对象中。这是对象(例如变量)在 C 中的工作方式只有满足对象要求的值才能放入其中。在编译时使用模板所做的事情不涉及对象只涉及值。特别是编译时没有变量。因此模板编程类似于动态类型编程语言中的编程但运行时成本为零并且在运行时类型语言中表现为异常的错误在 C 中变为编译时错误。 通用编程、元编程以及所有模板使用的一个关键方面是统一处理内置类型和用户定义类型。例如accumulate() 操作并不关心它所加的值的类型是 int、complexdouble 还是矩阵。它关心的是它们可以使用 运算符相加。使用类型作为模板参数并不意味着或要求使用类层级结构或任何形式的运行时对象类型的自我识别。这在逻辑上是令人满意的并且对于高性能应用程序至关重要。
本节重点介绍泛型编程的两个方面
• 提升(Lifting)将算法泛化以允许最大(合理)范围的参数类型(§24.2)也就是说将算法(或类)对属性的依赖限制在必要的范围内。
• Concepts(布尔谓词)仔细而准确地指定算法(或类)基于其参数的要求(§24.3)。
24.2 算法和(通用性的)提升(Algorithms and Lifting) 函数模板是普通函数的泛化因为它可以对各种数据类型执行操作并使用作为参数传递的各种操作来实现这些操作。算法是解决问题的过程或公式一系列有限的计算步骤来产生结果。因此函数模板通常被称为算法。 我们如何从一个对特定数据执行特定操作的函数转变为一个对各种数据类型执行更通用操作的算法获得良好算法的最有效方法是从一个(最好是多个)具体示例进行概括。这种概括称为提升即从具体函数中提升通用算法。在保持性能并关注合理性的同时从具体到抽象非常重要。过于聪明的程序员可能进行荒谬的概括以试图涵盖所有可能发生的情况。因此在没有具体示例的情况下尝试从第一原理进行抽象通常会导致代码臃肿、难以使用。
我将通过一个具体的例子来说明提升的过程。考虑一下
double add_all(double∗ array, int n)
// 基于double 数组的具体算法
{
double s {0};
for (int i 0; in; i)
s s array[i];
return s;
}
显然这计算了参数数组中double数的总和。另请考虑
struct Node {
Node∗ next;
int data;
};
int sum_elements(Node∗ first, Node∗ last)
// 基于int列表的另一个具体的算法
{
int s 0;
while (first!last) {
s first−data;
first first−next;
}
return s;
}
这将计算由 Node 实现的单链表中的整数之和。 这两个代码片段在细节和风格上有所不同但经验丰富的程序员会立即说“好吧这只是累积算法的两种实现。”这是一种流行的算法。与大多数流行算法一样它有很多名字包括减少、折叠、求和与聚合。但是让我们尝试分阶段从两个具体示例中开发一个通用算法以便了解提升的过程。首先我们尝试抽象出数据类型这样我们就不必具体说明
• double 对比 int, 或
• 数组对比链表。
为此我写了一些伪代码
// pseudo code:
T sum(data)
// 通过值类型和容器类型以某种方式进行参数化
{
T s 0
while (not at end) {
s s current value
get next data element
}
return s
} 为了具体化我们需要三个操作来访问“容器”数据结构
• 不在末尾
• 获取当前值
• 获取下一个数据元素
对于实际数据我们还需要三个操作
• 初始化为零
• 添加
• 返回结果
显然这不太精确但我们可以将其转换为代码
// 具的类 STL代码:
templatetypename Iter, typename Val
Val sum(Iter first, Iter last)
{
Val s 0;
while (first!last) {
s s ∗first;
first;
}
return s;
} 在这里我利用了对 STL 中表示值序列的常用方法(§4.5)的了解。该序列表示为一对支持三种操作的迭代器
• ∗ 用于访问当前值
• 用于前进到下一个元素
• ! 用于比较迭代器以检查我们是否处于序列的末尾
我们现在有了一个算法(一个函数模板)它既可用于数组又可用于链表既可用于整数又可用于双精度数。数组示例立即生效因为 double∗ 是迭代器的一个示例
double ad[] {1,2,3,4};
double s sumdouble∗(ad,ad4);
要使用手工制作的单链表我们需要为其提供一个迭代器。给定几个操作Node∗ 可以作为迭代器
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 sumint∗(lst,end(lst));
} 我使用 nullptr 作为结束迭代器。我使用显式模板参数(此处为 int)来允许调用者指定要用于累加器变量的类型。 到目前为止我们所拥有的代码比许多现实世界的代码更通用。例如sum() 适用于浮点数列表(所有精度)、整数数组(所有范围)以及许多其他类型例如 vectorchar。重要的是sum()与我们开始时手工编写的函数一样高效。我们不想以牺牲性能为代价来实现通用性。 经验丰富的程序员会注意到 sum() 可以进一步推广。特别是使用额外的模板参数很不方便而且我们需要初始值 0。我们可以解决这个问题方法是让调用者提供一个初始值然后推断 Val
templatetypename Iter, typename Val
Val accumulate(Iter first, Iter last, Val s)
{
while (first!last) {
s s ∗first;
first;
}
return s;
}
double ad[] {1,2,3,4};
double s1 accumulate(ad,ad4,0.0); // 按 double 叠加
double s2 accumulate(ad,ad4,0); // 按 int 叠加
但为什么是 有时我们想将元素相乘。事实上似乎有很多操作我们可能想应用于序列的元素。这导致了进一步的概括
templatetypename 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;
}
我们现在使用参数 op 将元素值与累加器组合起来。例如
double ad[] {1,2,3,4};
double s1 accumulate(ad,ad4,0.0,std::plusdouble); // 如前
double s2 accumulate(ad,ad4,1.0,std::multiplydouble);
标准库提供常用操作例如加法和乘法作为可用作参数的函数对象。在这里我们看到了让调用者提供初始值的实用性0 和 ∗ 不能很好地结合在一起进行累加。标准库提供了对 accumulate() 的进一步泛化允许用户提供 的替代方案以将“加法”的结果与累加器 (§40.6) 结合起来。
提升是一项需要应用领域知识和一定经验的技能。设计算法最重要的单一指南是从具体示例中提升算法而不添加会影响其使用的特性(符号或运行时成本)。标准库算法是提升的结果并且高度重视性能问题。 24.3 概念(此指模板参数的插件)(Concepts) 模板对其参数的要求是什么换句话说模板代码对其参数类型有何假设或者反过来说类型必须提供什么才能被接受为模板的参数可能性是无限的因为我们可以构建具有任意属性的类和模板例如
• 提供 − 但不提供 的类型
• 可以复制但不能移动值的类型
• 复制操作不复制的类型 (§17.5.1.3)
• 比较相等的类型和其他 compare() 比较相等的类型
• 将加法定义为成员函数 plus() 的类型和其他将其定义为非成员函数 operator() 的类型
在这个方向上存在着混乱。如果每个类都有一个唯一的接口那么编写可以采用多种不同类型的模板就变得很困难。相反如果每个模板的要求都是唯一的那么定义可以用于许多模板的类型就变得很困难。我们必须记住并跟踪大量接口这对于小型程序来说是可行的但对于现实世界的库和程序来说却难以管理。我们需要做的是确定少量的要求(需求集)这些概念(ideal)可以作为参数用于许多模板和许多类型。理想的情况是某种我们从物理世界所知道的“插件兼容性(plug compatibility)”具有少量的标准插件设计。
24.3.1 发现插件集(Discovering a Concept) 作为示例考虑第 23.2 节中的 String 类模板
templatetypename C
class String {
// ...
};
类型 X 需要满足什么要求才能用作 String 的参数StringX更一般地说在这样的字符串类中要成为字符需要什么经验丰富的设计师会对这个问题有少数可能的答案并根据这些答案开始设计。然而让我们考虑一下如何从第一原理来回答这个问题。我们进行三阶段分析
[1] 首先我们查看我们的(初始)实现并从其参数类型(以及这些操作的含义)中确定它使用哪些属性(操作、函数、成员类型等)。结果列表是该特定模板实现的最低要求。
[2] 接下来我们查看合理的替代模板实现并列出它们对模板参数的要求。这样做我们可能会决定对模板参数提出更多或更严格的要求以允许替代实现。或者我们可能决定选择一种要求更少和/或更简单的实现。
[3] 最后我们查看所需属性的结果列表(或列表)并将其与我们用于其他模板的需求(概念)列表进行比较。我们尝试找到简单的、最好是通用的概念这些概念可以表达原本会有很多长列表的需求。这里的目的是让我们的设计受益于分类的一般工作。产生的概念更容易给出有意义的名称也更容易记住。他们还应通过将概念变化限制在必要的范围内来最大限度地提高模板和类型的互操作性。
前两个步骤与我们将具体算法概括(“提升”)为通用算法(§24.2)的方式非常相似。最后一步抵制了为每个算法提供一组与其实现完全匹配的参数要求的诱惑。这样的需求列表过于专业化且不稳定对实现的每次更改都意味着对作为算法接口一部分记录的需求进行更改。
对于 StringC首先考虑 String 实现对参数 C 实际执行的操作(§19.3)。这将是 String 实现的最低要求集
[1] C 通过复制赋值和复制初始化进行复制。
[2] String 使用 和 ! 比较 C。
[3] String 创建 C 数组(这意味着 C 的默认构造)。
[4] String 获取 C 的地址。
[5] 当 String 被销毁时C 也会被销毁。
[6] String 有 和 运算符它们必须以某种方式读取和写入 C。
要求 [4] 和 [5] 是我们通常假设所有数据类型都具备的技术要求我不会讨论无法满足这些要求的类型这些类型几乎都是过于聪明的产物。第一个要求——值可以复制——对于一些重要的类型(例如代表真实资源的 std::unique_ptr)来说并不正确(§5.2.1,§34.3.1)。但是对于几乎所有“普通类型”这都是正确的所以我们需要它。调用复制操作的能力与语义要求相伴而生即副本确实是原始副本也就是说除了获取地址之外两个副本的行为完全相同。因此复制的能力通常(对于我们的 String)与提供 的要求相伴而生并且具有通常的语义。 通过要求赋值我们暗示 const 类型不能用作模板参数。例如Stringconst char 不能保证工作。在这种情况下这没问题就像大多数情况一样。赋值意味着算法可以使用其参数类型的临时变量创建参数类型对象的容器等。这并不意味着我们不能使用 const 来指定接口。例如
templatetypename T
bool operator(const StringT s1, const StringT s2)
{
if (s1.size()!s2.siz e()) return false;
for (auto i 0; i!s1.size(); i)
if (s1[i]!s2[i]) return false;
return true;
} 对于 StringX我们要求 X 类型的对象可以复制。另外通过其参数类型中的 constoperator() 承诺不会写入 X 元素。
我们是否应该要求元素类型 C 进行移动毕竟我们为 StringC 提供了移动操作。我们可以这样做但这不是必需的我们对 C 的操作可以通过复制来处理如果某些复制被隐式转换为移动(例如当我们返回 C 时)那就更好了。特别是可能很重要的示例(例如 StringStringchar)将正常工作(正确且高效)而无需将移动操作添加到要求中。
到目前为止一切都很好但最后一个要求( 我们可以使用 和 读取和写入 C )似乎有点多余。我们真的可以读取和写入每种类型的字符串吗也许这样说会更好如果我们读取和写入 StringX那么 X 必须提供 和 也就是说我们不是要求 C 满足整个字符串的要求而是(仅)要求我们实际读取和写入的字符串满足该要求。
这是一个重要且基本的设计选择我们可以对类模板参数设置要求(以便它们适用于所有类成员)或者只对单个类函数成员的模板参数设置要求。后者更灵活但也更冗长(我们必须表达每个需要它的函数的要求)程序员更难记住。
查看到目前为止的需求列表我注意到“普通字符串”中缺少几个对于“普通字符”常见的操作
[1] 无排序( 例如 )
[2] 不转换为整数值
经过初步分析后我们可以考虑我们的要求列表与哪些“众所周知的要求”(§24.3.2)相关。“普通类型”的核心要求是常规的。常规类型是一种
• 您可以使用适当的复制语义进行复制(使用赋值或初始化)(§17.5.1.3)
• 您可以默认构造
• 不会遇到各种次要技术要求的问题(例如获取变量的地址)
• 您可以比较相等性(使用 和 !)。
对于我们的 String 模板参数来说这似乎是一个很好的选择。我考虑过省去相等性比较但决定不相等的复制很少有用。通常常规是安全的选择思考 的含义可以帮助避免复制定义中的错误。所有内置类型都是常规的。 但是省略 String 的排序 () 是否有意义考虑一下我们如何使用字符串。模板(如 String)的预期用途应决定其对参数的要求。我们确实会广泛比较字符串此外当我们对字符串序列进行排序、将字符串放入集合等时我们也会间接使用比较。此外标准库string确实提供了 。从标准中寻找灵感通常是一个好主意。因此我们不仅需要我们的String是Regular还需要Ordered也是Regular。这就是要求 Ordered 。 有趣的是关于 Regular 是否应该要求 存在相当多的争论。似乎大多数与数字相关的类型都有自然顺序。例如字符以可以解释为整数的位模式编码并且任何值序列都可以按字典顺序排列。但是许多类型没有自然顺序(例如复数和图像)即使我们可以定义一个。其他类型有几种自然顺序但没有唯一的最佳顺序(例如记录可以按名称或地址排序)。最后一些(合理的)类型根本没有顺序。例如考虑
enum class rsp { rock, scissors, paper };
石头剪刀布游戏的关键在于
• scissors rock,
• rock paper, 以及
• paper scissors 。
但是我们的 String 不应该采用任意类型作为其字符类型它应该采用支持字符串操作(例如比较排序和 I/O)的类型因此我决定要求排序。 在对 String 模板参数的要求中添加默认构造函数以及 和 运算符使我们能够为 String 提供几个有用的操作。事实上我们对模板参数类型的要求越多模板实现者完成各种任务就越容易模板可以为其用户提供的服务就越多。另一方面重要的是不要用很少使用且仅由特定操作使用的要求来加载模板每个要求都会给参数类型的实现者带来负担并限制可用作参数的类型集。因此对于 StringX我们需要
• OrderedX
• 如果我们使用 StringX 的 和 则 X 的 和 (仅此而已)
• 如果我们定义并使用来自 X 的转换操作则可转换为整数(仅此而已) 到目前为止我们已经从句法属性的角度表达了对 String 字符类型的要求例如 X 必须提供复制操作、 和 。此外我们必须要求这些操作具有正确的语义例如复制操作进行复制(相等)比较相等(小于) 提供排序。通常这种语义涉及操作之间的关系。例如对于标准库我们有(§31.2.2.1)
• 副本的结果与原始值相等 (ab意味着 T{a}T{b})且副本与其来源无关 (§17.5.1.3)。
• 小于比较 (例如 ) 提供严格弱顺序 (§31.2.2.1)。 语义是用英文文本或(最好是)数学来定义的但遗憾的是我们没有办法用 C 本身表达语义要求(但请参见 §24.4.1)。对于标准库您可以在 ISO 标准中找到用格式化英语编写的语义要求。
24.3.2 概念与约束(Concepts and Constraints) 概念(concepts)不是任意的属性集合。大多数类型(或一组类型)的属性列表都没有定义一个连贯且有用的概念。要使作为一个概念有用需求列表必须反映一组算法或一组模板类操作的需求。在许多努力领域人们已经设计或发现了描述该领域基本内涵(concept)的概念(concept) (C 中“concept”一词的技术用法就是考虑到这种常见用法而选择的)。似乎很少有概念是有意义的(译注大概指术语能反映事件的真实含义)。例如代数建立在一元组(monad)、域(field) 和 环(ring) 等概念之上而 STL 依赖于前向迭代器、双向迭代器和随机访问迭代器等概念。在一个领域找到一个新概念是一项重大成就这不是你应该期望每年都做的事情。大多数情况下你通过检查研究领域或应用领域的基础文本来找到概念。本书中使用的概念集在§24.4.4 中描述。(译注此段说的概念是指事件的通用内涵。) “concepts”是一个非常笼统的思想在本质上与模板没有任何关系。甚至 KR C [Kernighan,1978] 也有概念即有符号整数类型是编程语言对内存中整数概念的概括。我们对模板参数的要求也是概念(无论如何表达)因此与概念相关的大多数有趣问题都出现在模板的上下文中。(译注此段指的概念是指对模板参数施加的基本要求。) 我认为概念是精心设计的实体反映了应用领域的基本属性。因此应该只有少数概念可以作为算法和类型设计的指导方针。这与物理插件和插座类似我们希望用最少的插头和插座简化我们的生活并降低设计和建造成本。这种理想可能与每个单独的通用算法(§24.2)和每个单独的参数化类的最低要求理想相冲突。此外这种理想可能与为类提供绝对最小接口的理想相冲突(§16.2.3)甚至与一些程序员认为他们有权“完全按照自己喜欢的方式”编写代码相冲突。然而如果不付出努力和某种形式的标准我们就无法获得插件兼容性。 我对概念的标准非常高我需要通用性、一定的稳定性、跨多种算法的可用性、语义一致性等等。事实上根据我的标准我们希望模板参数的许多简单约束都不符合概念的条件(译注指通用性的要求)。我认为这是不可避免的。特别是我们编写的许多模板并不反映通用算法或广泛适用的类型。相反它们是实现细节它们的参数只需反映模板的必要细节该模板的目的在于在某事物的单一实现中一次性使用。我称对此类模板参数的要求为约束或(如果必须)临时概念(译注不具有通用性的模板参数称为约束或临时概念)。看待约束的一种方法是将它们视为接口的不完整(部分)规范。通常部分规范很有用而且比没有规范要好得多。 举个例子考虑一个用于试验平衡二叉树平衡策略的库。该树将 Balancer 作为模板参数
templatetypename Node, typename Balance
struct node_base { // 平衡二叉树基类
// ...
}
Balancer只是一个提供三种节点操作的类。例如
struct Red_black_balance {
// ...
templatetypename Node static void add_fixup(Node∗ x);
templatetypename Node static void touch(Node∗ x);
templatetypename Node static void detach(Node∗ x);
};
显然我们想说一下 node_base 的参数需要什么但平衡器(balancer)并不意味着是一个广泛使用且易于理解的接口它只是作为平衡树的特定实现的细节使用。平衡器的这个想法(我犹豫是否使用“概念”这个词)不太可能在其他地方使用甚至不可能在平衡树实现的重大重写中保持不变。很难确定平衡器的确切语义。首先Balancer 的语义将严重依赖于 Node 的语义。在这些方面Balancer 与适当的概念(例如 Random_access_iterator)不同。然而我们仍然可以使用平衡器的最小规范“在节点上提供这三个函数”作为对 node_base 参数的约束。 请注意“语义(semantics)”在概念讨论中不断出现的方式。我发现“我能写出半形式语义吗”在决定某事物是概念还是仅仅是类型(或类型集)的临时约束集合时这个问题最有帮助。如果我能写出有意义的语义规范我就有了一个概念。如果不能我所拥有的是一个可能有用但不应期望其稳定或广泛有用的约束。
24.4 具体化概念(Making Concepts Concrete) 遗憾的是C 没有用于直接表达概念的特定语言功能。但是仅将“概念”作为设计理念(ideal)处理并以注释的形式非正式地呈现它们并不理想。首先编译器不理解注释因此仅以注释形式表达的需求必须由程序员检查并且无法帮助编译器提供良好的错误消息。经验表明即使没有直接的语言支持就无法完美地表示概念我们也可以使用执行模板参数属性的编译时检查的代码来近似它们。 (C中的)概念就是谓词(predicate即下判断并返回真假结果)也就是说在C中我们将概念视为一个编译时函数(它有一组要求)它查看一组模板参数如果它们满足概念的要求则返回 true如果它们不满足则返回 false。因此我们将概念实现为 constexpr 函数。在这里我将使用术语“约束检查(constraints check)”来指代 constexpr 谓词的调用该谓词检查概念是否具有一组类型和值。与专有的概念相比约束检查不处理语义问题它只是检查有关句法属性的假设。 考虑我们的String它的字符类型参数应该是有序的
templatetypename C
class String {
static_assert(OrderedC(),Strings character type is not ordered);
// ...
}; 当为类型 X 实例化 StringX 时编译器将执行static_assert。如果 OrderedX() 返回 true则编译将继续进行并生成与无断言时完全相同的代码。否则将生成错误消息。 乍一看这似乎是一种相当合理的解决方法。我宁愿说
templateOrdered C
class String {
// ...
};
不过那是未来的事所以让我们看看如何定义谓词 OrderedT()
templatetypename T
constexpr bool Ordered()
{
return RegularT() Totally_orderedT();
} 也就是说如果一个类型既是Regular类型又是Totally_ordered类型那么它就是Ordered类型。让我们“深入挖掘”一下看看这意味着什么
templatetypename T
constexpr bool Totally_ordered()
{
return Equality_comparableT() // has and ! Has_lessT() BooleanLess_resultT() Has_greaterT() BooleanGreater_resultT() Has_less_equalT() BooleanLess_equal_resultT() Has_greater_equalT() BooleanGreater_equal_resultT();
}
templatetypename T
constexpr bool Equality_comparable()
{
return Has_equalT() BooleanEqual_resultT() Has_not_equalT() BooleanNot_equal_resultT();
} 因此如果类型 T 是常规的并且提供通常的六个比较运算则它是有序的。比较运算必须提供可以转换为 bool 的结果。比较运算符也应该具有其正确的数学含义。C 标准精确地指定了这指的是什么(§31.2.2.1,§iso.25.4)。 Has_equals 是使用 enable_if 和 §28.4.4 中描述的技术实现的。 我将约束名称大写(例如Regular)尽管这样做违反了我的“内部风格”即将类型和模板名称大写但不将函数大写。但是概念比类型更为根本所以我觉得有必要强调它们。我还将它们保存在一个单独的命名空间(Estd)中希望非常相似的名称最终会成为语言或标准库的一部分。 进一步深入研究这组有用的概念我们可以定义Regular
templatetypename T
constexpr bool Regular()
{
return SemiregularT() Equality_comparableT();
} Equality_comparable 给出了 和 !。Semiregular是一种表达没有不寻常技术限制的类型概念的概念
templatetypename T
constexpr bool Semiregular()
{
return DestructibleT() Default_constructibleT() Move_constructibleT() Move_assignableT() Copy_constructibleT() Copy_assignableT();
} Semiregular 既可以移动也可以复制。这描述了大多数类型但也有一些无法复制的类型例如 unique_ptr。然而我不知道有哪些有用的类型可以复制但不能移动。既不能移动也不能复制的类型(例如 type_info (§22.5))非常罕见而且往往反映系统属性。 我们还可以使用函数约束检查例如
templatetypename C
ostream operator(ostream out, StringC s)
{
static_assert(StreamableC(),Strings character not streamable);
out ;
for (int i0; i!s.size(); i) cout s[i];
out ;
} String 的输出运算符 所需的概念 Streamable 要求其参数 C 提供输出运算符
templatetypename T
constexpr bool Streamable()
{
return Input_streamableT() Output_streamableT();
}
也就是说Streamable 测试我们是否可以对某种类型使用标准流 I/O(§4.3第 38 章)。 通过约束检查的方式模板检查概念有明显的弱点
• 约束检查位于定义中但它们实际上属于声明。也就是说概念是抽象接口的一部分但约束检查只能在其实现中使用。
• 约束检查是约束检查模板实例化的一部分。因此检查可能比我们希望的晚发生。特别是我们希望编译器保证在第一次调用时完成约束检查但如果没有语言的变化这是不可能的。
• 我们可能会忘记插入约束检查(尤其是对于函数模板)。
• 编译器不会检查模板实现是否仅使用其概念中指定的属性。因此模板实现可能会通过约束检查但仍然无法进行类型检查。
• 我们没有以编译器可以理解的方式指定语义属性(例如我们使用注释)。 添加约束检查使模板参数的要求变得明确如果约束检查设计得当它会产生更易于理解的错误消息。如果我们忘记插入约束检查我们将回到模板实例化生成的代码的普通类型检查。这可能很不幸但并不糟糕。这些约束检查是一种使基于概念的设计检查更加健壮的技术而不是类型系统的组成部分。 如果我们愿意我们可以在几乎任何地方放置约束检查。例如为了保证针对特定概念检查特定类型我们可以在命名空间范围(例如全局范围)中放置约束检查。例如
static_assert(Orderedstd::string,std::string is not Ordered); //将成功
static_assert(OrderedStringchar,Stringchar is not Ordered); //将失败
第一个 static_assert 检查标准字符串是否有序(是的因为它提供了 、! 和 )。第二个检查我们的字符串是否有序(不是因为我“忘记”定义 )。使用这样的全局检查将独立于我们是否在程序中实际使用模板的具体特化来执行约束检查。根据我们的目标这可能是一个优点也可能是一个麻烦。这样的检查强制在程序中的特定点进行类型检查这通常有利于错误隔离。此外这样的检查可以帮助单元测试。但是对于使用多个库的程序显式检查很快就会变得难以管理。 类型具有Regular是一种理想状态。我们可以复制常规类型的对象将它们放入向量和数组中进行比较等。如果类型是Ordered的我们还可以在集合中使用它的对象对此类对象的序列进行排序等。因此我们回过头来改进我们的String使其是Ordered的。特别是我们添加 以提供字典顺序
templatetypename C
bool operator(const StringC s1, const StringC s2)
{
static_assert(OrderedC(),Strings character type not ordered);
bool eq true;
for (int i0; i!s1.size() i!s2.size(); i) {
if (s2[i]s1[i]) return false;
if (s1[i]s2[i]) eq false; // not s1s2
}
if (s2.size()s1.siz e()) return false; // s2 is shorter than s1
if (s1.size()s2.siz e() eq) return false; // s1s2
return true;
} 24.4.1 公理(Axioms) 就像在数学中一样公理是我们无法证明的东西。它是我们假设为真的东西。在模板参数要求的上下文中我们使用“公理”来指代语义属性。我们使用公理来表述类或算法对其输入集的假设。无论如何表达公理都表示算法或类对其参数的期望(假设)。我们通常无法测试公理是否适用于某种类型的值(这是我们将它们称为公理的原因之一)。此外公理只需要适用于算法实际使用的值。例如算法可以小心地避免取消引用空指针或复制浮点 NaN。如果是这样它可能具有要求指针可解引用和浮点值可复制的公理。或者可以用一般假设来编写公理即奇异值(例如NaN 和 nullptr)违反了某些先决条件因此不需要考虑它们。 C(目前)没有任何方式来表达公理但是对于概念我们可以使我们的概念的理念比设计文档中的注释或某些文本更具体一些。 考虑我们如何表达类型为常规(regular)的一些关键语义要求
templatetypename T
bool Copy_equality(T x) // 复制构造语义
{
return T{x}x; // 复制比较起来等于……的副本
}
templatetypename T
bool Copy_assign_equality(T x, T y) // 赋值语义
{
return (yx, yx); // 赋值的结果比较起来等于赋值源
}
换句话说复制操作会产生副本。
templatetypename T
bool Move_effect(T x, T y) // 移动的语义
{
return (xy ? T{std::move(x)}y) : true) can_destroy(y);
}
templatetypename T
bool Move_assign_effect(T x, T y, T z) // 移动赋值的语义
{
return (yz ? (xstd::move(y), xz)) : true) can_destroy(y);
} 换句话说移动操作产生的值与比较的移动操作源的值相等并且移动源可以销毁。 这些公理以可执行代码的形式表示。我们可能会用它们进行测试但最重要的是我们必须比简单地写评论更努力地思考才能表达它们。由此产生的公理比“普通英语”中的公理表述得更精确。基本上我们可以使用一阶谓词逻辑来表达这样的伪公理。
24.4.2 多参数概念(Multi-argument Concepts) 当查看单参数概念并将其应用于类型时看起来就像我们正在进行常规类型检查并且该概念是类型的类型。这是故事的一部分但只是一部分。通常我们发现参数类型之间的关系对于正确规范和使用至关重要。考虑标准库 find() 算法
templatetypename Iter, typename Val
Iter find(Iter b, Iter e, Val x);
Iter 模板参数必须是一个输入迭代器并且我们可以(相对)轻松地为该概念定义一个约束检查模板。 到目前为止一切都很好但 find() 严重依赖于将 x 与序列 [b:e) 的元素进行比较。我们需要指定比较是必需的也就是说我们需要声明 Val 和输入迭代器的值类型是相等可比较的。这需要 Equality_comparable 的双参数版本
templatetypename A, typename B
constexpr bool Equality_comparable(A a, B b)
{
return CommonT, U() Totally_orderedT() Totally_orderedU() Totally_orderedCommon_typeT,U() Has_lessT,U() BooleanLess_resultT,U() Has_lessU,T() BooleanLess_resultU,T() Has_greaterT,U() BooleanGreater_resultT,U() Has_greaterU,T() BooleanGreater_resultU,T() Has_less_equalT,U() BooleanLess_equal_resultT,U() Has_less_equalU,T() BooleanLess_equal_resultU,T() Has_greater_equalT,U() BooleanGreater_equal_resultT,U() Has_greater_equalU,T() BooleanGreater_equal_resultU,T();
}; 对于一个简单的概念来说这太冗长了。但是我想明确说明所有运算符及其使用的对称性而不是将复杂性埋在概括中。
鉴于此我们定义find()
templatetypename Iter, typename Val
Iter find(Iter b, Iter e, Val x)
{
static_assert(Input_iteratorIter(),find() requires an input iterator);
static_assert(Equality_comparableValue_typeIter,Val(),
find()s iterator and value arguments must match);
while (b!e) {
if (∗bx) return b;
b;
}
return b;
} 多参数概念在指定通用算法时特别常见且实用。这也是您发现最多概念和最需要指定新概念的领域(而不是从常用概念目录中挑选“标准概念”)。明确定义的类型之间的差异似乎比算法对其参数的要求之间的差异更为有限。
24.4.3 值概念(Value Concepts)
概念可以表达对一组模板参数的任意(语法)要求。具体来说模板参数可以是整数值因此概念可以采用整数参数。例如我们可以编写约束检查来测试值模板参数是否很小
templateint N
constexpr bool Small_size()
{
return N8;
}
一个更现实的例子是对于一个概念来说数值参数只是众多参数之一。例如
constexpr int stack_limit 2048;
templatetypename T,int N
constexpr bool Stackable() // T 是常规的并且 T 的 N 个元素可以放在小堆栈上
{
return RegularT() sizeof(T)∗Nstack_limit;
}
这实现了“足够小以至于可以分配到堆栈”的概念。它可以像这样使用
templatetypename T, int N
struct Buffer {
// ...
};
templatetypename T, int N
void fct()
{
static_assert(StackableT,N(),fct() buffer wont fit on stack);
BufferT,N buf;
// ...
} 与类型的基本概念相比值概念往往较小且临时。
24.4.4 约束检查(Constraints Checks) 本书中使用的约束检查可以在本书的支持网站上找到。它们不是标准的一部分我希望将来它们会被适当的语言机制取代。但是它们对于思考模板和类型设计很实用并反映了标准库中的事实概念。它们应该放在单独的命名空间中以避免干扰可能的未来语言功能和概念理念的替代实现。我使用命名空间 Estd但这可能是一个别名(§14.4.2)。以下是一些您可能会觉得有用的约束检查
• Input_iteratorXX 是一个迭代器我们只能使用它一次来遍历一个序列(使用向前 )每个元素只读一次。
• Output_iteratorXX 是一个迭代器我们只能使用它一次来遍历一个序列(使用向前 )每个元素只写一次。
• Forward_iteratorXX 是一个迭代器我们可以使用它来遍历一个序列(使用向前 )。这是单链表(例如forward_list)自然支持的。
• Bidirectional_iteratorXX 是一个迭代器我们既可以向前移动(使用 )也可以向后移动(使用−−)。这是双链表(例如list)自然支持的。
• Random_access_iteratorXX 是一个迭代器我们可以使用它来遍历一个序列(向前和向后)并使用下标随机访问元素并使用 和 − 定位。这是数组自然支持的。
• Equality_comparableX,Y可以使用 和 ! 将 X 与 Y 进行比较。
• Totally_orderedX,YX 和 Y 是 Equality_comparable可以使用 、、 和 将 X 与 Y 进行比较。
• SemiregularXX 可以复制、默认构造、在免费存储中分配并且没有令人讨厌的技术限制。
• RegularXX 是 Semiregular 的可以使用相等性进行比较。标准库容器要求其元素是规则的。
• OrderedXX 是规则的和 Totally_ordered。标准库关联容器要求其元素按顺序排列除非您明确提供比较操作。
• AssignableX,Y可以使用 将 Y 分配给 X。
• PredicateF,X可以为 X 调用 F 以产生布尔值。
• StreamableX可以使用 iostream 读取和写入 X。
• MovableX可以移动 X也就是说它具有移动构造函数和移动赋值。此外X 是可寻址和可破坏的。
• CopyableXX 是可移动的也可以复制。
• ConvertibleX,Y可以隐式将 X 转换为 Y。
• CommonX,Y可以明确地将 X 和 Y 转换为称为 Common_typeX,Y 的通用类型。这是操作数与?: 兼容性的语言规则的形式化(§11.1.3)。例如Common_typeBase∗,Derived∗ 是 Base∗而 Common_typeint,long 是 long。
• RangeX可由 range-for(§9.5.1)使用的 X即 X 必须提供成员 x.begin() 和 x.end()或非成员等价项 begin(x) 和 end(x)并满足所需的语义。 显然这些定义是非正式的。在大多数情况下这些概念基于标准库类型谓词(§35.4.1)而 ISO C 标准提供了正式定义(例如§iso.17.6.3)。
24.4.5 模板定义检查(Template Definition Checking) 约束检查模板确保类型提供概念所需的属性。如果模板的实现实际上使用的属性多于其概念保证的属性我们可能会得到类型错误。例如标准库 find() 需要一对输入迭代器作为参数但我们可能(不谨慎地)将其定义为
templatetypename Iter, typename Val
Iter find(Iter b, Iter e, Val x)
{
static_assert(Input_iteratorIter(),find(): Iter is not a Forward iterator);
static_assert(Equality_comparableValue_typeIter,Val),
find(): value type doesnt match iterator);
while (b!e) {
if (∗bx) return b;
b b1; //note: not b
}
return b;
}
现在除非 b 是随机访问迭代器(而不仅仅是约束检查确保的前向迭代器)否则 b1 是错误的。但是约束检查并不能帮助我们检测该问题。例如
void f(listint lst, vectorstring vs)
{
auto p find(lst.begin(),lst.end(),1209); // 错 : list 未提供
auto q find(vs.begin(),vs.end(),Cambridge); // OK: vector 提供
// ...
} 对列表的 find() 调用将会失败(因为 没有为列表提供的前向迭代器定义)而对向量的调用将会成功(因为 b1 对于 vectorstring::iterator 来说是可以的。 约束检查主要为模板用户提供服务根据模板的要求检查实际模板参数。另一方面约束检查对模板编写者没有帮助因为他们希望确保实现不使用概念中指定的任何属性。理想情况下类型系统会确保这一点但这需要未来的语言特性。那么我们如何测试参数化类或泛型算法的实现呢 概念提供了强有力的指导方针实现不应使用概念未指定的参数的属性因此我们应该使用提供实现概念所指定的属性的参数来测试实现并且只使用那些属性。这种类型有时被称为原型。 因此对于 find() 示例我们查看 Forward_iterator 和 Equality_comparable或者查看标准对前向迭代器和相等可比较概念的定义(§iso.17.6.3.1,§iso.24.2.5)。然后我们决定我们需要一个至少提供以下内容的 Iterator 类型
• 默认构造函数
• 复制构造函数和复制赋值
• 运算符 和 !
• 前缀运算符
• 类型 Value_typeIterator
• 前缀运算符 ∗
• 能够将 ∗ 的结果分配给 Value_typeIterator
• 能够将 Value_typeIterator 分配给 ∗ 的结果
这比标准库的前向迭代器略微简化但对于 find() 来说已经足够了。通过查看概念来构建该列表很容易。 给定此列表我们需要查找或定义仅提供所需功能的类型。对于 find() 所需的前向迭代器标准库 forward_list 完全符合要求。这是因为“前向迭代器”被定义为表达允许我们迭代单链表的想法。一种流行类型是流行概念的原型并不罕见。如果我们决定使用现有类型我们必须小心不要选择比所需更灵活的类型。例如测试算法(如 find())时典型的错误是使用向量。然而使向量如此流行的通用性和灵活性使其无法用作许多简单算法的原型。 如果找不到符合我们需求的现有类型我们必须自己定义一个。这是通过查看需求列表并定义合适的成员来完成的
templatetypename Val
struct Forward { // for checking find()
Forward();
Forward(const Forward);
Forward operator(const Forward);
bool operator(const Forward);
bool operator!(const Forward);
void operator();
Val operator∗(); // 简化: 不处理 Val 的代理
};
templatetypename Val
using Value_typeForwardVal Val; // 简化; 见 §28.2.4
void f()
{
Forwardint p find(Forwardint{},Forwardint{},7);
} 在这个级别的测试中我们不需要检查这些操作是否真正实现了正确的语义。我们只需检查模板实现是否不依赖于它不应该依赖的属性。 在这里我通过不引入 Val 参数的原型来简化测试。相反我只是使用了 int。测试 Val 原型和 Iter 原型之间的非平凡转换将需要做更多的工作而且很可能不是特别有用。
编写一个测试工具来检查 find() 是否针对 std::forward_list 或 X 实现并非易事但这并不是泛型算法设计者面临的最困难的任务之一。使用一组相对较小且明确指定的概念可以使任务易于管理。测试可以且应该完全在编译时进行。
请注意这种简单的规范和检查策略导致 find() 要求其迭代器参数具有 Value_type 类型函数(§28.2)。这允许将指针用作迭代器。对于许多模板参数来说重要的是可以使用内置类型以及用户定义类型(§1.2.2,§25.2.1)。
24.5 建议(Advice)
[1] 模板可以传递参数类型而不会丢失信息§24.1。
[2] 模板为编译时编程提供了一种通用机制§24.1。
[3] 模板提供编译时“鸭子类型”§24.1。
[4] 通过从具体示例中“提取”来设计通用算法§24.2。
[5] 通过以概念的形式指定模板参数要求来概括算法§24.3。
[6] 不要给常规符号赋予非常规含义§24.3。
[7] 使用概念作为设计工具§24.3。
[8] 通过使用通用和常规模板参数要求力求实现算法和参数类型之间的“插件兼容性”§24.3。
[9] 通过最小化算法对其模板参数的要求来发现概念然后进行概括以供更广泛使用§24.3.1。
[10] 概念不仅仅是对算法特定实现需求的描述§24.3.1。
[11] 如果可能请从众所周知的概念列表中选择一个概念§24.3.1§24.4.4。
[12] 模板参数的默认概念是 Regular§24.3.1。
[13] 并非所有模板参数类型都是 Regular§24.3.1。
[14] 概念需要语义方面它主要不是句法概念§24.3.1§24.3.2§24.4.1。
[15] 在代码中使概念具体化§24.4。
[16] 将概念表达为编译时谓词(constexpr 函数)并使用static_assert() 或 enable_if 对其进行测试§24.4。
[17] 使用公理作为设计工具 §24.4.1.
[18] 使用公理作为测试的指南§24.4.1.
[19] 一些概念涉及两个或多个模板参数§24.4.2.
[20] 概念不仅仅是类型的类型§24.4.2.
[21] 概念可以涉及数值§24.4.3.
[22] 使用概念作为测试模板定义的指南§24.4.5. 内容来源
The C Programming Language 第4版作者 Bjarne Stroustrup
文章转载自： http://www.morning.blzrj.cn.gov.cn.blzrj.cn http://www.morning.hlxxl.cn.gov.cn.hlxxl.cn http://www.morning.pqkyx.cn.gov.cn.pqkyx.cn http://www.morning.tpyjr.cn.gov.cn.tpyjr.cn http://www.morning.mytmn.cn.gov.cn.mytmn.cn http://www.morning.rzscb.cn.gov.cn.rzscb.cn http://www.morning.mdfxn.cn.gov.cn.mdfxn.cn http://www.morning.kqxwm.cn.gov.cn.kqxwm.cn http://www.morning.jbshh.cn.gov.cn.jbshh.cn http://www.morning.qhkdt.cn.gov.cn.qhkdt.cn http://www.morning.kyjpg.cn.gov.cn.kyjpg.cn http://www.morning.kjyhh.cn.gov.cn.kjyhh.cn http://www.morning.ykwbx.cn.gov.cn.ykwbx.cn http://www.morning.pbtrx.cn.gov.cn.pbtrx.cn http://www.morning.rjmd.cn.gov.cn.rjmd.cn http://www.morning.ndrzq.cn.gov.cn.ndrzq.cn http://www.morning.rlbg.cn.gov.cn.rlbg.cn http://www.morning.jsxrm.cn.gov.cn.jsxrm.cn http://www.morning.clpfd.cn.gov.cn.clpfd.cn http://www.morning.mtsgx.cn.gov.cn.mtsgx.cn http://www.morning.grbp.cn.gov.cn.grbp.cn http://www.morning.glxdk.cn.gov.cn.glxdk.cn http://www.morning.wbysj.cn.gov.cn.wbysj.cn http://www.morning.snrbl.cn.gov.cn.snrbl.cn http://www.morning.tqklh.cn.gov.cn.tqklh.cn http://www.morning.dwkfx.cn.gov.cn.dwkfx.cn http://www.morning.zwtp.cn.gov.cn.zwtp.cn http://www.morning.ftmly.cn.gov.cn.ftmly.cn http://www.morning.xhhqd.cn.gov.cn.xhhqd.cn http://www.morning.gfkb.cn.gov.cn.gfkb.cn http://www.morning.ddfp.cn.gov.cn.ddfp.cn http://www.morning.rnkq.cn.gov.cn.rnkq.cn http://www.morning.dwyyf.cn.gov.cn.dwyyf.cn http://www.morning.gbpanel.com.gov.cn.gbpanel.com http://www.morning.msxhb.cn.gov.cn.msxhb.cn http://www.morning.ljmbd.cn.gov.cn.ljmbd.cn http://www.morning.tftw.cn.gov.cn.tftw.cn http://www.morning.qfrsm.cn.gov.cn.qfrsm.cn http://www.morning.qhvah.cn.gov.cn.qhvah.cn http://www.morning.czrcf.cn.gov.cn.czrcf.cn http://www.morning.hqrkq.cn.gov.cn.hqrkq.cn http://www.morning.mznqz.cn.gov.cn.mznqz.cn http://www.morning.mtrz.cn.gov.cn.mtrz.cn http://www.morning.jrlgz.cn.gov.cn.jrlgz.cn http://www.morning.xmrmk.cn.gov.cn.xmrmk.cn http://www.morning.slmbg.cn.gov.cn.slmbg.cn http://www.morning.qlrtd.cn.gov.cn.qlrtd.cn http://www.morning.dbtdy.cn.gov.cn.dbtdy.cn http://www.morning.sbqrm.cn.gov.cn.sbqrm.cn http://www.morning.errnull.com.gov.cn.errnull.com http://www.morning.bwrbm.cn.gov.cn.bwrbm.cn http://www.morning.kryxk.cn.gov.cn.kryxk.cn http://www.morning.fgxws.cn.gov.cn.fgxws.cn http://www.morning.hbpjb.cn.gov.cn.hbpjb.cn http://www.morning.wnnts.cn.gov.cn.wnnts.cn http://www.morning.mxmzl.cn.gov.cn.mxmzl.cn http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.ghzfx.cn.gov.cn.ghzfx.cn http://www.morning.wbqt.cn.gov.cn.wbqt.cn http://www.morning.tdhxp.cn.gov.cn.tdhxp.cn http://www.morning.xxwl1.com.gov.cn.xxwl1.com http://www.morning.tkgxg.cn.gov.cn.tkgxg.cn http://www.morning.hffpy.cn.gov.cn.hffpy.cn http://www.morning.qgqck.cn.gov.cn.qgqck.cn http://www.morning.zqbrw.cn.gov.cn.zqbrw.cn http://www.morning.lxctl.cn.gov.cn.lxctl.cn http://www.morning.fhxrb.cn.gov.cn.fhxrb.cn http://www.morning.ggxbyhk.cn.gov.cn.ggxbyhk.cn http://www.morning.ckhry.cn.gov.cn.ckhry.cn http://www.morning.fldsb.cn.gov.cn.fldsb.cn http://www.morning.yrbp.cn.gov.cn.yrbp.cn http://www.morning.rqnhf.cn.gov.cn.rqnhf.cn http://www.morning.hpprx.cn.gov.cn.hpprx.cn http://www.morning.ydhmt.cn.gov.cn.ydhmt.cn http://www.morning.khpgd.cn.gov.cn.khpgd.cn http://www.morning.dyxzn.cn.gov.cn.dyxzn.cn http://www.morning.qmzwl.cn.gov.cn.qmzwl.cn http://www.morning.ksgjy.cn.gov.cn.ksgjy.cn http://www.morning.lxkhx.cn.gov.cn.lxkhx.cn http://www.morning.jgttx.cn.gov.cn.jgttx.cn
