C++編程語言：抽象機制：泛型編程(Bjarne Stroustrup)

泛型編程(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、complex<double> 還是矩陣。它關心的是它們可以使用 + 運算符相加。使用類型作為模板參數并不意味著或要求使用類層級結構或任何形式的運行時對象類型的自我識別。這在邏輯上是令人滿意的，并且對于高性能應用程序至關重要。

本節重點介紹泛型編程的兩個方面：

? 提升(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; i<n; ++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代碼:

template<typename 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 = sum<double?>(ad,ad+4);

要使用手工制作的單鏈表，我們需要為其提供一個迭代器。給定幾個操作，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 = sum<int?>(lst,end(lst));

}

我使用 nullptr 作為結束迭代器。我使用顯式模板參數(此處為 <int>)來允許調用者指定要用于累加器變量的類型。

??? 到目前為止，我們所擁有的代碼比許多現實世界的代碼更通用。例如，sum() 適用于浮點數列表(所有精度)、整數數組(所有范圍)以及許多其他類型，例如 vector<char>。重要的是，sum()與我們開始時手工編寫的函數一樣高效。我們不想以犧牲性能為代價來實現通用性。

??? 經驗豐富的程序員會注意到 sum() 可以進一步推廣。特別是，使用額外的模板參數很不方便，而且我們需要初始值 0。我們可以解決這個問題，方法是讓調用者提供一個初始值，然后推斷 Val：

template<typename 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,ad+4,0.0); // 按 double 疊加

double s2 = accumulate(ad,ad+4,0); // 按 int 疊加

但為什么是 +？有時我們想將元素相乘。事實上，似乎有很多操作我們可能想應用于序列的元素。這導致了進一步的概括：

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;

}

我們現在使用參數 op 將元素值與累加器組合起來。例如：

double ad[] = {1,2,3,4};

double s1 = accumulate(ad,ad+4,0.0,std::plus<double>); // 如前

double s2 = accumulate(ad,ad+4,1.0,std::multiply<double>);

標準庫提供常用操作，例如加法和乘法，作為可用作參數的函數對象。在這里，我們看到了讓調用者提供初始值的實用性：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 類模板：

template<typename C>

class String {

// ...

};

類型 X 需要滿足什么要求才能用作 String 的參數：String<X>？更一般地說，在這樣的字符串類中，要成為字符需要什么？經驗豐富的設計師會對這個問題有少數可能的答案，并根據這些答案開始設計。然而，讓我們考慮一下如何從第一原理來回答這個問題。我們進行三階段分析：

[1] 首先，我們查看我們的(初始)實現，并從其參數類型(以及這些操作的含義)中確定它使用哪些屬性(操作、函數、成員類型等)。結果列表是該特定模板實現的最低要求。

[2] 接下來，我們查看合理的替代模板實現，并列出它們對模板參數的要求。這樣做，我們可能會決定對模板參數提出更多或更嚴格的要求，以允許替代實現。或者，我們可能決定選擇一種要求更少和/或更簡單的實現。

[3] 最后，我們查看所需屬性的結果列表(或列表)，并將其與我們用于其他模板的需求(概念)列表進行比較。我們嘗試找到簡單的、最好是通用的概念，這些概念可以表達原本會有很多長列表的需求。這里的目的是讓我們的設計受益于分類的一般工作。產生的概念更容易給出有意義的名稱，也更容易記住。他們還應通過將概念變化限制在必要的范圍內來最大限度地提高模板和類型的互操作性。

前兩個步驟與我們將具體算法概括(“提升”)為通用算法(§24.2)的方式非常相似。最后一步抵制了為每個算法提供一組與其實現完全匹配的參數要求的誘惑。這樣的需求列表過于專業化且不穩定：對實現的每次更改都意味著對作為算法接口一部分記錄的需求進行更改。

對于 String<C>，首先考慮 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 類型不能用作模板參數。例如，String<const char> 不能保證工作。在這種情況下，這沒問題，就像大多數情況一樣。賦值意味著算法可以使用其參數類型的臨時變量，創建參數類型對象的容器等。這并不意味著我們不能使用 const 來指定接口。例如：

template<typename T>

bool operator==(const String<T>& s1, const String<T>& 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;

}

??? 對于 String<X>，我們要求 X 類型的對象可以復制。另外，通過其參數類型中的 const，operator==() 承諾不會寫入 X 元素。

我們是否應該要求元素類型 C 進行移動？畢竟，我們為 String<C> 提供了移動操作。我們可以這樣做，但這不是必需的：我們對 C 的操作可以通過復制來處理，如果某些復制被隱式轉換為移動(例如，當我們返回 C 時)，那就更好了。特別是，可能很重要的示例(例如 String<String<char>>)將正常工作(正確且高效)，而無需將移動操作添加到要求中。

到目前為止，一切都很好，但最后一個要求( 我們可以使用 >> 和 << 讀取和寫入 C )似乎有點多余。我們真的可以讀取和寫入每種類型的字符串嗎？也許這樣說會更好：如果我們讀取和寫入 String<X>，那么 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 提供幾個有用的操作。事實上，我們對模板參數類型的要求越多，模板實現者完成各種任務就越容易，模板可以為其用戶提供的服務就越多。另一方面，重要的是不要用很少使用且僅由特定操作使用的要求來加載模板：每個要求都會給參數類型的實現者帶來負擔，并限制可用作參數的類型集。因此，對于 String<X>，我們需要：

? Ordered<X>

? 如果我們使用 String<X> 的 >> 和 <<，則 X 的 >> 和 <<(僅此而已)

? 如果我們定義并使用來自 X 的轉換操作，則可轉換為整數(僅此而已)

??? 到目前為止，我們已經從句法屬性的角度表達了對 String 字符類型的要求，例如 X 必須提供復制操作、== 和 <。此外，我們必須要求這些操作具有正確的語義；例如，復制操作進行復制，==(相等)比較相等，<(小于) 提供排序。通常，這種語義涉及操作之間的關系。例如，對于標準庫，我們有(§31.2.2.1)：

? 副本的結果與原始值相等 (a==b意味著 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”是一個非常籠統的思想，在本質上與模板沒有任何關系。甚至 K&R C [Kernighan,1978] 也有概念，即有符號整數類型是編程語言對內存中整數概念的概括。我們對模板參數的要求也是概念(無論如何表達)，因此與概念相關的大多數有趣問題都出現在模板的上下文中。(譯注：此段指的概念是指對模板參數施加的基本要求。)

??? 我認為概念是精心設計的實體，反映了應用領域的基本屬性。因此，應該只有少數概念可以作為算法和類型設計的指導方針。這與物理插件和插座類似；我們希望用最少的插頭和插座簡化我們的生活，并降低設計和建造成本。這種理想可能與每個單獨的通用算法(§24.2)和每個單獨的參數化類的最低要求理想相沖突。此外，這種理想可能與為類提供絕對最小接口的理想相沖突(§16.2.3)，甚至與一些程序員認為他們有權“完全按照自己喜歡的方式”編寫代碼相沖突。然而，如果不付出努力和某種形式的標準，我們就無法獲得插件兼容性。

??? 我對概念的標準非常高：我需要通用性、一定的穩定性、跨多種算法的可用性、語義一致性等等。事實上，根據我的標準，我們希望模板參數的許多簡單約束都不符合概念的條件(譯注：指通用性的要求)。我認為這是不可避免的。特別是，我們編寫的許多模板并不反映通用算法或廣泛適用的類型。相反，它們是實現細節，它們的參數只需反映模板的必要細節，該模板的目的在于在某事物的單一實現中一次性使用。我稱對此類模板參數的要求為約束或(如果必須)臨時概念(譯注：不具有通用性的模板參數稱為約束或臨時概念)。看待約束的一種方法是將它們視為接口的不完整(部分)規范。通常，部分規范很有用，而且比沒有規范要好得多。

??? 舉個例子，考慮一個用于試驗平衡二叉樹平衡策略的庫。該樹將 Balancer 作為模板參數：

template<typename Node, typename Balance>

struct node_base { // 平衡二叉樹基類

// ...

}

Balancer只是一個提供三種節點操作的類。例如：

struct Red_black_balance {

// ...

template<typename Node> static void add_fixup(Node? x);

template<typename Node> static void touch(Node? x);

template<typename 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；它的字符類型參數應該是有序的：

template<typename C>

class String {

static_assert(Ordered<C>(),"String's character type is not ordered");

// ...

};

??? 當為類型 X 實例化 String<X> 時，編譯器將執行static_assert。如果 Ordered<X>() 返回 true，則編譯將繼續進行，并生成與無斷言時完全相同的代碼。否則，將生成錯誤消息。

??? 乍一看，這似乎是一種相當合理的解決方法。我寧愿說：

template<Ordered C>

class String {

// ...

};

不過，那是未來的事，所以讓我們看看如何定義謂詞 Ordered<T>()：

template<typename T>

constexpr bool Ordered()

{

return Regular<T>() && Totally_ordered<T>();

}

也就是說，如果一個類型既是Regular類型又是Totally_ordered類型，那么它就是Ordered類型。讓我們“深入挖掘”一下，看看這意味著什么：

template<typename T>

constexpr bool Totally_ordered()

{

return Equality_comparable<T>() // has == and !=

&& Has_less<T>()&& Boolean<Less_result<T>>()

&& Has_greater<T>() && Boolean<Greater_result<T>>()

&& Has_less_equal<T>() && Boolean<Less_equal_result<T>>()

&& Has_greater_equal<T>() && Boolean<Greater_equal_result<T>>();

}

template<typename T>

constexpr bool Equality_comparable()

{

return Has_equal<T>() && Boolean<Equal_result<T>>()

&& Has_not_equal<T>() && Boolean<Not_equal_result<T>>();

}

因此，如果類型 T 是常規的并且提供通常的六個比較運算，則它是有序的。比較運算必須提供可以轉換為 bool 的結果。比較運算符也應該具有其正確的數學含義。C++ 標準精確地指定了這指的是什么(§31.2.2.1,§iso.25.4)。

??? Has_equals 是使用 enable_if 和 §28.4.4 中描述的技術實現的。

??? 我將約束名稱大寫(例如，Regular)，盡管這樣做違反了我的“內部風格”，即將類型和模板名稱大寫，但不將函數大寫。但是，概念比類型更為根本，所以我覺得有必要強調它們。我還將它們保存在一個單獨的命名空間(Estd)中，希望非常相似的名稱最終會成為語言或標準庫的一部分。

??? 進一步深入研究這組有用的概念，我們可以定義Regular：

template<typename T>

constexpr bool Regular()

{

return Semiregular<T>() && Equality_comparable<T>();

}

??? Equality_comparable 給出了 == 和 !=。Semiregular是一種表達沒有不尋常技術限制的類型概念的概念：

template<typename T>

constexpr bool Semiregular()

{

return Destructible<T>()

&& Default_constructible<T>()

&& Move_constructible<T>()

&& Move_assignable<T>()

&& Copy_constructible<T>()

&& Copy_assignable<T>();

}

Semiregular 既可以移動也可以復制。這描述了大多數類型，但也有一些無法復制的類型，例如 unique_ptr。然而，我不知道有哪些有用的類型可以復制但不能移動。既不能移動也不能復制的類型(例如 type_info (§22.5))非常罕見，而且往往反映系統屬性。

??? 我們還可以使用函數約束檢查；例如：

template<typename C>

ostream& operator<<(ostream& out, String<C>& s)

{

static_assert(Streamable<C>(),"String's character not streamable");

out << '"';

for (int i=0; i!=s.size(); ++i) cout << s[i];

out << '"';

}

String 的輸出運算符 << 所需的概念 Streamable 要求其參數 C 提供輸出運算符 << ：

template<typename T>

constexpr bool Streamable()

{

return Input_streamable<T>() && Output_streamable<T>();

}

也就是說，Streamable 測試我們是否可以對某種類型使用標準流 I/O(§4.3，第 38 章)。

??? 通過約束檢查的方式模板檢查概念有明顯的弱點：

? 約束檢查位于定義中，但它們實際上屬于聲明。也就是說，概念是抽象接口的一部分，但約束檢查只能在其實現中使用。

? 約束檢查是約束檢查模板實例化的一部分。因此，檢查可能比我們希望的晚發生。特別是，我們希望編譯器保證在第一次調用時完成約束檢查，但如果沒有語言的變化，這是不可能的。

? 我們可能會忘記插入約束檢查(尤其是對于函數模板)。

? 編譯器不會檢查模板實現是否僅使用其概念中指定的屬性。因此，模板實現可能會通過約束檢查，但仍然無法進行類型檢查。

? 我們沒有以編譯器可以理解的方式指定語義屬性(例如，我們使用注釋)。

??? 添加約束檢查使模板參數的要求變得明確，如果約束檢查設計得當，它會產生更易于理解的錯誤消息。如果我們忘記插入約束檢查，我們將回到模板實例化生成的代碼的普通類型檢查。這可能很不幸，但并不糟糕。這些約束檢查是一種使基于概念的設計檢查更加健壯的技術，而不是類型系統的組成部分。

??? 如果我們愿意，我們可以在幾乎任何地方放置約束檢查。例如，為了保證針對特定概念檢查特定類型，我們可以在命名空間范圍(例如全局范圍)中放置約束檢查。例如：

static_assert(Ordered<std::string>,"std::string is not Ordered"); //將成功

static_assert(Ordered<String<char>>,"String<char> is not Ordered"); //將失敗

第一個 static_assert 檢查標準字符串是否有序(是的，因為它提供了 ==、!= 和 <)。第二個檢查我們的字符串是否有序(不是，因為我“忘記”定義 < )。使用這樣的全局檢查將獨立于我們是否在程序中實際使用模板的具體特化來執行約束檢查。根據我們的目標，這可能是一個優點，也可能是一個麻煩。這樣的檢查強制在程序中的特定點進行類型檢查；這通常有利于錯誤隔離。此外，這樣的檢查可以幫助單元測試。但是，對于使用多個庫的程序，顯式檢查很快就會變得難以管理。

??? 類型具有Regular是一種理想狀態。我們可以復制常規類型的對象，將它們放入向量和數組中，進行比較等。如果類型是Ordered的，我們還可以在集合中使用它的對象，對此類對象的序列進行排序等。因此，我們回過頭來改進我們的String，使其是Ordered的。特別是，我們添加 < 以提供字典順序：

template<typename C>

bool operator<(const String<C>& s1, const String<C>& s2)

{

static_assert(Ordered<C>(),"String's character type not ordered");

bool eq = true;

for (int i=0; i!=s1.size() && i!=s2.size(); ++i) {

if (s2[i]<s1[i]) return false;

if (s1[i]<s2[i]) eq = false; // not s1==s2

}

if (s2.size()<s1.siz e()) return false; // s2 is shorter than s1

if (s1.size()==s2.siz e() && eq) return false; // s1==s2

return true;

}

24.4.1 ?公理(Axioms)

??? 就像在數學中一樣，公理是我們無法證明的東西。它是我們假設為真的東西。在模板參數要求的上下文中，我們使用“公理”來指代語義屬性。我們使用公理來表述類或算法對其輸入集的假設。無論如何表達，公理都表示算法或類對其參數的期望(假設)。我們通常無法測試公理是否適用于某種類型的值(這是我們將它們稱為公理的原因之一)。此外，公理只需要適用于算法實際使用的值。例如，算法可以小心地避免取消引用空指針或復制浮點 NaN。如果是這樣，它可能具有要求指針可解引用和浮點值可復制的公理。或者，可以用一般假設來編寫公理，即奇異值(例如，NaN 和 nullptr)違反了某些先決條件，因此不需要考慮它們。

??? C++(目前)沒有任何方式來表達公理，但是對于概念，我們可以使我們的概念的理念比設計文檔中的注釋或某些文本更具體一些。

??? 考慮我們如何表達類型為常規(regular)的一些關鍵語義要求：

template<typename T>

bool Copy_equality(T x) // 復制構造語義

{

return T{x}==x; // 復制比較起來等于……的副本

}

template<typename T>

bool Copy_assign_equality(T x, T& y) // 賦值語義

{

return (y=x, y==x); // 賦值的結果比較起來等于賦值源

}

換句話說，復制操作會產生副本。

template<typename T>

bool Move_effect(T x, T& y) // 移動的語義

{

return (x==y ? T{std::move(x)}==y) : true) && can_destroy(y);

}

template<typename T>

bool Move_assign_effect(T x, T& y, T& z) // 移動賦值的語義

{

return (y==z ? (x=std::move(y), x==z)) : true) && can_destroy(y);

}

換句話說，移動操作產生的值與比較的移動操作源的值相等，并且移動源可以銷毀。

??? 這些公理以可執行代碼的形式表示。我們可能會用它們進行測試，但最重要的是，我們必須比簡單地寫評論更努力地思考才能表達它們。由此產生的公理比“普通英語”中的公理表述得更精確。基本上，我們可以使用一階謂詞邏輯來表達這樣的偽公理。

24.4.2 ?多參數概念(Multi-argument Concepts)

??? 當查看單參數概念并將其應用于類型時，看起來就像我們正在進行常規類型檢查，并且該概念是類型的類型。這是故事的一部分，但只是一部分。通常，我們發現參數類型之間的關系對于正確規范和使用至關重要。考慮標準庫 find() 算法：

template<typename Iter, typename Val>

Iter find(Iter b, Iter e, Val x);

Iter 模板參數必須是一個輸入迭代器，并且我們可以(相對)輕松地為該概念定義一個約束檢查模板。

??? 到目前為止，一切都很好，但 find() 嚴重依賴于將 x 與序列 [b:e) 的元素進行比較。我們需要指定比較是必需的；也就是說，我們需要聲明 Val 和輸入迭代器的值類型是相等可比較的。這需要 Equality_comparable 的雙參數版本：

template<typename A, typename B>

constexpr bool Equality_comparable(A a, B b)

{

return Common<T, U>()

&& Totally_ordered<T>()

&& Totally_ordered<U>()

&& Totally_ordered<Common_type<T,U>>()

&& Has_less<T,U>() && Boolean<Less_result<T,U>>()

&& Has_less<U,T>() && Boolean<Less_result<U,T>>()

&& Has_greater<T,U>() && Boolean<Greater_result<T,U>>()

&& Has_greater<U,T>() && Boolean<Greater_result<U,T>>()

&& Has_less_equal<T,U>() && Boolean<Less_equal_result<T,U>>()

&& Has_less_equal<U,T>() && Boolean<Less_equal_result<U,T>>()

&& Has_greater_equal<T,U>() && Boolean<Greater_equal_result<T,U>>()

&& Has_greater_equal<U,T>() && Boolean<Greater_equal_result<U,T>>();

};

對于一個簡單的概念來說，這太冗長了。但是，我想明確說明所有運算符及其使用的對稱性，而不是將復雜性埋在概括中。

鑒于此，我們定義find() ：

template<typename Iter, typename Val>

Iter find(Iter b, Iter e, Val x)

{

static_assert(Input_iterator<Iter>(),"find() requires an input iterator");

static_assert(Equality_comparable<Value_type<Iter>,Val>(),

"find()'s iterator and value arguments must match");

while (b!=e) {

if (?b==x) return b;

++b;

}

return b;

}

多參數概念在指定通用算法時特別常見且實用。這也是您發現最多概念和最需要指定新概念的領域(而不是從常用概念目錄中挑選“標準概念”)。明確定義的類型之間的差異似乎比算法對其參數的要求之間的差異更為有限。

24.4.3 ?值概念(Value Concepts)

概念可以表達對一組模板參數的任意(語法)要求。具體來說，模板參數可以是整數值，因此概念可以采用整數參數。例如，我們可以編寫約束檢查來測試值模板參數是否很小：

template<int N>

constexpr bool Small_size()

{

return N<=8;

}

一個更現實的例子是，對于一個概念來說，數值參數只是眾多參數之一。例如：

constexpr int stack_limit = 2048;

template<typename T,int N>

constexpr bool Stackable() // T 是常規的，并且 T 的 N 個元素可以放在小堆棧上

{

return Regular<T>() && sizeof(T)?N<=stack_limit;

}

這實現了“足夠小以至于可以分配到堆棧”的概念。它可以像這樣使用：

template<typename T, int N>

struct Buffer {

// ...

};

template<typename T, int N>

void fct()

{

static_assert(Stackable<T,N>(),"fct() buffer won't fit on stack");

Buffer<T,N> buf;

// ...

}

與類型的基本概念相比，值概念往往較小且臨時。

24.4.4 ?約束檢查(Constraints Checks)

??? 本書中使用的約束檢查可以在本書的支持網站上找到。它們不是標準的一部分，我希望將來它們會被適當的語言機制取代。但是，它們對于思考模板和類型設計很實用，并反映了標準庫中的事實概念。它們應該放在單獨的命名空間中，以避免干擾可能的未來語言功能和概念理念的替代實現。我使用命名空間 Estd，但這可能是一個別名(§14.4.2)。以下是一些您可能會覺得有用的約束檢查：

? Input_iterator<X>：X 是一個迭代器，我們只能使用它一次來遍歷一個序列(使用向前 ++)，每個元素只讀一次。

? Output_iterator<X>：X 是一個迭代器，我們只能使用它一次來遍歷一個序列(使用向前 ++)，每個元素只寫一次。

? Forward_iterator<X>：X 是一個迭代器，我們可以使用它來遍歷一個序列(使用向前 ++)。這是單鏈表(例如，forward_list)自然支持的。

? Bidirectional_iterator<X>：X 是一個迭代器，我們既可以向前移動(使用 ++)，也可以向后移動(使用??)。這是雙鏈表(例如，list)自然支持的。

? Random_access_iterator<X>：X 是一個迭代器，我們可以使用它來遍歷一個序列(向前和向后)，并使用下標隨機訪問元素，并使用 += 和 ?= 定位。這是數組自然支持的。

? Equality_comparable<X,Y>：可以使用 == 和 != 將 X 與 Y 進行比較。

? Totally_ordered<X,Y>：X 和 Y 是 Equality_comparable，可以使用 <、<=、> 和 >= 將 X 與 Y 進行比較。

? Semiregular<X>：X 可以復制、默認構造、在免費存儲中分配，并且沒有令人討厭的技術限制。

? Regular<X>：X 是 Semiregular 的，可以使用相等性進行比較。標準庫容器要求其元素是規則的。

? Ordered<X>：X 是規則的和 Totally_ordered。標準庫關聯容器要求其元素按順序排列，除非您明確提供比較操作。

? Assignable<X,Y>：可以使用 = 將 Y 分配給 X。

? Predicate<F,X>：可以為 X 調用 F 以產生布爾值。

? Streamable<X>：可以使用 iostream 讀取和寫入 X。

? Movable<X>：可以移動 X；也就是說，它具有移動構造函數和移動賦值。此外，X 是可尋址和可破壞的。

? Copyable<X>：X 是可移動的，也可以復制。

? Convertible<X,Y>：可以隱式將 X 轉換為 Y。

? Common<X,Y>：可以明確地將 X 和 Y 轉換為稱為 Common_type<X,Y> 的通用類型。這是操作數與?: 兼容性的語言規則的形式化(§11.1.3)。例如，Common_type<Base?,Derived?> 是 Base?，而 Common_type<int,long> 是 long。

? Range<X>：可由 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() 需要一對輸入迭代器作為參數，但我們可能(不謹慎地)將其定義為：

template<typename Iter, typename Val>

Iter find(Iter b, Iter e, Val x)

{

static_assert(Input_iterator<Iter>(),"find(): Iter is not a Forward iterator");

static_assert(Equality_comparable<Value_type<Iter>,Val>),

"find(): value type doesn't match iterator");

while (b!=e) {

if (?b==x) return b;

b =b+1; //note: not ++b

}

return b;

}

現在，除非 b 是隨機訪問迭代器(而不僅僅是約束檢查確保的前向迭代器)，否則 b+1 是錯誤的。但是，約束檢查并不能幫助我們檢測該問題。例如：

void f(list<int>& lst, vector<string>& vs)

{

auto p = find(lst.begin(),lst.end(),1209); // 錯 : list 未提供 +

auto q = find(vs.begin(),vs.end(),"Cambridge"); // OK: vector 提供 +

// ...

}

??? 對列表的 find() 調用將會失敗(因為 + 沒有為列表提供的前向迭代器定義)，而對向量的調用將會成功(因為 b+1 對于 vector<string>::iterator 來說是可以的）。

??? 約束檢查主要為模板用戶提供服務：根據模板的要求檢查實際模板參數。另一方面，約束檢查對模板編寫者沒有幫助，因為他們希望確保實現不使用概念中指定的任何屬性。理想情況下，類型系統會確保這一點，但這需要未來的語言特性。那么，我們如何測試參數化類或泛型算法的實現呢？

??? 概念提供了強有力的指導方針：實現不應使用概念未指定的參數的屬性，因此我們應該使用提供實現概念所指定的屬性的參數來測試實現，并且只使用那些屬性。這種類型有時被稱為原型。

??? 因此，對于 find() 示例，我們查看 Forward_iterator 和 Equality_comparable，或者查看標準對前向迭代器和相等可比較概念的定義(§iso.17.6.3.1,§iso.24.2.5)。然后，我們決定我們需要一個至少提供以下內容的 Iterator 類型：

? 默認構造函數

? 復制構造函數和復制賦值

? 運算符 == 和 !=

? 前綴運算符 ++

? 類型 Value_type<Iterator>

? 前綴運算符 ?

? 能夠將 ? 的結果分配給 Value_type<Iterator>

? 能夠將 Value_type<Iterator> 分配給 ? 的結果

這比標準庫的前向迭代器略微簡化，但對于 find() 來說已經足夠了。通過查看概念來構建該列表很容易。

??? 給定此列表，我們需要查找或定義僅提供所需功能的類型。對于 find() 所需的前向迭代器，標準庫 forward_list 完全符合要求。這是因為“前向迭代器”被定義為表達允許我們迭代單鏈表的想法。一種流行類型是流行概念的原型并不罕見。如果我們決定使用現有類型，我們必須小心，不要選擇比所需更靈活的類型。例如，測試算法(如 find())時典型的錯誤是使用向量。然而，使向量如此流行的通用性和靈活性使其無法用作許多簡單算法的原型。

??? 如果找不到符合我們需求的現有類型，我們必須自己定義一個。這是通過查看需求列表并定義合適的成員來完成的：

template<typename 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 的代理

};

template<typename Val>