第10章 泛型算法------(持續(xù)更新)

順序容器只定義了很少的操作:在多數情況下，我們可以添加和刪除元素訪問首尾元素、確定容器是否為空以及獲得指向首元素或尾元素之后位置的迭代器。

我們可以想象用戶可能還希望做其他很多有用的操作:查找特定元素、替換或刪除一個特定值、重排元素順序等。

標準庫并未給每個容器都定義成員函數來實現這些操作，而是定義了一組泛型算法( generic algorithm):稱它們?yōu)椤八惴ā保且驗樗鼈儗崿F了一些經典算法的公共接口，如排序和搜索;稱它們是“泛型的”，是因為它們可以用于不同類型的元素和多種容器類型(不僅包括標準庫類型，如vector或list，還包括內置的數組類型)，以及我們將看到的，還能用于其他類型的序列。

關系圖：

10.1、概述

大多數算法都定義在頭文件algorithm中。標準庫還在頭文件 numeric 中定義了一組數值泛型算法。

一般情況下，這些算法并不直接操作容器，而是遍歷由兩個迭代器指定的一個元素范圍來進行操作。通常情況下，算法遍歷范圍，對其中每個元素進行一些處理。

例如，假定我們有一個int的vector，希望知道vector中是否包含一-個特定值?；卮疬@個問題最方便的方法是調用標準庫算法find:

int val = 42; 	//我們將查找的值
//如果在vec中找到想要的元素，則返回結果指向它，否則返回結果為vec.cend()
auto result = find (vec.cbegin(), vec.cend(), val);
//報告結果
cout << "The value " << val <<(result == vec.cend() ? " is not present" : " is present") 
	 << endl;

例如，可以用find在一個string 的list中查找一個給定值:

string val = "a value" ; //我們要查找的值
//此調用在list中查找string 元素
auto result = find(lst.cbegin(), lst.cend(), val);

類似的，由于指針就像內置數組上的迭代器一樣，我們可以用find在數組中查找值:

int ia[] = {27,210,12,47,109,83};
int val = 83;
int* result = find(begin(ia), end (ia), val);

算法如何工作

為了弄清這些算法如何用于不同類型的容器，讓我們更近地觀察一下find。 find的工作是在一個未排序的元素序列中查找一個特定元素。概念上，find應執(zhí)行如下步驟:

1. 訪問序列中的首元素。
2. 比較此元素與我們要查找的值。
3. 如果此元素與我們要查找的值匹配，find返回標識此元素的值。
4. 否則，find前進到下一個元素，重復執(zhí)行步驟2和3。
5. 如果到達序列尾，find應停止。
6. 如果find 到達序列末尾，它應該返回一個指出元素未找到的值。此值和步驟3返回的值必須具有相容的類型。

這些步驟都不依賴于容器所保存的元素類型。因此，只要有一個迭代器可用來訪問元素，find就完全不依賴于容器類型（甚至無須理會保存元素的是不是容器)。

迭代器令算法不依賴于容器，……

在上述find 函數流程中，除了第2步外，其他步驟都可以用迭代器操作來實現:利用迭代器解引用運算符可以實現元素訪問;

• 如果發(fā)現匹配元素，find可以返回指向該元素的迭代器;用迭代器遞增運算符可以移動到下一個元素;
• 尾后迭代器可以用來判斷find是否到達給定序列的末尾;find可以返回尾后迭代器來表示未找到給定元素。

……，但算法依賴于元素類型的操作

雖然迭代器的使用令算法不依賴于容器類型，但大多數算法都使用了一個（或多個)元素類型上的操作。例如，

• 在步驟2中，find用元素類型的 == 運算符完成每個元素與給定值的比較。
• 其他算法可能要求元素類型支持 < 運算符。
• 不過，我們將會看到，大多數算法提供了一種方法，允許我們使用自定義的操作來代替默認的運算符。

關鍵概念:算法水遠不會執(zhí)行容器的操作
泛型算法本身不會執(zhí)行容器的操作，它們只會運行于迭代器之上,執(zhí)行迭代器的操作。泛型算法運行于迭代器之上而不會執(zhí)行容器操作的特性帶來了一個令人驚訝但非常必要的編程假定:
算法永遠不會改變底層容器的大小。
算法可能改變容器中保存的元素的值，也可能在容器內移動元素，但永遠不會直接添加或刪除元素。

如我們將在10.4.1節(jié)所看到的，標準庫定義了一類特殊的迭代器，稱為插入器(inserter)。與普通迭代器只能遍歷所綁定的容器相比，插入器能做更多的事情。當給這類迭代器賦值時，它們會在底層的容器上執(zhí)行插入操作。因此，當一個算法操作一個這樣的迭代器時,迭代器可以完成向容器添加元素的效果，但算法自身永遠不會做這樣的操作。

10.2、初識泛型算法

標準庫提供了超過100個算法。幸運的是，與容器類似，這些算法有一致的結構。比起死記硬背全部100多個算法，理解此結構可以幫助我們更容易地學習和使用這些算法。

除了少數例外，標準庫算法都對一個范圍內的元素進行操作。我們將此元素范圍稱為“輸入范圍”。接受輸入范圍的算法總是使用前兩個參數來表示此范圍，兩個參數分別是指向要處理的第一個元素和尾元素之后位置的迭代器。

雖然大多數算法遍歷輸入范圍的方式相似，但它們使用范圍中元素的方式不同。理解算法的最基本的方法就是了解它們是否讀取元素、改變元素或是重排元素順序。

10.2.1、只讀算法

一些算法只會讀取其輸入范圍內的元素，而從不改變元素。find就是這樣一種算法，以及count函數也是如此。

另一個只讀算法是accumulate，它定義在頭文件numeric中。accumulate函數接受三個參數，前兩個指出了需要求和的元素的范圍，第三個參數是和的初值。假定vec是一個整數序列，則:

//對vec中的元素求和，和的初值是0
int sum = accumulate(vec.cbegin(), vec.cend(), 0);

accumulate的第三個參數的類型決定了函數中使用哪個加法運算符以及返回值的類型。

算法和元素類型

accumulate將第三個參數作為求和起點，這蘊含著一個編程假定:將元素類型加到和的類型上的操作必須是可行的。即，序列中元素的類型必須與第三個參數匹配.或者能夠轉換為第三個參數的類型。

在上例中, vec 中的元素可以是int,或者是double、long long或任何其他可以加到int上的類型。

下面是另一個例子，由于string 定義了 + 運算符，所以我們可以通過調用 accumulate 來將vector 中所有 string 元素連接起來:

string sum = accumulate(v.cbegin(), v.cend(), string(""));

//錯誤:const char*上沒有定義+運算符
string sum = accumulate(v.cbegin(), v.cend(), "");

注意，

• 我們通過第三個參數顯式地創(chuàng)建了一個string。
• 將空串當做一個字符串字面值傳遞給第三個參數是不可以的，會導致一個編譯錯誤。原因在于，如果我們傳遞了一個字符串字面值，用于保存和的對象的類型將是const char*。如前所述，此類型決定了使用哪個 + 運算符。由于const char* 并沒有 + 運算符，此調用將產生編譯錯誤。

對于只讀取而不改變元素的算法，通常最好使用cbegin()和cend()。但是，如果你計劃使用算法返回的迭代器來改變元素的值,就需要使用begin()和end()的結果作為參數。

操作兩個序列的算法

另一個只讀算法是equal，用于確定兩個序列是否保存相同的值。它將第一個序列中的每個元素與第二個序列中的對應元素進行比較。如果所有對應元素都相等，則返回true，否則返回false。

此算法接受三個迭代器:前兩個(與以往一樣）表示第一個序列中的元素范圍，第三個表示第二個序列的首元素:

// roster2中的元素數目應該至少與roster1一樣多
equal(rosterl.cbegin(), roster1.cend(), roster2.cbegin());

由于equal利用迭代器完成操作，因此我們可以通過調用equal 來比較兩個不同類型的容器中的元素。而且，元素類型也不必一樣，只要我們能用–來比較兩個元素類型即可。

例如，在此例中，roster1可以是 vector<string>，而roster2是list<const char*>。

但是, equal 基于一個非常重要的假設:它假定第二個序列至少與第一個序列一樣長。
此算法要處理第一個序列中的每個元素，它假定每個元素在第二個序列中都有一個與之對應的元素。

那些只接受一個單一迭代器來表示第二個序列的算法，都假定第二個序列至少與第一個序列一樣長。

10.2.2、寫容器元素的算法

一些算法將新值賦予序列中的元素。當我們使用這類算法時，必須注意確保序列原大小至少不小于我們要求算法寫入的元素數目。記住，算法不會執(zhí)行容器操作，因此它們自身不可能改變容器的大小。

一些算法會自己向輸入范圍寫入元素。這些算法本質上并不危險，它們最多寫入與給定序列一樣多的元素。

例如,算法 fill 接受一對迭代器表示一個范圍,還接受一個值作為第三個參數。fill 將給定的這個值賦予輸入序列中的每個元素。

fill(vec.begin(), vec.end(), 0);//將每個元素重置為0
//將容器的一個子序列設置為10
fill(vec.begin(), vec.begin() + vec.size()/2, 10);

由于 fill 向給定輸入序列中寫入數據，因此，只要我們傳遞了一個有效的輸入序列，寫入操作就是安全的。

算法不檢查寫操作

一些算法接受一個迭代器來指出一個單獨的目的位置。這些算法將新值賦予一個序列中的元素，該序列從目的位置迭代器指向的元素開始。

例如，函數fill_n接受一個單代器、一個計數值和一個值。它將給定值賦予迭代器指向的元素開始的指定個元素。我們可以用fill_n將一個新值賦予vector中的元素:

vector<int> vec;// 空vector
//使用vec，賦予它不同值
fill_n(vec.begin(), vec.size(), 0);//將所有元素重置為0

//函數fill_n假定寫入指定個元素是安全的。即，如下形式的調用
fill_n(dest, n, val);

fill_n假定dest指向一個元素，而從dest開始的序列至少包含n個元素。

一個初學者非常容易犯的錯誤是在一個空容器上調用fill_n(或類似的寫元素的算法):

vector<int> vec;//空向量
//災難:修改vec中的10個（不存在）元素
fill_n(vec.begin(), 10, 0);

這個調用是一場災難。我們指定了要寫入10個元素，但 vec中并沒有元素——它是空的。這條語句的結果是未定義的。

向目的位置迭代器寫入數據的算法假定目的位置足夠大，能容納要寫入的元素。

介紹back_inserter

一種保證算法有足夠元素空間來容納輸出數據的方法是使用插入迭代器（insert iterator)。

• 插入迭代器是一種向容器中添加元素的迭代器。
• 通常情況，當我們通過一個迭代器向容器元素賦值時，值被賦予迭代器指向的元素。而當我們通過一個插入迭代器賦值時，一個與賦值號右側值相等的元素被添加到容器中。

我們將在10.4.1節(jié)中詳細介紹插入迭代器的內容。但是，為了展示如何用算法向容器寫入數據,我們現在將使用back_inserter,它是定義在頭文件iterator中的一個函數。

back_inserter接受一個指向容器的引用，返回一個與該容器綁定的插入迭代器。當我們通過此迭代器賦值時，賦值運算符會調用push_back將一個具有給定值的元素添加到容器中:

vector<int> vec;//空向量
auto it = back_inserter(vec);//通過它賦值會將元素添加到vec中
*it = 42;		// vec中現在有一個元素，值為42

我們常常使用back_inserter來創(chuàng)建一個迭代器，作為算法的目的位置來使用。例如:

vector<int> vec; //空向量
//正確: back_inserter創(chuàng)建一個插入迭代器，可用來向vec添加元素
fill_n(back_inserter(vec), 10, 0);//添加10個元素到vec

在每步迭代中，fill_n 向給定序列的一個元素賦值。由于我們傳遞的參數是back_inserter返回的迭代器，因此每次賦值都會在vec上調用push_back。最終，這條fill_n調用語句向vec的末尾添加了10個元素，每個元素的值都是0.

拷貝算法

拷貝(copy）算法是另一個向目的位置迭代器指向的輸出序列中的元素寫入數據的算法。此算法接受三個迭代器，前兩個表示一個輸入范圍，第三個表示目的序列的起始位置。此算法將輸入范圍中的元素拷貝到目的序列中。傳遞給copy的目的序列至少要包含與輸入序列一樣多的元素，這一點很重要。

我們可以用copy實現內置數組的鉑貝，如下面代碼所示:

int a1[]= {0,1,2,3,4, 5,6,7,8,9};
int a2[sizeof(a1) / sizeof(*a1)];	//a2與al大小一樣
// ret指向拷貝到a2的尾元素之后的位置
auto ret = copy(begin(al), end(al), a2); //把a1的內容拷貝給a2

copy返回的是其目的位置迭代器（遞增后）的值。即，ret恰好指向拷貝到a2的尾元素之后的位置。

多個算法都提供所謂的“拷貝”版本。這些算法計算新元素的值，但不會將它們放置在輸入序列的末尾，而是創(chuàng)建一個新序列保存這些結果。

例如，replace 算法讀入一個序列，并將其中所有等于給定值的元素都改為另一個值。

• 此算法接受4個參數:前兩個是迭代器，表示輸入序列，后兩個一個是要搜索的值，另一個是新值。它將所有等于第一個值的元素替換為第二個值:

//將所有值為0的元素改為42
replace(ilst.begin(), ilst.end(), 0, 42);

此調用將序列中所有的0都替換為42。如果我們希望保留原序列不變，可以調用replace_copy。此算法接受額外第三個迭代器參數，指出調整后序列的保存位置:

//使用back_inserter按需要增長目標序列
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

此調用后，ilst并未改變，ivec包含ilst的一份拷貝，不過原來在ilst中值為0的元素在ivec中都變?yōu)?2。

10.2.3、重排容器元素的算法

某些算法會重排容器中元素的順序，一個明顯的例子是sort。調用sort會重排輸入序列中的元素，使之有序，它是利用元素類型的 < 運算符來實現排序的。

例如，假定我們想分析一系列兒童故事中所用的詞匯。假定已有一個vector，保存了多個故事的文本。我們希望化簡這個vector，使得每個單詞只出現一次，而不管單詞在任意給定文檔中到底出現了多少次。

為了便于說明問題，我們將使用下面簡單的故事作為輸入:

the quick red fox jumps over the slow red turtle

消除重復單詞

為了消除重復單詞,

• 首先將vector排序,使得重復的單詞都相鄰出現。
• 一旦vector排序完畢，我們就可以使用另一個稱為unique 的標準庫算法來重排vector，使得不重復的元素出現在vector的開始部分。
• 由于算法不能執(zhí)行容器的操作,我們將使用vector的erase成員來完成真正的刪除操作:

void elimDups(vector<string> &words)
{
	//按字典序排序words，以便查找重復單詞
	sort(words.begin(), words.end());
	// unique重排輸入范圍，使得每個單詞只出現一次
	//排列在范圍的前部，返回指向不重復區(qū)域之后一個位置的迭代器
	auto end_unique = unique(words.begin(), words.end());
	//使用向量操作erase刪除重復單詞
	words.erase(end_unique, words.end());
}

unique并不真的刪除任何元素，它只是覆蓋相鄰的重復元素，使得不重復元素出現在序列開始部分。unique返回的迭代器指向最后一個不重復元素之后的位置。此位置之后的元素仍然存在，但我們不知道它們的值是什么。

為了真正地刪除無用元素，我們必須使用容器操作，本例中使用erase。

標準庫算法對迭代器而不是容器進行操作。因此,算法不能（直接)添加或刪除元素。

10.3、定制操作

很多算法都會比較輸入序列中的元素。默認情況下，這類算法使用元素類型的 < 或 == 運算符完成比較。標準庫還為這些算法定義了額外的版本，允許我們提供自己定義的操作來代替默認運算符。

10.3.1、向算法傳遞函數

謂詞（predicate）

謂詞是一個可調用的表達式，其返回結果是一個能用作條件的值。標準庫算法所使用的謂詞分為兩類:

• 一元謂詞（unary predicate，意味著它們只接受單一參數）;
• 二元謂詞( binary predicate，意味著它們有兩個參數)。

接受謂詞參數的算法對輸入序列中的元素調用謂詞。因此,元素類型必須能轉換為謂詞的參數類型。

接受一個二元謂詞參數的sort版本用這個謂詞代替 < 來比較元素。當前，我們只需知道，此操作必須在輸入序列中所有可能的元素值上定義一個一致的序。我們之前定義的 isShorter就是一個滿足這些要求的函數，因此可以將 isShorter傳遞給sort。這樣做會將元素按大小重新排序:

//比較函數，用來按長度排序單詞
bool isShorter(const string &s1, const string &s2){
	return sl.size() < s2.size();
}

//按長度由短至長排序words
sort(words.begin(), words.end(), isshorter);

排序算法

在我們將 words 按大小重排的同時，還希望具有相同長度的元素按字典序排列。為了保持相同長度的單詞按字典序排列，可以使用stable_sort算法。這種穩(wěn)定排序算法維持相等元素的原有順序。

通常情況下，我們不關心有序序列中相等元素的相對順序，它們畢竟是相等的。但是，在本例中，我們定義的“相等”關系表示“具有相同長度”。而具有相同長度的元素，如果看其內容，其實還是各不相同的。通過調用stable_sort，可以保持等長元素間的字典序:

elimDups(words); //將words按字典序重排，并消除重復單詞
//按長度重新排序，長度相同的單詞維持字典序
stable_sort(words.begin(), words.end(), isShorter);
for(const auto &s : words)//無須拷貝字符串
	cout << s << " "; //打印每個元素，以空格分隔
cout << endl;

假定在此調用前words是按字典序排列的，則調用之后，words會按元素大小排序，而長度相同的單詞會保持字典序。如果我們對原來的vector內容運行這段代碼，輸出為:

fox red the over slow jumps quick turtle

10.3.2、lambda表達式

根據算法接受一元謂詞還是二元謂詞，我們傳遞給算法的謂詞必須嚴格接受一個或兩個參數。但是，有時我們希望進行的操作需要更多參數，超出了算法對謂詞的限制。

一個相關的例子是，我們將修改上面的程序，求大于等于一個給定長度的單詞有多少。我們還會修改輸出，使程序只打印大于等于給定長度的單詞。

我們將此函數命名為biggies，其框架如下所示:

void biggies(vector<string> &words, vector<string>::size_type sz)
{
	elimDups (words);//將words按字典序排序，刪除重復單詞
	//按長度排序，長度相同的單詞維持字典序
	stable_sort(words.begin(), words.end(), isShorter);
	//獲取一個迭代器，指向第一個滿足size() >= sz的元素
	//計算滿足size >= sz的元素的數目
	//打印長度大于等于給定值的單詞，每個單詞后面接一個空格
}

我們可以使用標準庫find_if 算法來查找第一個具有特定大小的元素, find_if 的第三個參數是一個謂詞。但是，find_if 接受一元謂詞——我們傳遞給 find_if 的任何函數都必須嚴格接受一個參數，以便能用來自輸入序列的一個元素調用它。沒有任何辦法能傳遞給它第二個參數來表示長度。為了解決此問題，需要使用另外一些語言特性。

介紹lambda

我們可以向一個算法傳遞任何類別的可調用對象（callable object)。對于一個對象或一個表達式，如果可以對其使用調用運算符，則稱它為可調用的。即，如果e是一個可調用的表達式，則我們可以編寫代碼e(args)，其中args是一個逗號分隔的一個或多個參數的列表。

到目前為止，

• 我們使用過的僅有的兩種可調用對象是函數和函數指針。
• 還有其他兩種可調用對象:
  • 重載了函數調用運算符的類，我們將在14.8節(jié)介紹;
  • 以及lambda表達式（lambda expression)。

一個lambda表達式表示一個可調用的代碼單元。我們可以將其理解為一個未命名的內聯函數。與任何函數類似，一個 lambda具有一個返回類型、一個參數列表和一個函數體。但與函數不同，lambda可能定義在函數內部。一個 lambda表達式具有如下形式:

[capture list ](parameter list) -> return type { function body }

• capture list（捕獲列表）是一個lambda所在函數中定義的局部變量的列表(通常為空);
• return type、parameter list和 function body與任何普通函數一樣，分別表示返回類型、參數列表和函數體。
• 但是，與普通函數不同，lambda必須使用尾置返回（參見6.3.3節(jié)，第206頁) 來指定返回類型。

我們可以忽略參數列表和返回類型，但必須永遠包含捕獲列表和函數體：

//我們定義了一個可調用對象 `f` ，它不接受參數，返回42。
auto f = [] { return 42;};

//lambda 的調用方式與普通函數的調用方式相同，都是使用調用運算符:
cout << f() << endl; //打印42

在 lambda中忽略括號和參數列表等價于指定一個空參數列表。在此例中，當調用f時，參數列表是空的。如果忽略返回類型，lambda根據函數體中的代碼推斷出返回類型。如果函數體只是一個return語句，則返回類型從返回的表達式的類型推斷而來。否則，返回類型為void。

如果 lambda的函數體包含任何單一return語句之外的內容，且未指定返回類型，則返回void。

向lambda傳遞參數

與一個普通函數調用類似，調用一個 lambda時給定的實參被用來初始化lambda的形參。

• 通常，實參和形參的類型必須匹配。
• 但與普通函數不同，lambda不能有默認參數。因此，一個lambda調用的實參數目永遠與形參數目相等。
• 一旦形參初始化完畢，就可以執(zhí)行函數體了。

作為一個帶參數的 lambda 的例子，我們可以編寫一個與isShorter函數完成相同功能的lambda:

[](const string &a, const string &b)
	{return a.size() < b.size();}

空捕獲列表表明此lambda 不使用它所在函數中的任何局部變量。
lambda 的參數與isShorter 的參數類似，是const string的引用。lambda的函數體也與isShorter類似，比較其兩個參數的size()，并根據兩者的相對大小返回一個布爾值。

如下所示，可以使用此 lambda來調用stable_sort:

stable_sort(words.begin(), words.end(),
			[](const string &a, const string &b)
				{return a.size() < b.size(); } );

當stable_sort需要比較兩個元素時，它就會調用給定的這個lambda表達式。

使用捕獲列表

我們現在已經準備好解決原來的問題了——編寫一個可以傳遞給find_if的可調用表達式。我們希望這個表達式能將輸入序列中每個string 的長度與 biggies 函數中的sz 參數的值進行比較。

雖然一個 lambda可以出現在一個函數中，使用其局部變量，但它只能使用那些明確指明的變量。一個lambda通過將局部變量包含在其捕獲列表中來指出將會使用這些變量。捕獲列表指引 lambda在其內部包含訪問局部變量所需的信息。

在本例中，我們的 lambda 會捕獲 sz，并只有單一的string參數。其函數體會將string的大小與捕獲的sz的值進行比較:

[sz] (const string &a)
	{ return a.size() >= sz; };

lambda 以一對 [] 開始，我們可以在其中提供一個以逗號分隔的名字列表，這些名字都是它所在函數中定義的。

由于此lambda捕獲sz，因此 lambda的函數體可以使用sz。lambda不捕獲words,因此不能訪問此變量。如果我們給lambda提供一個空捕獲列表，則代碼會編譯錯誤:

//錯誤:sz未捕獲
[](const string &a)
	{ return a.size() >= sz; };

一個lambda只有在其捕獲列表中捕獲一個它所在函數中的局部變量，才能在函數體中使用該變量。

調用find_if

使用此lambda，我們就可以查找第一個長度大于等于sz的元素:

//獲取一個迭代器，指向第一個滿足size ( ) >= sz的元素
auto wc = find_if(words.begin(), words.end(),
	[sz] (const string &a)
		{ return a.size() >= sz; });

這里對find_if的調用返回一個迭代器，指向第一個長度不小于給定參數sz的元素。如果這樣的元素不存在，則返回words.end()的一個拷貝。

我們可以使用find_if返回的迭代器來計算從它開始到words的末尾一共有多少個元素：

//計算滿足size >= sz的元素的數目
auto count = words.end() - wc;
cout << count << " " << make_plural(count, "word", "s")
		<<" of length " << sz << " or longer" << endl;

我們的輸出語句調用make_plural來輸出“word”或“words"，具體輸出哪個取決于大小是否等于1。

for_each算法

問題的最后一部分是打印words中長度大于等于sz的元素。為了達到這一目的，我們可以使用for_each算法。此算法接受一個可調用對象，并對輸入序列中每個元素調用此對象:

//打印長度大于等于給定值的單詞，每個單詞后面接一個空格
for_each(wc, words.end(),
		[] (const string &s){cout << s << " " ;});
cout << endl;

此lambda中的捕獲列表為空，但其函數體中還是使用了兩個名字: s 和 cout，前者是它自己的參數。

捕獲列表為空，是因為我們只對lambda所在函數中定義的(非static)變量使用捕獲列表。一個 lambda可以直接使用定義在當前函數之外的名字。在本例中，cout不是定義在biggies中的局部名字，而是定義在頭文件iostream中。因此，只要在biggies出現的作用域中包含了頭文件iostream，我們的 lambda就可以使用cout。

捕獲列表只用于局部非static變量，lambda可以直接使用局部static變量和在它所在函數之外聲明的名字。

完整的biggies

到目前為止，我們已經解決了程序的所有細節(jié)，下面就是完整的程序:

void biggies(vector<string> &words, vector<string>::size_type sz)
{
	elimDups(words); //將words按字典序排序，刪除重復單詞
	//按長度排序，長度相同的單詞維持字典序
	stable_sort(words.begin(), words.end(),
				[](const string &a, const string &b)
					{return a.size() < b.size();});
	//獲取一個迭代器，指向第一個滿足size() >= sz的元素
	auto wc = find_if(words.begin (), words.end(),
					[sz] (const string &a)
					{ return a.size() >= sz; });
	//計算滿足size >= sz的元素的數目
	auto count = words.end() - wc;
	cout << count << " " << make_plural(count, "word", "s")
		<< " of length " << sz << " or longer" << endl;
	//打印長度大于等于給定值的單詞，每個單詞后面接一個空格
	for_each (wc, words.end(),
				[]（const string &s){cout << s << " ";});
	cout << endl;
}

10.3.3、lambda捕獲和返回

當定義一個 lambda 時，編譯器生成一個與 lambda 對應的新的（未命名的）類類型?？梢赃@樣理解，當向一個函數傳遞一個lambda時，同時定義了一個新類型和該類型的一個對象:傳遞的參數就是此編譯器生成的類類型的未命名對象。類似的，當使用auto定義一個用 lambda初始化的變量時，定義了一個從 lambda生成的類型的對象。

默認情況下,從 lambda 生成的類都包含一個對應該lambda所捕獲的變量的數據成員。類似任何普通類的數據成員，lambda的數據成員也在 lambda 對象創(chuàng)建時被初始化。

值捕獲

類似參數傳遞，變量的捕獲方式也可以是值或引用。表10.1列出了幾種不同的構造捕獲列表的方式。到目前為止，我們的 lambda采用值捕獲的方式。與傳值參數類似，采用值捕獲的前提是變量可以拷貝。與參數不同，被捕獲的變量的值是在lambda創(chuàng)建時拷貝，而不是調用時拷貝:

void fcn1()
{
	size_t v1 =42;		//局部變量
	//將v1拷貝到名為f的可調用對象
	auto f = [v1] { return v1; };
	v1 = 0;
	auto j = f();	//j為42;f保存了我們創(chuàng)建它時v1的拷貝
}

由于被捕獲變量的值是在 lambda創(chuàng)建時拷貝，因此隨后對其修改不會影響到lambda內對應的值。

引用捕獲

我們定義lambda時可以采用引用方式捕獲變量。例如:

void fcn2()
{
	size_t v1 = 42;	//局部變量
	//對象f2包含v1的引用
	auto f2 = [&v1] { return vl; };
	vl = 0;
	auto j = f2();	// j為0;f2保存v1的引用，而非拷貝
}

v1之前的&指出v1應該以引用方式捕獲。一個以引用方式捕獲的變量與其他任何類型的引用的行為類似。當我們在 lambda函數體內使用此變量時，實際上使用的是引用所綁定的對象。在本例中，當lambda返回v1時，它返回的是v1指向的對象的值。

引用捕獲與返回引用有著相同的問題和限制。如果我們采用引用方式捕獲一個變量，就必須確保被引用的對象在 lambda 執(zhí)行的時候是存在的。lambda捕獲的都是局部變量，這些變量在函數結束后就不復存在了。如果 lambda可能在函數結束后執(zhí)行,捕獲的引用指向的局部變量已經消失。

引用捕獲有時是必要的。例如，我們可能希望biggies 函數接受一個 ostream的引用，用來輸出數據，并接受一個字符作為分隔符:

void biggies (vector<string> &words,
				vector<string>::size_type sz,
				ostream &os = cout, char c= ' ')
{
	//與之前例子一樣的重排words的代碼
	//打印count的語句改為打印到os
	for_each (words.begin(), words.end(),
				[&os, c](const string &s){ os << s << c; });
}

我們不能拷貝ostream對象（參見8.1.1節(jié))，因此捕獲os 的唯一方法就是捕獲其引用（或指向os的指針)。

當我們向一個函數傳遞一個lambda時，就像本例中調用for_each 那樣,lambda會立即執(zhí)行。在此情況下，以引用方式捕獲 os 沒有問題，因為當for_each 執(zhí)行時，biggies 中的變量是存在的。

我們也可以從一個函數返回 lambda。函數可以直接返回一個可調用對象，或者返回一個類對象，該類含有可調用對象的數據成員。如果函數返回一個lambda，則與函數不能返回一個局部變量的引用類似，此lambda也不能包含引用捕獲。

當以引用方式捕獲一個變量時，必須保證在 lambda執(zhí)行時變量是存在的。

隱式捕獲

除了顯式列出我們希望使用的來自所在函數的變量之外,還可以讓編譯器根據lambda體中的代碼來推斷我們要使用哪些變量。為了指示編譯器推斷捕獲列表，應在捕獲列表中寫一個 & 或 =。

• & 告訴編譯器采用捕獲引用方式，
• =則表示采用值捕獲方式。

例如，我們可以重寫傳遞給 find_if 的 lambda :

// sz為隱式捕獲，值捕獲方式
wc = find_if (words.begin(), words.end(),
				[=] (const string &s )
				{ return s.size() >= sz; });

如果我們希望對一部分變量采用值捕獲，對其他變量采用引用捕獲，可以混合使用隱式捕獲和顯式捕獲:

void biggies(vector<string> &words,
			vector<string>::size_type sz, ostream &os = cout, char c = '')
{
	//其他處理與前例一樣
	// os隱式捕獲，引用捕獲方式; c顯式捕獲，值捕獲方式
	for_each (words.begin(), words.end(),
				[&, c] (const string &s){ os << s << c; });
	// os顯式捕獲，引用捕獲方式;c隱式捕獲，值捕獲方式
	for_each (words.begin(), words.end(),
				[=, &os](const string &s){ os << s << c;});
}

當我們混合使用隱式捕獲和顯式捕獲時，捕獲列表中的第一個元素必須是一個 & 或 =。此符號指定了默認捕獲方式為引用或值。

當混合使用隱式捕獲和顯式捕獲時，顯式捕獲的變量必須使用與隱式捕獲不同的方式。即，

• 如果隱式捕獲是引用方式（使用了&)，則顯式捕獲命名變量必須采用值方式，因此不能在其名字前使用&。
• 類似的，如果隱式捕獲采用的是值方式(使用了=)，則顯式捕獲命名變量必須采用引用方式，即，在名字前使用&。

可變lambda

默認情況下，對于一個值被拷貝的變量，lambda不會改變其值。如果我們希望能改變一個被捕獲的變量的值，就必須在參數列表首加上關鍵字mutable。因此，可變lambda能省略參數列表:

void fcn3(){
	size_t v1 = 42;//局部變量
	// f可以改變它所捕獲的變量的值
	auto f = [v1] () mutable { return ++v1; };
	vl = 0;
	auto j = f();// j為43
}

一個引用捕獲的變量是否(如往常一樣)可以修改依賴于此引用指向的是一個const類型還是一個非const類型:

void fcn4 (){
	size_t v1 = 42; //局部變量
	// v1是一個非const變量的引用
	//可以通過f2中的引用來改變它
	auto f2 = [&v1] { return ++vl; };
	v1 = 0;
	auto j = f2();// j為1
}

指定lambda返回類型

到目前為止，我們所編寫的 lambda 都只包含單一的return語句。因此，我們還未遇到必須指定返回類型的情況。默認情況下，如果一個 lambda體包含return 之外的任何語句，則編譯器假定此 lambda 返回 void。與其他返回void 的函數類似，被推斷返回 void 的 lambda不能返回值。

下面給出了一個簡單的例子，我們可以使用標準庫 transform 算法和一個 lambda 來將一個序列中的每個負數替換為其絕對值:

transform(vi.begin(), vi.end(), vi.begin(),
			[] (int i){ return i < 0 ? -i : i; });

在本例中，我們傳遞給 transform 一個lambda，它返回其參數的絕對值lambda體是單一的return語句，返回一個條件表達式的結果。我們無須指定返回類型，因為可以根據條件運算符的類型推斷出來。

但是，如果我們將程序改寫為看起來是等價的 if 語句，就會產生編譯錯誤:

//錯誤:不能推斷l(xiāng)ambda的返回類型
transform(vi.begin(), vi.end(), vi.begin(),
			[](int i) { if(i < 0) return -i; else return i; })

編譯器推斷這個版本的 lambda 返回類型為 void，但它返回了一個 int 值。

當我們需要為一個lambda定義返回類型時，必須使用尾置返回類型:

transform (vi.begin(), vi.end(), vi.begin(),
			[] (int i) -> int
			{ if (i < 0) return -i; else return i; });

在此例中，傳遞給transform的第四個參數是一個lambda，它的捕獲列表是空的，接受單一int參數，返回一個int值。它的函數體是一個返回其參數的絕對值的if 語句。

10.3.4、參數綁定

對于那種只在一兩個地方使用的簡單操作，lambda表達式是最有用的。

如果我們需要在很多地方使用相同的操作，通常應該定義一個函數，而不是多次編寫相同的 lambda表達式。類似的，如果一個操作需要很多語句才能完成，通常使用函數更好。

如果lambda的捕獲列表為空，通常可以用函數來代替它。

• 如前面章節(jié)所示，既可以用一個 lambda，也可以用函數 isShorter 來實現將 vector 中的單詞按長度排序。
• 類似的，對于打印 vector內容的lambda，編寫一個函數來替換它也是很容易的事情，這個函數只需接受一個string 并在標準輸出上打印它即可。

但是，對于捕獲局部變量的 lambda，用函數來替換它就不是那么容易了。

• 例如，我們用在find_if調用中的 lambda 比較一個string 和一個給定大小。

我們可以很容易地編寫一個完成同樣工作的函數:

bool check_size (const string &s, string::size_type sz)
{
	return s.size() >= sz;
}

但是，我們不能用這個函數作為find_if的一個參數。如前文所示，find_if接受一個一元謂詞，因此傳遞給find_if 的可調用對象必須接受單一參數。biggies 傳遞給find_if的 lambda使用捕獲列表來保存sz。為了用check_size來代替此lambda，必須解決如何向sz形參傳遞一個參數的問題。

標準庫bind函數

我們可以解決向check_size傳遞一個長度參數的問題，方法是使用一個新的名為bind的標準庫函數，它定義在頭文件 functional中。

• 可以將bind函數看作一個通用的函數適配器（參見9.6節(jié))
• 它接受一個可調用對象，生成一個新的可調用對象來“適應”原對象的參數列表。

調用bind的一般形式為:

auto newCallable = bind(callable, arg_list);

其中，newCallable 本身是一個可調用對象，arg_list 是一個逗號分隔的參數列表，對應給定的 callable 的參數。

• 即，當我們調用 newCallable 時 ，newCallable 會調用 callable ，并傳遞給它 arg_list 中的參數。
• arg_list 中的參數可能包含形如 _n 的名字，其中 n 是一個整數。
  • 這些 參數 是“占位符”,表示 newCallable 的參數，它們占據了傳遞給 newCallable 的參數的“位置”。
  • 數值 n 表示生成的可調用對象中參數的位置: _1 為 newCallable 的第一個參數，_2 為第二個參數，依此類推。

綁定 check_size 的 sz 參數

作為一個簡單的例子，我們將使用 bind 生成一個調用check_size的對象，如下所示，它用一個定值作為其大小參數來調用check_size:

// check6是一個可調用對象，接受一個string類型的參數
//并用此string和值6來調用check_size
auto check6 = bind(check_size, _1, 6);

string s = "hello";
bool b1 = check6(s); // check6(s)會調用check_size(s,6)

此 bind 調用只有一個占位符，表示check6只接受單一參數。占位符出現在arg_list 的第一個位置，表示 check6的此參數對應check_size的第一個參數。此參數是一個const string&。因此，調用check6必須傳遞給它一個string類型的參數，check6會將此參數傳遞給check_size。

使用bind，我們可以將原來基于lambda的find_if調用，替換為如下使用check_size的版本:

auto wc = find_if(words.begin(), words.end(),
					[sz] (const string &a)
					{ return a.size() >= sz; });
//替換為
auto wc = find_if(words.begin(), words.end(),
					bind(check_size, _1, sz));

此 bind調用生成一個可調用對象，將check_size 的第二個參數綁定到sz的值。當find_if對words中的string調用這個對象時，這些對象會調用check_size，將給定的string和 sz傳遞給它。因此，find_if 可以有效地對輸入序列中每個string調用check_size，實現string 的大小與sz的比較。

使用placeholders名字

名字*_n* 都定義在一個名為placeholders的命名空間中，而這個命名空間本身定義在std命名空間（參見3.1節(jié))中。
為了使用這些名字，兩個命名空間都要寫上。與我們的其他例子類似，對bind 的調用代碼假定之前已經恰當地使用了using聲明。例如，_1對應的using聲明為:

using std::placeholders::_1;

此聲明說明我們要使用的名字*_1*定義在命名空間placeholders 中，而此命名空間又定義在命名空間std中。

對每個占位符名字，我們都必須提供一個單獨的using聲明。編寫這樣的聲明很煩人，也很容易出錯。可以使用另外一種不同形式的using 語句（詳細內容將在18.2.2節(jié)(第702頁)中介紹)，而不是分別聲明每個占位符，如下所示:

using namespace namespace_name;

這種形式說明希望所有來自namespace_name 的名字都可以在我們的程序中直接使用。例如：

using namespace std::placeholders;

//一般直接使用
using namespace std;

使得由placeholders定義的所有名字都可用。與bind函數一樣，placeholders命名空間也定義在functional頭文件中。

bind的參數

如前文所述，我們可以用bind修正參數的值。更一般的，可以用bind綁定給定可調用對象中的參數或重新安排其順序。例如，假定 f 是一個可調用對象，它有5個參數，則下面對bind的調用:

//g是一個有兩個參數的可調用對象
auto g = bind(f, a, b, _2, c, _1);

生成一個新的可調用對象 g，它有兩個參數，分別用占位符 _2 和 _1 表示。這個新的可調用對象將它自己的參數作為第三個和第五個參數傳遞給 f 。f 的第一個、第二個和第四個參數分別被綁定到給定的值a、b 和 c 上。

傳遞給 g 的參數按位置綁定到占位符。即，第一個參數綁定到 _1 ，第二個參數綁定到*_2* 。因此，當我們調用 g 時，其第一個參數將被傳遞給 f 作為最后一個參數，第二個參數將被傳遞給f作為第三個參數。實際上，這個bind 調用會:

g(_1, _2)
//映射為
f(a, b, _2, c, _1)

用bind 重排參數順序

下面是用bind重排參數順序的一個具體例子，我們可以用bind顛倒isShroter的含義:

//按單詞長度由短至長排序
sort(words.begin(), words.end(), isShorter);
//按單詞長度由長至短排序
sort(words.begin(), words.end(), bind(isShorter, _2, _1));

在第一個調用中，當sort需要比較兩個元素A和B時，它會調用isShorter(A,B)。在第二個對sort的調用中，傳遞給isShorter的參數被交換過來了。因此，當sort比較兩個元素時，就好像調用isshorter (B,A)一樣。

綁定引用參數

默認情況下，bind 的那些不是占位符的參數被拷貝到bind返回的可調用對象中。但是，與 lambda類似，有時對有些綁定的參數我們希望以引用方式傳遞，或是要綁定參數的類型無法拷貝。

例如，為了替換一個引用方式捕獲 ostream 的 lambda:

// os是一個局部變量，引用一個輸出流
// c是一個局部變量，類型為char
for_each(words.begin(), words.end(),
		[&os, c] (const string &s) { os << s << c; );

//可以很容易地編寫一個函數，完成相同的工作:
ostream &print(ostream &os, const string &s, char c)
{
	return os << s << c;
}

但是，不能直接用bind來代替對os的捕獲:

//錯誤:不能拷貝os
for_each(words.begin(), words.end(), 
		bind(print, os, _l, ' '));

原因在于bind 拷貝其參數，而我們不能拷貝一個 ostream。如果我們希望傳遞給bind一個對象而又不拷貝它，就必須使用標準庫 ref 函數:

for_each(words.begin(), words.end(),
		bind(print, ref(os), _1, ' '));

函數 ref 返回一個對象，包含給定的引用, 此對象是可以拷貝的。標準庫中還有一個cref函數，生成一個保存const引用的類。與bind一樣，函數ref和cref也定義在頭文件functional 中。

10.4、再探迭代器

除了為每個容器定義的迭代器之外，標準庫在頭文件 iterator 中還定義了額外幾種迭代器。這些迭代器包括以下幾種:

• 插入迭代器（insert iterator):這些迭代器被綁定到一個容器上，可用來向容器插元素。
• 流迭代器 ( stream iterator):這些迭代器被綁定到輸入或輸出流上，可用來遍歷所關聯的IO流。
• 反向迭代器（ reverse iterator ):這些迭代器向后而不是向前移動。除了forward_list之外的標準庫容器都有反向迭代器。
• 移動迭代器 (move iterator):這些專用的迭代器不是拷貝其中的元素，而是移動它們。我們將在13.6.2節(jié)介紹移動迭代器。

10.4.1、插入迭代器

插入器是一種迭代器適配器（參見9.6節(jié))，它接受一個容器，生成一個迭代器，能實現向給定容器添加元素。當我們通過一個插入迭代器進行賦值時，該迭代器調用容器操作來向給定容器的指定位置插入一個元素。表10.2列出了這種迭代器支持的操作。

插入器有三種類型,差異在于元素插入的位置:

• back_inserter (參見10.2.2節(jié)）創(chuàng)建一個使用push_back的迭代器。
• front_inserter 創(chuàng)建一個使用push_front的迭代器。
• inserter 創(chuàng)建一個使用insert的迭代器。此函數接受第二個參數，這個參數必須是一個指向給定容器的迭代器。元素將被插入到給定迭代器所表示的元素之前。

注： 只有在容器支持push_front的情況下,我們才可以使用front_inserter.類似的，只有在容器支持 push_back的情況下，我們才能使用back_inserter。

理解插入器的工作過程是很重要的:當調用 inserter(c, iter) 時，我們得到一個迭代器，接下來使用它時，會將元素插入到 iter 原來所指向的元素之前的位置。即，如果 it 是由 inserter 生成的迭代器，則下面這樣的賦值語句

*it = val;

//其效果與下面代碼一樣
it = c.insert(it, val); // it指向新加入的元素
++it; //遞增it使它指向原來的元素

front_inserter 生成的迭代器的行為與 inserter 生成的迭代器完全不一樣。

• 當我們使用 front_inserter時，元素總是插入到容器第一個元素之前。
• 即使我們傳遞給inserter的位置原來指向第一個元素，只要我們在此元素之前插入一個新元素，此元素就不再是容器的首元素了:

list<int> lst = {1,2,3,4};
list<int> lst2, lst3; //空list

//考貝完成之后，lst2包含4 3 2 1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
//拷貝完成之后，lst3包含1 2 3 4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

當調用front_inserter(c)時，我們得到一個插入迭代器，接下來會調用push_front。當每個元素被插入到容器 c 中時，它變?yōu)?c 的新的首元素。因此，front_inserter生成的迭代器會將插入的元素序列的順序顛倒過來，而 inserter 和 back_inserter 則不會。

10.4.2、iostream迭代器

雖然iostream類型不是容器，但標準庫定義了可以用于這些IO類型對象的迭代器:

• istream_iterator (參見表10.3）讀取輸入流;
• ostream_ iterator (參見表10.4節(jié)）向一個輸出流寫數據。

這些迭代器將它們對應的流當作一個特定類型的元素序列來處理。通過使用流迭代器，我們可以用泛型算法從流對象讀取數據以及向其寫入數據。

istream_iterator操作

當創(chuàng)建一個流迭代器時，必須指定迭代器將要讀寫的對象類型。

• 一個istream_iterator使用 >> 來讀取流。因此， istream_iterator 要讀取的類型必須定義了輸入運算符。
• 當創(chuàng)建一個istream_iterator時，我們可以將它綁定到一個流。
• 當然，我們還可以默認初始化迭代器，這樣就創(chuàng)建了一個可以當作尾后值使用的迭代器。

istream_iterator<int> int_it(cin); 		//從cin 讀取int
istream_iterator<int> int_eof;			//尾后迭代器
ifstream in("afile");
istream_iterator<string> str_it(in);	// 從"afile"讀取字符串

//下面是一個用istream_iterator從標準輸入讀取數據，存入一個vector的例子:
istream_iterator<int> in_iter(cin);		//從cin讀取int
istream_iterator<int> eof;				// istream尾后迭代器
while (in_iter != eof)					//當有數據可供讀取時
	//后置遞增運算讀取流，返回迭代器的舊值
	//解引用迭代器，獲得從流讀取的前一個值
	vec.push_back(*in_iter++);

此循環(huán)從cin 讀取 int 值，保存在 vec 中。在每個循環(huán)步中，循環(huán)體代碼檢查in_iter是否等于 eof。eof被定義為空的istream_iterator，從而可以當作尾后迭代器來使用。

此程序最困難的部分是傳遞給push_back的參數，后置遞增運算會從流中讀取下一個值，向前推進，但返回的是迭代器的舊值。迭代器的舊值包含了從流中讀取的前一個值，對迭代器進行解引用就能獲得此值。

對于一個綁定到流的迭代器，一旦其關聯的流遇到文件尾或遇到IO錯誤，迭代器的值就與尾后迭代器相等。

我們可以將程序重寫為如下形式，這體現了istream_iterator更有用的地方:

istream_iterator<int> in_iter(cin), eof;		// 從cin讀取int
vector<int> vec(in_iter, eof); 					//從迭代器范圍構造vec

本例中我們用一對表示元素范圍的迭代器來構造vec。這兩個迭代器是istream_iterator，這意味著元素范圍是通過從關聯的流中讀取數據獲得的。這個構造函數從cin中讀取數據，直至遇到文件尾或者遇到一個不是int 的數據為止。從流中讀取的數據被用來構造vec。

使用算法操作流迭代器

由于算法使用迭代器操作來處理數據，而流迭代器又至少支持某些迭代器操作，因此我們至少可以用某些算法來操作流迭代器。我們在10.5.1節(jié)會看到如何分辨哪些算法可以用于流迭代器。下面是一個例子，我們可以用一對istream_iterator來調用accumulate:

istream_iterator<int> in(cin), eof;
//如果輸入為： 23 109 45 89 6 34 12 90 34 23 56 23 8 89 23
cout << accumulate(in, eof, 0) << endl; //輸出為664

istream_iterator 允許使用懶惰求值

當我們將一個istream_iterator綁定到一個流時，標準庫并不保證迭代器立即從流讀取數據。具體實現可以推遲從流中讀取數據，直到我們使用迭代器時才真正讀取。

標準庫中的實現所保證的是，在我們第一次解引用迭代器之前，從流中讀取數據的操作已經完成了。

對于大多數程序來說，立即讀取還是推遲讀取沒什么差別。但是，如果我們創(chuàng)建了一個istream_iterator，沒有使用就銷毀了，或者我們正在從兩個不同的對象同步讀取同一個流，那么何時讀取可能就很重要了。

ostream_iterator操作

我們可以對任何具有輸出運算符（ << 運算符）的類型定義ostream_iterator。

• 當創(chuàng)建一個ostream_iterator時，我們可以提供(可選的）第二參數，它是一個字符串，在輸出每個元素后都會打印此字符串。此字符串必須是一個C風格字符串(即，一個字符串字面常量或者一個指向以空字符結尾的字符數組的指針)。
• 必須將ostream_iterator 綁定到一個指定的流，不允許空的或表示尾后位置的ostream_iterator。

我們可以用ostream_iterator來輸出值的序列:

ostream_iterator<int> out_iter(cout, " ");
for(auto e : vec)
	*out_iter++ = e; //賦值語句實際上將元素寫到cout
cout << endl;

此程序將vec中的每個元素寫到cout，每個元素后加一個空格。每次向out_iter賦值時，寫操作就會被提交(直接輸出)。

值得注意的是，當我們向out_iter賦值時，可以忽略解引用和遞增運算。即，循環(huán)可以重寫成下面的樣子:

for (auto e : vec)
	out_iter = e; //賦值語句將元素寫到cout
cout << endl;

運算符 * 和 ++ 實際上對 ostream_iterator 對象不做任何事情，因此忽略它們對我們的程序沒有任何影響。但是，推薦第一種形式。在這種寫法中，流迭代器的使用與其他迭代器的使用保持一致。如果想將此循環(huán)改為操作其他迭代器類型，修改起來非常容易。而且，對于讀者來說，此循環(huán)的行為也更為清晰。

可以通過調用copy來打印vec中的元素，這比編寫循環(huán)更為簡單:

copy(vec.begin(), vec.end(), out_iter) ;
cout << endl;

使用流迭代器處理類類型

我們可以為任何定義了輸入運算符( >> )的類型創(chuàng)建 istream_iterator對象。類似的，只要類型有輸出運算符( << )，我們就可以為其定義ostream_iterator。

由于sales_item 既有輸入運算符也有輸出運算符，因此可以使用IO迭代器重寫1.6節(jié)（第21頁）中的書店程序:

istream_iterator<sales_item> item_iter(cin), eof;
ostream_iterator<Sales_item> out_iter(cout, "\n");
//將第一筆交易記錄存在 sum 中，并讀取下一條記錄
sales_item sum = *item_iter++;
while (item_iter != eof) {
	//如果當前交易記錄（存在iten_iter中）有著相同的ISBN號
	if (item_iter->isbn() == sum.isbn())
		sum += *item_iter++;			//將其加到sum上并讀取下一條記錄
	else {
		out_iter = sum;					//輸出 sum當前值
		sum = *item_iter++;				//讀取下一條記錄
	}
}
out_iter = sum;							//記得打印最后一組記錄的和

10.4.3、反向迭代器

反向迭代器就是在容器中從尾元素向首元素反向移動的迭代器。對于反向迭代器，遞增（以及遞減）操作的含義會顛倒過來。遞增一個反向迭代器（++it ）會移動到前一個元素;遞減一個迭代器（--it）會移動到下一個元素。

除了 forward_list 之外,其他容器都支持反向迭代器。我們可以通過調用rbegin、rend、crbegin和 crend 成員函數來獲得反向迭代器。這些成員函數返回指向容器尾元素和首元素之前一個位置的迭代器。與普通迭代器一樣，反向迭代器也有 const 和非 const 版本。

下面的循環(huán)是一個使用反向迭代器的例子，它按逆序打印 vec 中的元素:

vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
//從尾元素到首元素的反向迭代器
for (auto r_iter = vec.crbegin(); 			 //將r_iter綁定到尾元素
			r_iter != vec.crend();			 //crend指向首元素之前的位置
			++r_iter)			 			 //實際是遞減，移動到前一個元素
	cout << *r_iter << endl;		      	 //打印9，8， 7, ... 0


sort(vec.begin(), vec.end()); //按“正常序”排序vec

//按逆序排序:將最小元素放在vec的末尾
sort(vec.rbegin(), vec.rend());

反向迭代器需要遞減運算符

• 不必驚訝，我們只能從既支持 ++ 也支持 -- 的迭代器來定義反向迭代器。畢竟反向迭代器的目的是在序列中反向移動。
• 除了forward_list 之外，標準容器上的其他迭代器都既支持遞增運算又支持遞減運算。
• 但是，流迭代器不支持遞減運算，因為不可能在一個流中反向移動。因此，不可能從一個forward_list或一個流迭代器創(chuàng)建反向迭代器。

反向迭代器和其他迭代器間的關系

假定有一個名為line 的 string，保存著一個逗號分隔的單詞列表，我們希望打印 line 中的第一個單詞。使用find可以很容易地完成這一任務:

//在一個逗號分隔的列表中查找第一個元素
auto comma = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), comma) << endl;

//如果希望打印最后一個單詞，可以改用反向迭代器
//在一個逗號分隔的列表中查找最后一個元素
auto rcomma = find(line.crbegin(), line.crend(), ',');

//錯誤:將逆序輸出單詞的字符
cout << string(line.crbegin(), rcomma) << endl;

//正確:得到一個正向迭代器，從逗號開始讀取字符直到line末尾 
cout << string(rcomma.base(), line.cend())<< endl;

圖10.2中的對象顯示了普通迭代器與反向迭代器之間的關系。例如，rcomma和 rcomma.base()指向不同的元素，line.crbegin和 line.cend()也是如此。這些不同保證了元素范圍無論是正向處理還是反向處理都是相同的。

從技術上講，普通迭代器與反向迭代器的關系反映了左閉合區(qū)間的特性。關鍵點在于[line.crbegin()， rcomma)和[rcomma.base(), line.cend()) 指向 line中相同的元素范圍。為了實現這一點，rcomma和rcomma.base()必須生成相鄰位置而不是相同位置，crbegin()和cend ()也是如此。

反向迭代器的目的是表示元素范圍，而這些范圍是不對稱的，這導致一個重要的結果:當我們從一個普通迭代器初始化一個反向迭代器，或是給一個反向迭代器賦值時,結果迭代器與原迭代器指向的并不是相同的元素。

10.5、泛型算法結構

任何算法的最基本的特性是它要求其迭代器提供哪些操作。

• 某些算法，如 find，只要求通過迭代器訪問元素、遞增迭代器以及比較兩個迭代器是否相等這些能力。
• 其他一些算法，如 sort，還要求讀、寫 和 隨機訪問元素的能力。

算法所要求的迭代器操作可以分為5個迭代器類別（iterator category)，如表10.5所示。每個算法都會對它的每個迭代器參數指明須提供哪類迭代器。

第二種算法分類的方式是按照是否 讀、寫 或是 重排序列 中的元素來分類。附錄A按這種分類方法列出了所有算法。
算法還共享一組參數傳遞規(guī)范和一組命名規(guī)范，我們在介紹迭代器類別之后將介紹這些內容。

10.5.1、5類迭代器

類似容器，迭代器也定義了一組公共操作。一些操作所有迭代器都支持，另外一些只有特定類別的迭代器才支持。例如，

• ostream_iterator 只支持遞增、解引用和 賦值。
• vector、string和 deque 的迭代器除了這些操作外，還支持遞減、關系 和 算術運算。

迭代器是按它們所提供的操作來分類的，而這種分類形成了一種層次。除了輸出迭代器之外，一個高層類別的迭代器支持低層類別迭代器的所有操作。

C++標準指明了泛型和數值算法的每個迭代器參數的最小類別。例如，

• find 算法在一個序列上進行一遍掃描，對元素進行只讀操作，因此至少需要輸入迭代器。
• replace 函數需要一對迭代器，至少是前向迭代器。
• 類似的，replace_copy 的前兩個迭代器參數也要求至少是前向迭代器。其第三個迭代器表示目的位置，必須至少是輸出迭代器。
• 其他的例子類似。對每個迭代器參數來說，其能力必須與規(guī)定的最小類別至少相當。向算法傳遞一個能力更差的迭代器會產生錯誤。

注意：對于向一個算法傳遞錯誤類別的迭代器的問題,很多編譯器不會給出任何警告或提示。

迭代器類別

(1)、輸入迭代器（input iterator)：可以讀取序列中的元素。一個輸入迭代器必須支持

• 用于比較兩個迭代器的相等和不相等運算符（ ==、!= )
• 用于推進迭代器的前置和后置遞增運算（++ )
• 用于讀取元素的解引用運算符( * );解引用只會出現在賦值運算符的右側
• 箭頭運算符( -> )，等價于 (*it) .member，即，解引用迭代器，并提取對象的成員

輸入迭代器只用于順序訪問。對于一個輸入迭代器，*it++ 保證是有效的，但遞增它可能導致所有其他指向流的迭代器失效。其結果就是，不能保證輸入迭代器的狀態(tài)可以保存下來并用來訪問元素。因此,輸入迭代器只能用于單遍掃描算法。算法 find 和 accumulate 要求輸入迭代器; 而istream_iterator是一種輸入迭代器。

(2)、輸出迭代器（output iterator):可以看作輸入迭代器功能上的補集——只寫而不讀元素。輸出迭代器必須支持

• 用于推進迭代器的前置和后置遞增運算（ ++ )
• 解引用運算符( * )，只出現在賦值運算符的左側(向一個已經解引用的輸出迭代器賦值，就是將值寫入它所指向的元素)

我們只能向一個輸出迭代器賦值一次。類似輸入迭代器，輸出迭代器只能用于單遍掃描算法。用作目的位置的迭代器通常都是輸出迭代器。例如，copy函數的第三個參數就是輸出迭代器。ostream_iterator類型也是輸出迭代器。

(3)、前向迭代器（forward iterator)：可以讀寫元素。這類迭代器只能在序列中沿一個方向移動。

• 前向迭代器支持所有輸入和輸出迭代器的操作，而且可以多次讀寫同一個元素。因此，我們可以保存前向迭代器的狀態(tài)，使用前向迭代器的算法可以對序列進行多遍掃描。
• 算法replace要求前向迭代器，forward_list上的迭代器是前向迭代器。

(4)、雙向迭代器（bidirectional iterator)：可以正向/反向讀寫序列中的元素。

• 除了支持所有前向迭代器的操作之外，雙向迭代器還支持前置和后置遞減運算符( -- )。
• 算法 reverse 要求雙向迭代器，除了forward_list 之外，其他標準庫都提供符合雙向迭代器要求的迭代器。

(5)、隨機訪問迭代器（random-access iterator)：提供在常量時間內訪問序列中任意元素的能力。

• 此類迭代器支持 雙向迭代器的所有功能，此外還支持表3.7中的操作:

• 用于比較兩個迭代器相對位置的關系運算符( <、<=、> 和 >=)
• 迭代器和一個整數值的加減運算(+、+=、- 和 -=)，計算結果是迭代器在序列中前進（或后退）給定整數個元素后的位置
• 用于兩個迭代器上的減法運算符( - )，得到兩個迭代器的距離
• 下標運算符( iter[n] )，與 *(iter[n])等價

算法 sort 要求隨機訪問迭代器。array、deque、string 和 vector 的迭代器都是隨機訪問迭代器，用于訪問內置數組元素的指針也是。

10.5.2、算法形參模式

在任何其他算法分類之上，還有一組參數規(guī)范。理解這些參數規(guī)范對學習新算法很有幫助——通過理解參數的含義，你可以將注意力集中在算法所做的操作上。大多數算法具有如下4種形式之一:

alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);

其中alg是算法的名字，beg和 end 表示算法所操作的輸入范圍。幾乎所有算法都接受一個輸入范圍，是否有其他參數依賴于要執(zhí)行的操作。這里列出了常見的一種——dest、beg2和 end2，都是迭代器參數。顧名思義，如果用到了這些迭代器參數，它們分別承擔指定目的位置和第二個范圍的角色。除了這些迭代器參數，一些算法還接受額外的、非迭代器的特定參數。

接受單個目標迭代器的算法

• dest參數是一個表示算法可以寫入的目的位置的迭代器。算法假定（assume):按其需要寫入數據，不管寫入多少個元素都是安全的。

向輸出迭代器寫入數據的算法都假定目標空間足夠容納寫入的數據。

• 如果dest是一個直接指向容器的迭代器，那么算法將輸出數據寫到容器中已存在的元素內。
• 更常見的情況是，dest被綁定到一個插入迭代器（參見10.4.1節(jié))或是一個ostream_iterator(參見10.4.2節(jié))。
  • 插入迭代器會將新元素添加到容器中，因而保證空間是足夠的。
  • ostream_iterator會將數據寫入到一個輸出流，同樣不管要寫入多少個元素都沒有問題。

接受第二個輸入序列的算法

接受單獨的beg2或是接受beg2和 end2的算法用這些迭代器表示第二個輸入范圍。這些算法通常使用第二個范圍中的元素與第一個輸入范圍結合來進行一些運算。

• 如果一個算法接受 beg2和 end2，這兩個迭代器表示第二個范圍。這類算法接受兩個完整指定的范圍:[beg,end)表示的范圍和[beg2 end2)表示的第二個范圍。
• 只接受單獨的beg2(不接受end2)的算法將beg2作為第二個輸入范圍中的首元素。此范圍的結束位置未指定，這些算法假定從beg2開始的范圍與beg和 end 所表示的范圍至少一樣大。

接受單獨beg2的算法假定從beg2開始的序列與beg和end所表示的范圍至少一樣大。

10.5.3、算法命名規(guī)范

除了參數規(guī)范，算法還遵循一套命名和重載規(guī)范。這些規(guī)范處理諸如:如何提供一個操作代替默認的 < 或 == 運算符以及算法是將輸出數據寫入輸入序列還是一個分離的目的位置等問題。

一些算法使用重載形式傳遞一個謂詞

接受謂詞參數來代替 < 或 == 運算符的算法，以及那些不接受額外參數的算法, 通常都是重載的函數。

• 函數的一個版本用元素類型的運算符來比較元素;
• 另一個版本接受一個額外謂詞參數，來代替 < 或 ==:

unique(beg, end);			//使用==運算符比較元素
unique(beg, end, comp);		//使用comp比較元素

兩個調用都重新整理給定序列，將相鄰的重復元素刪除。第一個調用使用元素類型的 == 運算符來檢查重復元素; 第二個則調用comp來確定兩個元素是否相等。由于兩個版本的函數在參數個數上不相等,因此具體應該調用哪個版本不會產生歧義(參見6.4節(jié))。

_if 版本的算法

接受一個元素值的算法通常有另一個不同名的(不是重載的)版本，該版本接受一個謂詞(參見10.3.1節(jié))代替元素值。接受謂詞參數的算法都有附加的 _if 前綴:

find(beg, end, val);			//查找輸入范圍中val第一次出現的位置
find_if(beg, end, pred);		//查找第一個令pred為真的元素

• 這兩個算法都在輸入范圍中查找特定元素第一次出現的位置。算法 find 查找一個指定值;算法 find_if 查找使得pred返回非零值的元素。
• 這兩個算法提供了命名上差異的版本，而非重載版本，因為兩個版本的算法都接受相同數目的參數。因此可能產生重載歧義，雖然很罕見，但為了避免任何可能的歧義，標準庫選擇提供不同名字的版本而不是重載。

區(qū)分拷貝元素的版本和不拷貝的版本

默認情況下，重排元素的算法將重排后的元素寫回給定的輸入序列中。這些算法還提供另一個版本，將元素寫到一個指定的輸出目的位置。如我們所見，寫到額外目的空間的算法都在名字后面附加一個 copy（參見10.2.2節(jié)):

reverse(beg, end);					//反轉輸入范圍中元素的順序
reverse_copy(beg, end, dest);		//將元素按逆序拷貝到dest

//一些算法同時提供 _copy 和_if 版本。這些版本接受一個目的位置迭代器和一個謂詞;
//從v1中刪除奇數元素
remove_if(v1.begin(), v1.end ( ),
						[](int i){return i % 2;});
//將偶數元素從v1拷貝到v2;v1不變
remove_copy_if(vl.begin(), v1.end(), back_inserter(v2),
							[](int i) { return i % 2;});

兩個算法都調用了lambda(參見10.3.2節(jié))來確定元素是否為奇數。

• 在第一個調用中，我們從輸入序列中將奇數元素刪除。
• 在第二個調用中，我們將非奇數(亦即偶數)元素從輸入范圍拷貝到 v2 中。

10.6、特定容器算法(list、forward_list)

與其他容器不同，鏈表類型 list 和 forward_list 定義了幾個成員函數形式的算法，如表10.6所示。特別是，它們定義了獨有的 sort、merge、remove、reverse和unique。

通用版本的sort要求隨機訪問迭代器,因此不能用于list和forward_list,因為這兩個類型分別提供雙向迭代器和前向迭代器。

鏈表類型定義的其他算法的通用版本可以用于鏈表，但代價太高。這些算法需要交換輸入序列中的元素。一個鏈表可以通過改變元素間的鏈接而不是真的交換它們的值來快速“交換”元素。因此，這些鏈表版本的算法的性能比對應的通用版本好得多。

對于 list 和 forward_list,應該優(yōu)先使用成員函數版本的算法而不是通用算法。

splice成員

鏈表類型還定義了splice算法,其描述見表10.7。此算法是鏈表數據結構所特有的,因此不需要通用版本。

鏈表特有的操作會改變容器

多數鏈表特有的算法都與其通用版本很相似，但不完全相同。鏈表特有版本與通用版本間的一個至關重要的區(qū)別是鏈表版本會改變底層的容器。例如，

• remove的鏈表版本會刪除指定的元素。
• unique的鏈表版本會刪除第二個和后繼的重復元素。

類似的，merge和 splice會銷毀其參數。例如，

• 通用版本的merge將合并的序列寫到一個給定的目的迭代器;兩個輸入序列是不變的。而鏈表版本的merge函數會銷毀給定的鏈表——元素從參數指定的鏈表中刪除，被合并到調用merge 的鏈表對象中。在merge之后，來自兩個鏈表中的元素仍然存在，但它們都已在同一個鏈表中。

注：僅供學習參考，如有不足，歡迎指正！文章來源地址http://www.zghlxwxcb.cn/news/detail-420745.html

到了這里，關于C++標準庫 -- 泛型算法 (Primer C++ 第五版 · 閱讀筆記)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！