• 除了為每個容器定義的迭代器之外，標準庫在頭文件iterator中還定義了額外幾種迭代器。這些迭代器包括以下幾種。
• 插入迭代器(insert iterator)：這些迭代器被綁定到一個容器上，可用來向容器插入元素。
• 流迭代器(stream iterator)：這些迭代器被綁定到輸入或輸出流上，可用來遍歷所關聯的IO流。
• 反向迭代器 (reverse iterator ): 這些迭代器向后而不是向前移動 。除了 forward_list之外的標準庫容器都有反向迭代器。
• 移動迭代器(move iterator)：這些專用的迭代器不是拷貝其中的元素，而是移動它們。我們將在13.6.2節 (第 480頁)介紹移動迭代器。

10.4.1插入迭代器

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

• 插入器有三種類型，差異在于元素插入的位置：
• back_inserter (參見10.2.2節，第 341頁)創建一個使用push_back的迭代器。
• front_inserter創建一個使用push_front的迭代器。
• inserter創建一個使用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> 1st = {1,2,3,4}; list<int> lst2, lst3; // 空 list
• / / 拷貝完成之后，lst2包含4 3 2 1? ? ? ? copy(1st.cbegin()r lst.cend(), front_inserter(lst2));
• / / 拷 貝完成之后，1st3包 含 1 2 3 4? ? ?copy(1st.cbegin(), 1st.cend(), inserter(lst3, lst3.begin()));
• 當調用front_ insert( c )時 ，我們得到一個插入迭代器，接下來會調用 push_front. 當每個元素被插入到容器c 中時，它變為c的新的首元素。因此,front_insert生成的迭代器會將插入的元素序列的順序顛倒過來，而insert 和back_insert則不會。

10.4.2 iostream 迭代器

• 雖然iostream 類型不是容器，但標準庫定義了可以用于這些IO類型對象的迭代器( 參 見 8.1 節 ，第 2 7 8 頁 )。istream_iterator ( 參見表 1 0 .3 )讀取輸入流 ，ostream _iterator (參見表10.4節，第 361頁)向一個輸出流寫數據。這些迭代器將它們對應的流當作一個特定類型的元素序列來處理。通過使用流迭代器，我們可以用泛型算法從流對象讀取數據以及向其寫入數據。

istreamjterator操作

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

• 此循環從cin讀取int值，保存在vec中。在每個循環步中，循環體代碼檢查in_iter 是否等于eof 。eof被定義為空的istream_iterator,從而可以當作尾后迭代器來使 用。對于一個綁定到流的迭代器，一旦其關聯的流遇到文件尾或遇到IO錯誤，迭代器的值就與尾后迭代器相等。
• 此程序最困難的部分是傳遞給push_back的參數，其中用到了解引用運算符和后置遞增運算符。該表達式的計算過程與我們之前寫過的其他結合解引用和后置遞增運算的表達式一樣(參見4.5節，第 131頁)。后置遞增運算會從流中讀取下一個值，向前推進，但返回的是迭代器的舊值。迭代器的舊值包含了從流中讀取的前一個值，對迭代器進行解引用就能獲得此值。
• 我們可以將程序重寫為如下形式，這體現了 istream_iterator更有用的地方：

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

10.4.3反向迭代器

• 反向迭代器就是在容器中從尾元素向首元素反向移動的迭代器。對于反向迭代器，遞增(以及遞減)操作的含義會顛倒過來。遞增一個反向迭代器(++it)會移動到前一個元素；遞減一個迭代器(--it)會移動到下一個元素。 除了 forward_list之外,其他容器都支持反向迭代器。我們可以通過調用rbegin、 rend、crbegin和 crend成員函數來獲得反向迭代器。這些成員函數返回指向容器尾 元素和首元素之前一個位置的迭代器。與普通迭代器一樣，反向迭代器也有const和非const版本。

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

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

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

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

• 從技術上講，普通迭代器與反向迭代器的關系反映了左閉合區間(參見9.2.1節，第296 頁 ) 的 特 性 。關 鍵 點 在 于 ［line.crbegin (), rcomma)和 ［rcomma.base (), line.cend?) 指 向 line中相同的元素范圍 。為了實現這一點 ，recomma和 rcomma.base ()必須生成相鄰位置而不是相同位置，crbegin ()和 cend ()也是如此
• 反向迭代器的目的是表示元素范圍，而這些范圍是不對稱的，這導致一個重要的結果：當我們從一個普通迭代器初始化一個反向迭代器，或是給一個反向迭代器賦值時，結果迭代器與原迭代器指向的并不是相同的元素.

1 0 .5 泛型算法結構

• 任何算法的最基本的特性是它要求其迭代器提供哪些操作。某些算法，如 find,只 要求通過迭代器訪問元素、遞增迭代器以及比較兩個迭代器是否相等這些能力。其他一些算法，如 sort,還要求讀、寫和隨機訪問元素的能力。算法所要求的迭代器操作可以分為 5 個迭代器類別(iterator category),如表 10.5所示。每個算法都會對它的每個迭代器參數指明須提供哪類迭代器。

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

10.5.1 5 類迭代器?

• 類似容器，迭代器也定義了一組公共操作。一些操作所有迭代器都支持，另外一些只有特定類別的迭代器才支持。例如，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）：提供在常量時間內訪問序列中任意元素的能力。 此類迭代器支持雙向迭代器的所有功能，此外還支持表3.7 （第 99頁）中的操作：
• 用于比較兩個迭代器相對位置的關系運算符（＜、＜=、＞和＞=）
• 迭代器和一個整數值的加減運算（+、+=、-和= ）, 計算結果是迭代器在序列中前進 （或后退）給定整數個元素后的位置
• 用于兩個迭代器上的減法運算符（-）, 得到兩個迭代器的距離
• 下標運算符（iter [n]）與* （iter [n]）等價，算法sort要求隨機訪問迭代器。array、deque、string和 vector的迭代器都是隨機訪問迭代器，用于訪問內置數組元素的指針也是。

1 0 .5 .2 算法形參模式

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

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

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

• dest參數是一個表示算法可以寫入的目的位置的迭代器。算法假定（assume）：按其需要寫入數據，不管寫入多少個元素都是安全的。向輸出迭代器寫入數據的算法都假定目標空間足夠容納寫入的數據“
• 如果dest是一個直接指向容器的迭代器，那么算法將輸出數據寫到容器中已存在的元素內。更常見的情況是，dest被綁定到一個插入迭代器（參 見 10.4.1節，第 358頁） 或是一個ostream_iterator （參 見 10.4.2節，第 359頁）。插入迭代器會將新元素添加到容器中,因而保證空間是足夠的。ostream_iterator會將數據寫入到一個輸出流， 同樣不管要寫入多少個元素都沒有問題。

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

• 接受單獨的beg2或是接受beg2和end2的算法用這些迭代器表示第二個輸入范圍。 這些算法通常使用第二個范圍中的元素與第一個輸入范圍結合來進行一些運算。
• 如果一個算法接受beg2和 end2,這兩個迭代器表示第二個范圍。這類算法接受兩個完整指定的范圍：［beg, end）表示的范圍和［beg2 end2）表示的第二個范圍。 只接受單獨的beg2（不接受end2）的算法將beg2作為第二個輸入范圍中的首元素。 此范圍的結束位置未指定，這些算法假定從beg2開始的范圍與beg和 end所表示的范 圍至少一樣大。

10.5.3算法命名規范

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

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

• 接受謂詞參數來代替＜或=運算符的算法，以及那些不接受額外參數的算法，通常都是重載的函數。函數的一個版本用元素類型的運算符來比較元素；另一個版本接受一個額外謂詞參數，來代替＜或=:
• unique (beg, end) ; / / 使 用 = = 運算符比較元素
• unique (beg, end, comp) ; // 使用 comp比較元素
• 兩個調用都重新整理給定序列，將相鄰的重復元素刪除。第一個調用使用元素類型的==運算符來檢查重復元素；第二個則調用comp來確定兩個元素是否相等。由于兩個版本的 函數在參數個數上不相等，因此具體應該調用哪個版本不會產生歧義（參見6.4節，第208頁）。

_ if版本的算法

• 接受一個元素值的算法通常有另一個不同名的（不是重載的）版本，該版本接受一個謂詞（參見10.3.1節，第 344頁）代替元素值。接受謂詞參數的算法都有附加的前綴：
• find （beg, end, val） ; / / 查找輸入范圍中val第一次出現的位置
• find_if （beg, end, pred） ; / / 查找第一個令pred為真的元素
• 這兩個算法都在輸入范圍中查找特定元素第一次出現的位置。算法find查找一個指定值； 算法f ind_if查找使得pred返回非零值的元素。 這兩個算法提供了命名上差異的版本，而非重載版本，因為兩個版本的算法都接受相同數目的參數。因此可能產生重載歧義，雖然很罕見，但為了避免任何可能的歧義，標準庫選擇提供不同名字的版本而不是重載。

區分拷貝元素的版本和不拷貝的版本

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

1 0 .6 特定容器算法

• 與其他容器不同，鏈表類型list 和 forward_list定義了幾個成員函數形式的算法，如 表 10.6所示。特別是，它們定義了獨有的sort , merge、remove, reverse 和 uniqueo通用版本的sort 要求隨機訪問迭代器，因此不能用于list和fordward_list.因為這兩個類型分別提供雙向迭代器和前向迭代器。
• 鏈表類型定義的其他算法的通用版本可以用于鏈表，但代價太高。這些算法需要交換輸入序列中的元素。-個鏈表可以通過改變元素間的鏈接而不是真的交換它們的值來快速“交換”元素。因此，這些鏈表版本的算法的性能比對應的通用版本好得多。
• 對于list和fordward_list,應該優先使用成員函數版本的算法而不是通用算法

splice成員

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

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

• 多數鏈表特有的算法都與其通用版本很相似，但不完全相同。鏈表特有版本與通用版本間的一個至關重要的區別是鏈表版本會改變底層的容器。例如，remove的鏈表版本會 刪除指定的元素。unique的鏈表版本會刪除第二個和后繼的重復元素。 類似的，merge和 splice會銷毀其參數。例如，通用版本的merge將合并的序列 寫到一個給定的目的迭代器；兩個輸入序列是不變的。而鏈表版本的merge函數會銷毀 給定的鏈表—— 元素從參數指定的鏈表中刪除，被合并到調用merge的鏈表對象中。在 merge之后，來自兩個鏈表中的元素仍然存在，但它們都已在同一個鏈表中。

小結

• 標準庫定義了大約100個類型無關的對序列進行操作的算法。序列可以是標準庫容器類型中的元素、一個內置數組或者是(例如)通過讀寫一個流來生成的。算法通過在迭代器上進行操作來實現類型無關。多數算法接受的前兩個參數是一對迭代器，表示一個元素范圍。額外的迭代器參數可能包括一個表示目的位置的輸出迭代器，或是表示第二個輸入范圍的另一個或另一對迭代器。
• 根據支持的操作不同，迭代器可分為五類：輸入、輸出、前向、雙向以及隨機訪問迭代器。如果一個迭代器支持某個迭代器類別所要求的操作，則屬于該類別。如同迭代器根據操作分類一樣，傳遞給算法的迭代器參數也按照所要求的操作進行分類。僅讀取序列的算法只要求輸入迭代器操作。寫入數據到目的位置迭代器的算法只要求輸出迭代器操作，依此類推。
• 算法從不直接改變它們所操作的序列的大小。它們會將元素從一個位置拷貝到另一個位置，但不會直接添加或刪除元素。雖然算法不能向序列添加元素，但插入迭代器可以做到。一個插入迭代器被綁定到一個容器上。當我們將一個容器元素類型的值賦予一個插入迭代器時，迭代器會將該值添加到容器中。
• 容 器 forward_list和 list 對一些通用算法定義了自己特有的版本。與通用算法不同，這些鏈表特有版本會修改給定的鏈表

術語表

• back_inserter這是一個迭代器適配器，它接受一個指向容器的引用，生成一個插入迭代器，該插入迭代器用push_back向指定容器添加元素。
• 雙向迭代器 ( bidirectional ite ra to r)支持前向迭代器的所有操作，還具有用--在序列中反向移動的能力。
• 二元謂詞(binary predicate)接受兩個參數的謂詞。
• bind標準庫函數，將一個或多個參數綁定到一個可調用表達式.bind定義在頭文件functional中。
• 可調用對象(callable object) 可以出現在調用運算符左邊的對象。函數指針、lambda以及重載了函數調用運算符的類的 對象都是可調用對象。
• 捕獲列表 (capture list) lambda表達式的—部分，指出lambda表達式可以訪問所在 上下文中哪些變量。
• cref標準庫函數，返回一個可拷貝的對象， 其中保存了一個指向不可拷貝類型的const對象的引用。
• 前向迭代器(forward iterator)可以讀寫元素，但不必支持--的迭代器。front_inserter迭代器適配器，給定一個容器，生成一個用push_front向容器開始位置添加元素的插入迭代器。
• 泛型算法(generic algorithm) 類型無關的算法。
• 輸入迭代器(input ite ra to r)可以讀但不能寫序列中元素的迭代器。
• 插入迭代器 (insertite ra to r)迭代器適配器，生成一個迭代器，該迭代器使用容器操作向給定容器添加元素
• 插 入 器 (inserter)迭代器適配器，接受一個迭代器和一個指向容器的引用，生成一個插入迭代器，該插入迭代器用insert 在給定迭代器指向的元素之前的位置添加元素。
• istreamjterator讀取輸入流的流迭代器。迭代器類別(iterator category)根據所支持的操作對迭代器進行的分類組織。迭代器類別形成一個層次，其中更強大的類別支持更弱類別的所有操作。算法使用迭代器類別來指出迭代器參數必須支持哪些操作。只要迭代器達到所要求的最小類別，它就可以用于算法。例如，一些算法只要求輸入迭代器。這類算法可處理除只滿足輸出迭代器要求的迭代器之外的任何迭代器。而要求隨機訪問迭代器的算法只能用于支持隨機訪問操作的迭代器。
• lambda 表 達 式 (lambda expression) 可調用的代碼單元.一個lambda類似一個未 命名的內聯函數。一個lambda以一個捕獲列表開始，此列表允許lambda訪問所在函 數中的變量。類似函數，lambda有一個(可 能為空的)參數列表、一個返回類型和一個函數體? lambda可以忽略返回類型? 如 果函數體是一個單一的re tu rn 語句，返 回類型就從返回對象的類型推斷。否則，忽略的返回類型默認定為void。
• 移動迭代器(move iterator)迭代器適配器，生成一個迭代器，該迭代器移動而不是拷貝元素。移動迭代器將在第13章中進行介紹。
• ostream_iterator寫輸出流的迭代器。 輸出迭代器(outputiterator)可以寫元素，但不必具有讀元素能力的迭代器。
• 謂 詞 (predicate)返回可以轉換為bool類型的值的函數。泛型算法通常用來檢測元素。標準庫使用的謂詞是一元(接受一個參數)或二元(接受兩個參數)的。
• 隨機訪問迭代器(random-access iterator)支持雙向迭代器的所有操作再加上比較迭代器值的關系運算符、下標運算符和迭代器匕的算術運算，因此支持隨機訪問元素。
• ref標準庫函數，從一個指向不能拷貝的類型的對象的引用生成一個可拷貝的對象。
• 反向迭代器(reverse ite ra to r)在序列中反向移動的迭代器。這些迭代器交換了++和一的含義。
• 流迭代器(stream ite ra to r)可以綁定到一個流的迭代器。
• —元 謂 詞 (unary predicate)接受一個參數的謂詞。