10.1 概述

1. 大多數(shù)算法都定義在頭文件?algorithm?中。標(biāo)準(zhǔn)庫還在頭文件?numeric?中定義了一組數(shù)值泛型算法。

2. 一般情況下，泛型算法不直接操作容器，而是遍歷由兩個(gè)迭代器指定的一個(gè)元素范圍來進(jìn)行操作。通常情況下算法遍歷范圍，對(duì)其中每個(gè)元素進(jìn)行一些處理：

std::vector<int> vec = { 0, 1, 2 };

int val = 1;

auto it = find(vec.cbegin(), vec.cend(), val);

1. 類似的，由于指針就像內(nèi)置數(shù)組上的迭代器一樣，我們可以用?find?在數(shù)組中查找值：

int ia[] = { 0, 1, 2 };

int val = 1;

int * it = find(begin(ia), end(ia), val);

1. 迭代器令算法不依賴于容器，但是算法依賴于元素類型的操作。

2. 泛型算法運(yùn)行于迭代器之上而不會(huì)執(zhí)行容器操作的特性帶來了一個(gè)令人驚訝但非常必要的編程假定：算法永遠(yuǎn)不會(huì)改變底層容器的大小。算法可能改變?nèi)萜髦斜４娴脑氐闹?，也可能在容器之移?dòng)元素，但永遠(yuǎn)不會(huì)直接添加或刪除元素。

3. 標(biāo)準(zhǔn)庫定義了一類特殊的迭代器稱為?插入器(inserter)，當(dāng)給這類迭代器賦值時(shí)，它們會(huì)在底層的容器上執(zhí)行插入操作。因此當(dāng)一個(gè)算法操作插入器時(shí)，插入器可以完成向容器添加元素的效果，但是算法本身永遠(yuǎn)不會(huì)做這樣的操作。

10.2 初識(shí)泛型算法

10.2.1 只讀算法

1. accumulate?將第三個(gè)參數(shù)作為求和起點(diǎn)，這蘊(yùn)含這一個(gè)編程假定：將元素類型加到和的類型上的操作必須是可行的。即序列中的元素的類型必須于第三個(gè)參數(shù)匹配，或者能夠轉(zhuǎn)換為第三個(gè)參數(shù)的類型。

// vec 中的元素可以時(shí) int，或者 double、long double 或者任何其他可以加到 int 上的類型。

int sum = accumulate(vec.cbegin(), vec.cend(), 0);




// 通過第三個(gè)參數(shù)顯示地創(chuàng)建了一個(gè) string。

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




// 將空串當(dāng)作一個(gè)字符串字面值傳遞給第三個(gè)參數(shù)是不可以的。

// 因?yàn)榇藭r(shí)保存和的對(duì)象類型將是 const char*，但 const char* 沒有 +運(yùn)算符。

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

1. equal?算法利用迭代器完成操作，因此可以通過調(diào)用?equal?來比較兩個(gè)不同類型的容器中的元素（例如比價(jià)?vector?和?list?兩個(gè)容器中的元素）。而且，容器中的元素類型也不必一樣，只要能用?==?運(yùn)算符來比較這兩個(gè)元素類型即可（例如比較?int?和?double?類型）。

2. 那些只接受一個(gè)單一迭代器來表示第二個(gè)序列的算法，都假定第二個(gè)序列至少于第一個(gè)序列一樣長(zhǎng)。

// 第三個(gè)參數(shù)接受一個(gè)單一的迭代器，roster2中的元素?cái)?shù)目應(yīng)至少與roster1一樣多

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

10.2.2 寫容器元素的算法

1. 一些算法從兩個(gè)序列中讀取元素。構(gòu)成這兩個(gè)序列的元素可以來自于不同類型的容器。而且兩個(gè)序列中元素的類型也不要求嚴(yán)格匹配，算法要求的只是能夠比較兩個(gè)序列中的元素。

2. 向目的的位置迭代器寫入數(shù)據(jù)的算法假定目的位置足夠大，能容納要寫入的元素。

3. 一種保證算法有足夠的元素空間來容納輸出數(shù)據(jù)的方法是使用?插入迭代器（insert iterator）。它是一種向容器中添加元素的迭代器，當(dāng)我們通過它來賦值時(shí)，一個(gè)與賦值號(hào)右側(cè)值相等的元素被添加到容器中。

vector<int> vec;

// 使用普通迭代器

fill_n(vec.begin(), 10, 0); // 錯(cuò)誤：修改 vec 中的10個(gè)（不存在）元素




// 使用插入迭代器

auto it = back_inserter(vec);

*it = 42; ? ? ? ? ? ? ? ? ? // 等價(jià)于 vec.push_back(42);

fill_n(it, 10, 0); ? ? ? ? ?// 給vec的尾部添加10個(gè)0（每次賦值都會(huì)在vec上調(diào)用push_back）

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

replace(ilst.begin(), ilst.end(), 0, 42); ? // 將ilst中所有0替換成42




// 如果希望保留原序列不變，可以調(diào)用其 “拷貝” 版本

// 此調(diào)用后ilst并未改變，ivec包含ilst的一份拷貝

// 不過原來在ilst中值為0的元素在ivec中都變?yōu)榱?2

replace(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

10.3 定制操作

10.3.1 向算法傳遞函數(shù)

1. 謂詞?是一個(gè)可調(diào)用的表達(dá)式，其返回結(jié)果是一個(gè)能用作條件的值。一元謂詞 (unary predicate)?只接受單一參數(shù)，二元謂詞 (binary predicate)?意味著它們有兩個(gè)參數(shù)。

10.3.2?lambda?表達(dá)式

1. 一個(gè)?lambda?表達(dá)式表示一個(gè)可調(diào)用的代碼單元，我們可以將其理解為一個(gè)未命名的內(nèi)聯(lián)函數(shù)。

// 與普通函數(shù)不同，lambda必須使用尾置返回

auto func = [capture list](parameter list) -> return type { fuction body }

1. 我們可以忽略參數(shù)列表和返回類型，但是必須永遠(yuǎn)包含捕獲列表和函數(shù)體。

2. 如果?lambda?的函數(shù)體包含任何單一?return?語句之外的內(nèi)容，且未指定返回類型，則返回?void。

3. 與普通函數(shù)不同，lambda?不能有默認(rèn)參數(shù)，一個(gè)?lambda?調(diào)用的實(shí)參數(shù)目永遠(yuǎn)與形參數(shù)目相等。

// 忽略括號(hào)和參數(shù)列表等價(jià)于指定一個(gè)空參數(shù)列表

// 忽略返回類型，lambda根據(jù)函數(shù)體中的代碼推斷出返回類型

auto func = [] { return 42; } ? // 返回類型為int




// 編譯器推斷這個(gè)版本返回類型為void，但是它返回了一個(gè)int類型

auto func1 = [] { int a = 0; return a; } ? ?




// 使用了尾置返回類型，可以返回一個(gè)int類型

auto func2= [] -> int { int a = 0; return a; }

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

10.3.3?lambda?捕獲和返回

1. 當(dāng)定義一個(gè)?lambda?時(shí)，編譯器生成一個(gè)與?lambda?對(duì)應(yīng)的新的（未命名的）類類型。

2. 與傳值參數(shù)類似，采用值捕獲的前提是變量可以拷貝。與參數(shù)不同，被捕獲的變量的值是在?lambda?創(chuàng)建時(shí)拷貝，而不是調(diào)用時(shí)拷貝。

3. 引用捕獲和返回引用有著相同的問題和限制。如果采用引用方式捕獲一個(gè)變量，就必須確保被引用的對(duì)象在?lambda?執(zhí)行的時(shí)候是存在的。

4. lambda?捕獲的都是局部變量，這些變量在函數(shù)結(jié)束就不復(fù)存在了。如果?lambda?可能在函數(shù)結(jié)束后執(zhí)行，捕獲的引用指向的局部變量已經(jīng)消失。

5. 如果函數(shù)返回一個(gè)?lambda, 則于函數(shù)不能返回一個(gè)局部變量的引用類似，此?lambda?不能包含引用捕獲。

6. 當(dāng)混合使用隱式捕獲和顯示捕獲時(shí)，顯示捕獲的變量必須使用于隱式捕獲不同的方式。

7. 默認(rèn)情況下，對(duì)于一個(gè)值拷貝的變量，lambda不會(huì)改變其值。如果我們希望能改變一個(gè)被捕獲的變量的值，就必須在參數(shù)列表首加上關(guān)鍵字?mutable。

int v1 = 42;

auto f = [v1]() mutable { return ++v1; };

10.3.4 參數(shù)綁定

1. 可以將?bind?函數(shù)看作一個(gè)通用的函數(shù)適配器，它接受一個(gè)可調(diào)用對(duì)象，生成一個(gè)新的可調(diào)用對(duì)象來“適應(yīng)”原對(duì)象的參數(shù)列表。

auto newCallable = bind(callable, arg_list);

1. arg_list?中的參數(shù)可能包含形如?_n?的名字，其中?n?是一個(gè)整數(shù)。這些參數(shù)是“占位符”，它們占據(jù)了傳遞給?newCallable?的參數(shù)的“位置”，數(shù)值?n?表示生成的可調(diào)用對(duì)象中的位置。

2. 使用?_n?之前要先定義命名空間：using namespace std::placeholders;

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

auto check = bind(check_size, _1, 6);

string s = "hello";

bool b1 = check(s); ? ? // 會(huì)調(diào)用 check_size(s, 6)

1. 使用?bind?可以將原來基于?lambda?的find_if調(diào)用替換為使用?check_size?的版本。

auto wc = find_if(words.begin(), word.end(), [sz](const string& a){...});

auto wc = find_if(words.begin(), word.end(), bind(check_size, _1, sz));

1. 可以使用?bind綁定給定可調(diào)用對(duì)象中的參數(shù)或重新安排其順序。

// g是一個(gè)有兩個(gè)參數(shù)的可調(diào)用對(duì)象

auto g = bind(fcn, a, b, _2, c, _1);

// 等價(jià)調(diào)用

g(X, Y);

f(a, b, Y, c, X);

1. 如果我們希望傳遞給?bind?一個(gè)對(duì)象而又不拷貝它，就必須使用標(biāo)準(zhǔn)庫?ref?函數(shù)。

for_each(word.begin(), word.end(), bind(print, os, _1, ' ')); ? // 錯(cuò)誤，不能拷貝ostream

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

10.4 再探迭代器

1. 插入迭代器（insert iterator）：被綁定到一個(gè)容器上，用來向容器插入元素。

2. 流迭代器（stream iterator）：被綁定到輸入或輸出流上，可用來遍歷所關(guān)聯(lián)的IO流。

3. 反向迭代器（reverse iterator）：向后而不向前移動(dòng)的迭代器，除了?forward_list?之外的標(biāo)準(zhǔn)庫容器都有反向迭代器。

4. 移動(dòng)迭代器（move iterator）：這些專用的迭代器不是拷貝其中的元素，而是移動(dòng)它們。

10.4.1 插入迭代器

1. 插入器是一種迭代器適配器，它接受一個(gè)容器，生成一個(gè)迭代器，能實(shí)現(xiàn)向給定容器添加元素。

2. 插入器有三種：back_inserter、front_inserter?和?inserter。

10.4.2?iostream?迭代器

1. istream_iterator讀取輸入流，ostream_iterator?向一個(gè)輸出流寫數(shù)據(jù)。我們可以為任何定義了輸入運(yùn)算符（>>）或輸出運(yùn)算符（<<）的類型創(chuàng)建?istream_iterator?或?ostream_iterator?對(duì)象。

istream_iterator<int> in_iter(cin), eof; ? // 從cin讀取int, eof為尾后迭代器

vector<int> vec(in_iter, eof); ? ? ? ? ? ? // 從迭代器范圍構(gòu)造vec

1. `istream_iterator 允許使用?懶惰求值。

2. 對(duì)于ostream_iterator<T> out(os)，*out, ++out, out++?這些運(yùn)算符是存在的，但是不對(duì)?out?做任何事情。每個(gè)運(yùn)算符都返回?out。

10.4.3 反向迭代器

1. 不能從一個(gè)?forward_list?或一個(gè)流迭代器創(chuàng)建反向迭代器。

2. 通過調(diào)用?reverse_iterator?的?base?成員函數(shù)返回其對(duì)應(yīng)的普通迭代器（迭代器指向的位置會(huì)往后移動(dòng)一個(gè)位置）。

3. 普通迭代器與反向迭代器的關(guān)系反映了左閉合區(qū)間。

4. 反向迭代器的目的是表示元素范圍，而這些范圍是不對(duì)稱的，這導(dǎo)致一個(gè)重要的結(jié)果：當(dāng)從一個(gè)普通迭代器初始化一個(gè)反向迭代器，或是給一個(gè)反向迭代器賦值時(shí)，結(jié)果迭代器于原迭代器指向的并不是相同的元素，而是相鄰的位置。

10.5 泛型算法結(jié)構(gòu)

1. 輸入迭代器（input iterator）、輸出迭代器（output iterator）、前向迭代器（forward iterator）、雙向迭代器（bidirectional iterator）、隨機(jī)訪問迭代器（random-access iterator）。

10.5.1 5類迭代器

1. 對(duì)于向一個(gè)算法傳遞錯(cuò)誤類別的迭代器的問題，很多編譯器不會(huì)給出任何警告或提示。

2. 對(duì)于一個(gè)?輸入迭代器，*it++?保證是有效的，但是遞增它可能導(dǎo)致所有其他指向流的迭代器失效。其結(jié)果是不能保證?輸入迭代器?的狀態(tài)可以保存下來并用來訪問元素。因此?輸入迭代器?只能用于單遍掃描算法。

3. 只能向一個(gè)?輸出迭代器?賦值一次，輸出迭代器?只能用于單遍掃描算法。用作目的位置的迭代器通常都是?輸出迭代器。

4. 前向迭代器?支持所有的輸入和輸出迭代器的操作，而且可以多次讀寫同一個(gè)元素，算法可以對(duì)序列進(jìn)行多遍掃描。

5. 隨機(jī)訪問迭代器?提供在常量時(shí)間內(nèi)訪問序列中任意元素的能力。

10.5.2 算法形參模式

alg(beg, end, other args);

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

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

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

1. dest參數(shù)是一個(gè)表示算法可以寫入的目的位置的迭代器。向輸出迭代器寫入數(shù)據(jù)的算法都假定目標(biāo)空間足夠容納寫入的數(shù)據(jù)。

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

10.5.3 算法命名規(guī)范

1. 一些算法使用重載形式傳遞一個(gè)謂詞

unique(beg, end); ? ? ? ? ? // 使用 == 運(yùn)算符比較元素

unique(beg, end, comp); ? ? // 使用 comp 比較元素

1. _if?版本的算法：接受謂詞參數(shù)的算法都有附加的?_if?前綴。

find(beg, end, value); ? ? ?// 查找輸入范圍中 value 第一次出現(xiàn)的位置

find(beg, end, pred); ? ? ? // 查找第一個(gè)令 pred 為真的元素

1. 區(qū)分拷貝元素的版本和不拷貝的版本。寫到額外目的空間的算法都在名字后面附加一個(gè)?_copy

reverse(beg, end); ? ? ? ? ? ? ?// 反轉(zhuǎn)輸入范圍中元素的順序

reverse_copy(beg, end, dest); ? // 將元素按逆序拷貝到 dest

1. 一些算法同時(shí)提供?_copy?和?_if?版本。

// 從v1中刪除奇數(shù)元素

remove_if(v1.begin(), v1.end(), [](int i){ return i % 2; });




// 將偶數(shù)元素從 v1 拷貝到 v2 ，v1不變

remove_if(v1.begin(), v1.end(), back_inserter(v2),

? ? ? ? ? [](int i){ return i % 2; });

10.6 特定容器算法

1. 對(duì)于?list?和?forward_list，應(yīng)該優(yōu)先使用成員函數(shù)版本的算法而不是通用算法。

2. 鏈表特有的操作會(huì)改變?nèi)萜鳌?/p>