---

概念

一般情況下，泛型算法本身不會執行容器的操作，它們只會運行于迭代器之上，執行迭代器的操作。

泛型算法的一大優點是 “泛型”，也就是一個算法可用于多種不同的數據類型，算法與所操作的數據結構分離。這對編程效率的提高是非常巨大的。

要做到算法與數據結構分離，重要的技術手段就是使用迭代器作為兩者的橋梁。算法從不操作具體的容器，從而也就不存在與特定容器綁定，不適用于其他容器的問題。算法只操作迭代器，由迭代器真正實現對容器的訪問。不同容器實現自己特定的迭代器（但不同迭代器是相容的），算法操作不同迭代器就實現了對不同容器的訪問。

因此，并不是算法應該改變或不該改變容器的問題。 為了實現與數據結構的分離，為了實現通用性，算法根本就不該知道容器的存在。 算法訪問數據的唯一通道是迭代器。是否改變容器大小，完全是迭代器的選擇和責任。

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

---

find()函數

以find()函數為例來理解。傳遞給find的前兩個參數是表示元素范圍的迭代器，第三個參數是一個值。find將范圍中每個元素與給定值進行比較。它返回指向第一個等于給定值的元素的迭代器。如果范圍中無匹配元素，則find返回第二個參數來表示搜索失敗。因此，我們可以通過比較返回值和第二個參數來判斷搜索是否成功。

由于指針就像內置數組上的迭代器，因此我們也可以用find在數組中查找值：

---

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

在find函數流程中，除了比較大小外，其他步驟都可以用迭代器操作來實現：

1. 利用迭代器解引用運算符可以實現元素訪問；
2. 如果發現匹配元素，find可以返回指向該元素的迭代器；
3. 用迭代器遞增運算符可以移動到下一個元素；
4. 尾后迭代器可以用來判斷find是否到達給定序列的末尾；
5. find可以返回尾后迭代器來表示未找到給定元素。

---

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

雖然迭代器的使用令算法不依賴于容器類型，但大多數算法都使用了一個（或多個）元素類型上的操作。 例如，find用元素類型的==運算符完成每個元素與給定值的比較。不過，我們將會看到，大多數算法提供了一種方法，允許我們使用自定義的操作來代替默認的運算符。

---

算法永遠不會執行容器的操作

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

---

---

只讀算法

一些算法只會讀取其輸入范圍內的元素，但不改變元素。
例如下面這三個：

• find()
• count()：接收一對迭代器和一個值作為參數，返回給定值在序列中出現的次數。

---

accumulate()函數

定義在頭文件numeric中。接受三個參數，前兩個指出需要求和的元素的范圍，第三個參數時和的初值，其類型決定了函數中使用哪個加法運算符以及返回值的類型（這也就要求序列中元素的類型必須與第三個參數匹配，或者能夠轉換為第三個參數的類型）。

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

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

此調用將v中每個元素連接到一個string上，該string初始時為空串。注意，我們通過第三個參數顯式地創建了一個string。如果單純將空串當做一個字符串字面值傳遞給第三個參數是不可以的，會導致一個編譯錯誤。

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

原因在于，如果我們傳遞了一個字符串字面值，用于保存和的對象的類型將是const char*。如前所述，此類型決定了使用哪個+運算符。由于const char*并沒有+運算符，此調用將產生編譯錯誤。

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

---

從兩個序列中讀取元素（equal函數為例）

迭代器作為參數形成兩個序列

一些算法從兩個序列中讀取元素。構成這兩個序列的元素可以來自于不同類型的容器。兩個序列中元素的類型也不要求嚴格匹配。算法要求的只是能夠比較兩個序列中的元素。

操作兩個序列的算法之間的區別在于我們如何傳遞第二個序列。 一些算法接受三個迭代器：前兩個表示第一個序列的范圍，第三個表示第二個序列中的首元素。 其他算法接受四個迭代器：前兩個表示第一個序列的元素范圍，后兩個表示第二個序列的范圍。

用一個單一迭代器表示第二個序列的算法都假定第二個序列至少與第一個一樣長。確保算法不會試圖訪問第二個序列中不存在的元素是程序員的責任。

---

equal()

equal()：用于確定兩個序列是否保存相同的值。它將第一個序列中的每個元素與第二個序列中的對應元素進行比較。如果所有對應元素都相等，則返回true，否則返回false。 此算法接受三個迭代器：前兩個表示第一個序列中的元素范圍，第三個表示第二個序列的首元素（第二個序列中的元素數目應大于等于第一個序列）。

根據上面的概念，我們可以比較不同容器中不同的元素類型，只要兩者能通過“ == ” 進行比較即可，因此，兩個序列可以是vector和list<const char*>。

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

---

---

寫容器元素的算法

概念

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

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

但是有一些算法接受一個迭代器和一個計數值來劃定范圍，然后寫入元素。這種算法假定目的位置足夠大，能容納要寫入的元素，也就是說算法不檢查寫操作。檢查目標輸入序列是否為空是程序員的責任，對空容器調用這些算法得到的結果是未定義的（但是可以通過back_insert()，來實現對空容器的操作）。

分別以 fill() 和 fill_n() 為例來探究：

fill()

接受一對迭代器表示一個范圍，還接受一個值作為第三個參數。將給定值賦予序列中的每個元素。

給定范圍有效：

給定范圍越界：

給定容器為空：

---

fill_n()

fill_n接受一個單迭代器、一個計數值和一個給定值。他將給定值賦予迭代器指向的元素開始的計數值個元素。

給定范圍有效：

給定范圍越界：

給定容器為空：

---

插入迭代器back_inserter

• 是定義在頭文件iterator中的一個函數。
• 是一種保證算法有足夠元素空間來容納輸出數據的方法
• 是一種向容器中添加元素的迭代器。
• 接受一個指向容器的引用，返回一個與該容器綁定的插入迭代器。
• 當我們通過此迭代器賦值時，賦值運算符會調用push_back將一個具有給定值的元素添加到容器中。

實例：

也可以使用back_inserter來創建一個迭代器，作為算法的目的位置來使用：

這樣可以避免對空容器操作的未定義行為。具體實現：

在每步迭代中，fill_n向給定序列的一個元素賦值。由于我們傳遞的參數是back_inserter返回的迭代器，因此每次賦值都會在vc上調用push_back（是向空容器添加元素，而不再是簡簡單單的對空容器的元素賦值這一未定義行為）。最終，這條fill_n調用語句向vec的末尾添加了10個元素，每個元素的值都是0。

當我們向fill_n傳遞back_inserter時，雖然最終效果是向容器添加了新的元素，但對fill_n來說，根本不知道這回事兒。它仍然像往常一樣（通過迭代器）向元素賦予新值，只不過這次是通過back_inserter來賦值，而back_inserter選擇將新值添加到了容器而已。

插入迭代器是否與“標準庫算法不會改變它們所操作的容器的大小”相悖

嚴格來說，標準庫算法根本不知道有“容器”這個東西。它們只接受迭代器參數，運行于這些迭代器之上，這些迭代器只能順序或隨機訪問容器中的元素，造成的效果就是算法只能讀取元素、改變元素值、移動元素，但無法添加或刪除元素。

但當我們傳遞給算法插入器，例如back_inserter時，由于這類迭代器能調用下層容器的操作（如push_back）來向容器插入元素，造成的算法執行的效果就是向容器中添加了元素。

因此，關鍵要理解：標準庫算法從來不直接操作容器，它們只操作迭代器，從而間接訪問容器。能不能插入和刪除元素，不在于算法，而在于傳遞給它們的迭代器是否具有這樣的能力。

---

拷貝（copy）算法

拷貝算法是另一個向目的位置迭代器指向的輸出序列中的元素寫入數據的算法。

• 接受三個迭代器，前兩個迭代器設置范圍，第三個表示目標序列的起始位置。
• 將前兩個迭代器劃定的輸入范圍中的元素拷貝到第三個迭代器指定的目標序列中。
• 后面的序列必須能容納前面的元素

可以實現內置數組的拷貝：

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

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

也可用來實現不改變原序列值的目的：

多個算符都提供“拷貝”版本。計算新元素的值，但不會將它們放置在輸入序列的末尾，而是創建一個新序列保存這些結果。以replace算法為例：

replace算法

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

此算法接受4個參數：

• 前兩個是迭代器，表示輸入序列；
• 后兩個一個是要搜索的值；
• 另一個是新值。它將所有等于第一個值的元素替換為第二個值。

replace(vc.begin(), vc.end(), 0, 2); // 將序列中所有0都替換為2

如果我們希望保留原序列不變，可調用replace_copy。該算法接受額外第三個迭代器參數，指出調整后序列的保存位置：

replace_copy(vc.cbegin(), vc.cend(), back_inseret(ivec), 0, 2);

調用后，vc未改變，ivec包含vc的一份拷貝，ivec中原vc對應位置的0都變為2。

---

這里的容器大小指的是元素數量

舉個例子：

即使我們用reserve分配了至少能容納10個int的內存空間。但調用fill_n的行為仍然是未定義的。

這是因為泛型算法對于容器的要求并不是有足夠的空間，而是足夠的元素數量。

而reserve調整的是capacity的值，而非size的值（下面兩圖），換言之，此時vc依然為空，沒有任何元素。而算法又不具備向容器添加元素的能力， 因此fill_n仍然失敗。

---

---

定制操作

上面說過，sort算法默認使用元素類型的<運算符。但我們可能遇見下列情況：

• 我們希望的排序順序與<所定義的順序不同
• 序列可能保存的是未定義<運算符的元素類型

這時就需要重載sort的默認行為。

謂詞

謂詞是一個可調用的表達式，返回結果是一個能用做條件的值。

標準庫算法使用的謂詞分為兩類：一元謂詞（只接受單一參數）和二元謂詞（有兩個參數）。接受謂詞參數的算法對輸入序列中的元素調用謂詞。因此，元素類型必須能轉換為謂詞的參數類型。

實例：
按照string的<運算符排序：

使單詞按照長度排序，相同長度的單詞按照字典序排列：

stable

帶有stable的函數可保證相等元素的原本相對次序在排序后保持不變。

實例，找出vector<string>內長度大于等于5的元素：

partition有時會打亂原有相對次序:

stable_partition會在排序的基礎上盡量維持原來的相對次序:

---

可調用對象

可以向一個算法傳遞任何類別的可調用對象。

可調用：對于一個對象或一個表達式，如果可以對其使用調用運算符——（），則稱它為可調用的。

可調用對象有四種：

1. 函數
2. 函數指針
3. 重載了函數調用運算符的類
4. lambda表達式

---

lambda表達式

概念

有時我們希望進行的操作需要更多的參數，以至于超出了算法對為此的限制（二元謂詞無法滿足需求）。此時就可以使用lambda表達式。

一個lambda表達式表示一個可調用的代碼單元。我們可以將其理解為一個未命名的內聯函數。

與任何函數類似，一個lambda具有一個返回類型、一個參數列表和一個函數體。 但與函數不同，lambda可能定義在函數內部。一個lambda表達式具有如下形式：

• capture list（捕獲列表）是一個lambda所在函數中定義的局部變量的列表（通常為空）；
• return 表示返回類型。
• parameter list表示參數列表。
• function body表示函數體。
• 與普通函數不同，lambda必須使用尾置返回來指定返回類型。
• 我們可以忽略參數列表和返回類型，但必須永遠包含捕獲列表和函數體。
• lambda的調用方式與普通函數的調用方式相同，都是使用調用運算符。
• lambda不能有默認實參。換言之，調用的實參數目永遠與形參數目相等。
• lambda表達式之間不能相互賦值，即使看起來類型相同。

在lambda中忽略括號和參數列表等價于指定一個空參數列表。

關于返回類型：

• 如果忽略返回類型，lambda根據函數體中的代碼推斷出返回類型。
• 如果函數體只是一個return語句，則返回類型從返回的表達式的類型推斷而來。
• 如果包含任何單一return語句之外的內容，則返回類型為void，此時lambda不能返回值。（C++11）

一個僅忽略返回類型的實例：

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

空捕獲列表表明此lambda不使用它所在函數中的任何局部變量。

一個lambda表達式表示一個可調用的代碼單元。我們可以將其看為一個未命名的內聯函數：

---

原理

當定義了lambda表達式之后，編譯器按照仿函數的形式自動生成一個lamber_uuid類（本質還是未命名的），并重載其中的operator()，當用戶進行調用的時候會自動通過該類的匿名對象來調用，使得其看起來和普通的函數一樣。

當向一個函數傳遞一個lambda時，同時定義了一個新類型和該類型的一個對象：傳遞的參數就是此編譯器生成的類類型的未命名對象。類似的，當使用auto定義一個用lambda初始化的變量時，定義了一個從lambda生成的類型的對象。

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

---

捕獲列表

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

捕獲列表允許的形式:

下面我們通過實例來詳細了解：

find_if

用find_if尋找vs中長度大于5的元素。

find_if返回一個迭代器，指向第一個長度不小于給定參數的元素。如果這樣的元素不存在，返回尾后迭代器的拷貝。

for_each

通過for_each算法來打印find_if找到的符合要求的元素。

接受一個可調用對象，并對輸入序列中每個元素調用此對象。

捕獲方式

值捕獲

采用值捕獲的前提是變量可以拷貝。與傳值參數不同的是，被捕獲的變量的值是在lambda創建時拷貝，而不是調用時拷貝：

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

mutable

默認情況下，lambda函數總是一個const函數，mutable可以取消其常量性。使用該修飾符時，參數列表不可省略(即使參數為空)。

如果我們希望能改變一個被捕獲的變量的值，必須在參數列表首加上關鍵字mutable。 但是由于上面的被捕獲變量的值是在創建lambda時拷貝的，因此在lambda表達式內修改變量值也不會影響值本身：

---

引用捕獲

在lambda函數體內使用引用捕獲的變量時，實際上使用的是引用所綁定的對象。

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

修改引用捕獲的變量

引用捕獲是否可以修改依賴于引用指向的是否是一個const類型。在lambda表達式內修改引用捕獲同樣會導致變量改變：

---

隱式捕獲

隱式捕獲：通過在捕獲列表中寫一個&或者=指示編譯器推斷捕獲列表，=表示采用值捕獲，&表示采用引用捕獲。

// st為隱式捕獲，方式為值捕獲
auto f = [=]{return st;};

也可以混用隱式捕獲和顯示捕獲，但列表中第一個元素必須是一個&或者=，指定隱式捕獲方式為引用或值，且顯式捕獲的變量必須用與隱式捕獲不同的方式（顯式為引用捕獲隱式必須為值捕獲，反之亦然）：

int st,c;auto f1 = [=, &c]{return st + c;}; // st隱式、值捕獲；c顯式、引用捕獲
auto f2 = [&, st]{return st + c;}; // c隱式、引用捕獲；st顯式、值捕獲

---

function模板

概念

C++中可調用對象(如函數指針，仿函數，lambda表達式等)的雖然都有一個比較統一的操作形式，但是定義方法五花八門，這樣就導致使用統一的方式保存可調用對象或者傳遞可調用對象時，會十分繁瑣。C++11中提供了std::function和std::bind統一了可調用對象的各種操作。

例如：

// 普通函數
int add(int a, int b){return a+b;} // lambda表達式
auto mod = [](int a, int b){ return a % b;}// 仿函數
struct divide{int operator()(int denominator, int divisor){return denominator/divisor;}
};

上面的幾種不同的可調用對象雖然類型不同，但是根據參數和返回值可以共享同一種調用形式int(int ,int)，通過function就可以統一其調用形式：

std::function<int(int ,int)>  a = add; 
std::function<int(int ,int)>  b = mod ; 
std::function<int(int ,int)>  c = divide(); 

定義格式：std::function<返回值（參數列表）> 名字

• std::function 是一個可調用對象包裝器，是一個類模板，可以容納除了類成員函數指針之外的所有可調用對象，它可以用統一的方式處理函數、函數對象、函數指針，并允許保存和延遲它們的執行。
• std::function可以取代函數指針的作用，因為它可以延遲函數的執行，特別適合作為回調函數使用。它比普通函數指針更加的靈活和便利。

---

function與重載函數

在使用function的時候還有一個需要注意的點，就是我們不能將重載過的函數直接放入function對象中，因為會有二義性的問題。

例如：

int add(int x, int y);
double add(double x, double y);map<string, function<int(int, int)>> map;
map.insert({"+", add});//此時無法判斷是哪個add//所以此時就不能直接使用函數名進行插入
//可以通過使用函數指針來指向對應函數，再通過函數指針插入來消除二義性
int (*func)(int, int) = add;
map.insert({"+", func});

---

---

bind函數

概念

定義在functional中。相當于一個通用的函數適配器。

調用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為第二個參數，依此類推。

使用placeholders名字

名字_n都定義在一個名為placeholders的命名空間中，這個命名空間本身定義在std命名空間。

為了使用_1我們必須做出以下聲明：

using std::placeholders::_1

說明_1定義在命名空間placeholders中，而placeholders又定義在命名空間std中。

這樣寫也有弊端：我們必須為每個_n提供單獨的using聲明，太過繁瑣。 因此我們可以使用另外一種形式：

using namespace namespace_name;

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

因此我們可以使用下面這兩種形式：

using namespace std::placeholders;using namespace std;
using namespace placeholders;

與bind函數一樣，placeholders命名空間也定義在functional頭文件中。

---

作用

削減參數數量

函數作為可調用對象，lambda表達式能出現的地方函數也可以。但問題是算法要求一元謂詞，函數的形參大于一個怎么辦？lambda可以通過捕獲列表解決一元謂詞的限制。函數可以通過bind函數適配器削減參數數量。

還是以之前find_if函數為例：

我們可以通過形如這樣的函數起到lambda表達式的作用：

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

但是由于find_if接受一個一元謂詞，因此傳遞給find_if的可調用對象必須接受單一參數。check_size接受兩個參數顯然不符合要求。那么怎么解決呢？lambda將sz放入捕獲列表，check_size可以使用bind函數，用一個定值作為其大小參數來調用check_size：

auto check5 = bind(check_size, _1, 5);
// _1形式亦可寫為placeholders::_1
// 前者需要添加語句 using namespace placeholders;

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

將原來基于lambda的find_if調用替換為使用bind的版本：

bool check_size(const string& s, string::size_type sz){return s.size() >= sz;
}int main(int argc, char const *argv[]) {vector<string> vs = {"daa","bbasdf","ccccc","dddd","aebbbb"};sort(vs.begin(), vs.end(), isshorter);auto check5 = bind(check_size,  placeholders::_1, 5);auto flag = find_if(vs.begin(), vs.end(), check5);for_each(flag, vs.end(),[](const string& s){cout << s << " ";});cout << endl;
}

輸出結果：

---

重排參數順序

bool isshorter(const string& s1, const string& s2){return s1.size() < s2.size();
}

按單詞長度由短至長排序：

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類似，有時對有些綁定的參數我們希望以引用方式傳遞，或是要綁定參數的類型無法拷貝。

我們想用函數替換下面lambda表達式：

ostream& os = cout;
for_each(flag, vs.end(),[&os](const string& s) {os << s << " ";});

目標功能函數：

ostream &print(ostream & os, const string&s){return os << s;
}

如果要用它替換lambda就必須用到bind：

ostream &os(cout);
for_each(flag, vs.end(), bind(print, os, _1));

但是這樣做是錯誤的，我們說，bind拷貝參數列表給返回的可調用對象，ostream是不能拷貝的。 如果希望傳遞給bind一個對象而又不拷貝它，就必須使用標準庫ref函數：

for_each(flag, vs.end(), bind(print, ref(os), _1));

值得一提的是， 在編譯器中對ostream的引用不加ref是不報錯的，但是不能運行。換言之，檢查某個參數bind能否拷貝是程序員的責任。

函數ref返回一個對象，包含給定的引用。返回的對象是可拷貝的。

類似的還有cref函數，生成一個保存const引用的類。

與bind一樣，函數ref和cref也定義在頭文件functional中。

---

---

泛型算法結構——迭代器類別

概念

算法分類方式可以如同一開始所寫那樣，分為：是否讀、寫或者是重排序類中的元素。

也可以從迭代器入手進行分類：

不同的算法要求其迭代器提供的操作不同。某些算法，如find，只要求通過迭代器訪問元素、遞增迭代器以及比較兩個迭代器是否相等這些能力。其他一些算法，如sort，還要求讀、寫和隨機訪問元素的能力。算法所要求的迭代器操作可以分為5個迭代器類別（iterator category），每個算法都會對它的每個迭代器參數指明須提供哪類迭代器。

---

不太重要的概念

類似容器，迭代器也定義了一組公共操作。一些操作所有迭代器都支持，另外一些只有特定類別的迭代器才支持。 例如，ostream_iterator只支持遞增、解引用和賦值。vector、string和deque的迭代器除了這些操作外，還支持遞減、關系和算術運算。

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

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

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

---

迭代器類別

輸入迭代器

輸入迭代器（input iterator）：只讀，不寫；單遍掃描，只能遞增。 一個輸入迭代器必須支持：

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

輸入迭代器只用于順序訪問。 對于一個輸入迭代器，*it++保證是有效的，但遞增它可能導致所有其他指向流的迭代器失效（私以為也就是值被讀取出來了，其他指向流的迭代器指向的元素沒有了，就會導致它們失效）。其結果就是，不能保證輸入迭代器的狀態可以保存下來并用來訪問元素。因此，輸入迭代器只能用于單遍掃描算法。（私以為類似于輸入流沒法被讀取第二次。） 算法find和accumulate要求輸入迭代器；而istream_iterator是一種輸入迭代器。

---

輸出迭代器

輸出迭代器（output iterator）：只寫而不讀元素；單遍掃描，只能遞增。 輸出迭代器必須支持：

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

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

---

前向迭代器

前向迭代器（forward iterator）：可以讀寫元素；多遍掃描，只能遞增。這類迭代器只能在序列中沿一個方向移動。

• 支持所有輸入和輸出迭代器的操作
• 可以多次讀寫同一個元素
• 可以保存前向迭代器的狀態

算法replace要求前向迭代器。forward_list上的迭代器是前向迭代器。

---

雙向迭代器

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

• 支持所有前向迭代器的操作
• 支持前置和后置遞減運算符（–）

算法reverse要求雙向迭代器。除了forward_list之外，其他標準庫都提供符合雙向迭代器要求的迭代器。

---

隨機訪問迭代器

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

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

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

---

---

算法的命名規范

_if版本的算法

接受一個元素值的算法通常有另一個不同名的（不是重載的）版本，該版本接受一個謂詞代替元素值。 接受謂詞參數的算法都有附加的_if前綴：

這兩個算法都在輸入范圍中查找特定元素第一次出現的位置。算法find查找一個指定值；算法find_if查找使得pred返回非零值的元素。

這兩個算法提供了命名上差異的版本，而非重載版本，因為兩個版本的算法都接受相同數目的參數，因此可能產生重載歧義。 雖然很罕見，但為了避免任何可能的歧義，標準庫選擇提供不同名字的版本而不是重載。

---

_copy版本的算法

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

一些算法同時提供_copy和_if版本。這些版本接受一個目的位置迭代器和一個謂詞：

兩個算法都調用了lambda（參見10.3.2節，第346頁）來確定元素是否為奇數。在第一個調用中，我們從輸入序列中將奇數元素刪除。在第二個調用中，我們將非奇數（亦即偶數）元素從輸入范圍拷貝到v2中。

---

---

list和forward_list獨有的算法

概念

與其他容器不同，鏈表類型list和forward_list定義了幾個成員函數形式的算法。例如，它們定義了獨有的sort、merge、remove、reverse和unique。通用版本的sort要求隨機訪問迭代器，因此不能用于list和forward_list，因為這兩個類型分別提供雙向迭代器和前向迭代器。

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

---

鏈表數據結構特有的splice算法

沒有通用版本。

多數鏈表特有的算法都與其通用版本很相似，但不完全相同。

鏈表特有版本與通用版本間的一個至關重要的區別是鏈表版本會改變底層的容器。例如，remove的鏈表版本會刪除指定的元素。unique的鏈表版本會刪除第二個和后繼的重復元素。

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

例如，

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