第十一章 泛型算法

標(biāo)準(zhǔn)庫(kù)容器定義的操作非常少。標(biāo)準(zhǔn)庫(kù)沒有給容器添加大量的功能函數(shù)，而是選擇提供一組算法，這些算法大都不依賴特定的容器類型，是“泛型”的，可作用在不同類型的容器和不同類型的元素上。

考慮下面的例子，可以使用 accumulate 把 string 型的 vector 容器中的元素連接起來(lái)：

     // concatenate elements from v and store in sum

     string sum = accumulate(v.begin(), v.end(), string(""));

這個(gè)函數(shù)調(diào)用的效果是：從空字符串開始，把 vec 里的每個(gè)元素連接成一個(gè)字符串。注意：程序顯式地創(chuàng)建了一個(gè) string 對(duì)象，用該函數(shù)調(diào)用的第三個(gè)實(shí)參。傳遞一個(gè)字符串字面值，將會(huì)導(dǎo)致編譯時(shí)錯(cuò)誤。因?yàn)榇藭r(shí)，累加和的類型將是 const char*，而 string 的加法操作符（第 3.2.3 節(jié)）所使用的操作數(shù)則分別是 string 和 const char* 類型，加法的結(jié)果將產(chǎn)生一個(gè) string 對(duì)象，而不是 const char* 指針。

對(duì)指定數(shù)目的元素做寫入運(yùn)算，或者寫到目標(biāo)迭代器的算法，都不檢查目標(biāo)的大小是否足以存儲(chǔ)要寫入的元素。

copy 帶有三個(gè)迭代器參數(shù)：頭兩個(gè)指定輸入范圍，第三個(gè)則指向目標(biāo)序列的一個(gè)元素。傳遞給 copy 的目標(biāo)序列必須至少要與輸入范圍一樣大。假設(shè) ilst 是一個(gè)存放 int 型數(shù)據(jù)的 list 對(duì)象，可如下將它 copy 給一個(gè) vector 對(duì)象：

     vector<int> ivec; // empty vector

     // copy elements from ilst into ivec

     copy (ilst.begin(), ilst.end(), back_inserter(ivec));

replace 算法就是一個(gè)很好的例子。該算法對(duì)輸入序列做讀寫操作，將序列中特定的值替換為新的值。該算法帶有四個(gè)形參：一對(duì)指定輸入范圍的迭代器和兩個(gè)值。每一個(gè)等于第一值的元素替換成第二個(gè)值。

     // replace any element with value of 0 by 42

     replace(ilst.begin(), ilst.end(), 0, 42);

這個(gè)調(diào)用將所有值為 0 的實(shí)例替換成 42。如果不想改變?cè)瓉?lái)的序列，則調(diào)用 replace_copy。這個(gè)算法接受第三個(gè)迭代器實(shí)參，指定保存調(diào)整后序列的目標(biāo)位置。

     // create empty vector to hold the replacement

     vector<int> ivec;

     // use back_inserter to grow destination as needed

     replace_copy (ilst.begin(), ilst.end(), back_inserter(ivec), 0, 42);

假設(shè)我們的輸入存儲(chǔ)在一個(gè)名為 words 的 vector 對(duì)象中，第一個(gè)子問(wèn)題是將 words 中重復(fù)出現(xiàn)的單詞去除掉：

     // sort words alphabetically so we can find the duplicates

     sort(words.begin(), words.end());

     /* eliminate duplicate words:

      * unique reorders words so that each word appears once in the

      *    front portion of words and returns an iterator one past the unique range;

      * erase uses a vector operation to remove the nonunique elements

      */

     vector<string>::iterator end_unique =

                    unique(words.begin(), words.end());

     words.erase(end_unique, words.end());

單詞按次序排列后，現(xiàn)在的問(wèn)題是：讓故事中所用到的每個(gè)單詞都只保留一個(gè)副本。unique 算法很適合用于解決這個(gè)問(wèn)題，它帶有兩個(gè)指定元素范圍的迭代器參數(shù)。該算法刪除相鄰的重復(fù)元素，然后重新排列輸入范圍內(nèi)的元素，并且返回一個(gè)迭代器，表示無(wú)重復(fù)的值范圍的結(jié)束。

After the call to unique, the vector holds

調(diào)用 unique 后，vector 中存儲(chǔ)內(nèi)容是：

注意，words 的大小并沒有改變，依然保存著 10 個(gè)元素；只是這些元素的順序改變了。調(diào)用 unique“刪除”了相鄰的重復(fù)值。給“刪除”加上引號(hào)是因?yàn)?nbsp;unique 實(shí)際上并沒有刪除任何元素，而是將無(wú)重復(fù)的元素復(fù)制到序列的前端，從而覆蓋相鄰的重復(fù)元素。unique 返回的迭代器指向超出無(wú)重復(fù)的元素范圍末端的下一位置。

現(xiàn)在此 vector 對(duì)象已經(jīng)按單詞長(zhǎng)度排序，剩下的問(wèn)題就是統(tǒng)計(jì)長(zhǎng)度不小于 6 的單詞個(gè)數(shù)。使用 count_if 算法處理這個(gè)問(wèn)題：

     vector<string>::size_type wc =

                  count_if(words.begin(), words.end(), GT6);

     bool GT6(const string &s)

     {

         return s.size() >= 6;

     }

盡管這個(gè)函數(shù)能解決問(wèn)題，但存在不必要限制——函數(shù)內(nèi)部硬性規(guī)定了對(duì)長(zhǎng)度大小的要求。如果要統(tǒng)計(jì)其他長(zhǎng)度的單詞個(gè)數(shù)，則必須編寫另一個(gè)函數(shù)。其實(shí)很容易寫出更通用的比較函數(shù)，使它帶有兩個(gè)形參，分別是 string 對(duì)象和一個(gè)長(zhǎng)度大小值即可。但是，傳遞給 count_if 算法的函數(shù)只能帶有一個(gè)實(shí)參，因此本程序不能使用上述更通用的方法。第 14.8.1 節(jié)將為這個(gè)問(wèn)題提供更好的解決方案。

了解程序的細(xì)節(jié)之后，下面是完整的程序：

     // comparison function to be used to sort by word length

     bool isShorter(const string &s1, const string &s2)

     {

         return s1.size() < s2.size();

     }

     // determine whether a length of a given word is 6 or more

     bool GT6(const string &s)

     {

         return s.size() >= 6;

     }

     int main()

     {

         vector<string> words;

         // copy contents of each book into a single vector

         string next_word;

         while (cin >> next_word) {

             // insert next book's contents at end of words

             words.push_back(next_word);

         }

         // sort words alphabetically so we can find the duplicates

         sort (words.begin(), words.end());

         /* eliminate duplicate words:

          * unique reorders words so that each word appears once in the

          *       front portion of words and returns an iterator one past the unique range;

          * erase uses a vector operation to remove the nonunique elements

          */

         vector<string>::iterator end_unique =

                     unique(words.begin(), words.end());

         words.erase(end_unique, words.end());

          // sort words by size, but maintain alphabetic order for words of the same size

          stable_sort(words.begin(), words.end(), isShorter);

          vector<string>::size_type wc =

                          count_if (words.begin(), words.end(), GT6);

          cout << wc << " " << make_plural(wc, "word", "s")

               << " 6 characters or longer" << endl;

          return 0;

     }

反向迭代器：這類迭代器實(shí)現(xiàn)向后遍歷，而不是向前遍歷。所有容器類型都定義了自己的 reverse_iterator 類型，由 rbegin 和 rend 成員函數(shù)返回。

第 11.2.2 節(jié)已強(qiáng)調(diào)標(biāo)準(zhǔn)庫(kù)所定義的迭代器不依賴于特定的容器。事實(shí)上，C++ 語(yǔ)言還提供了另外三種迭代器：

插入迭代器：這類迭代器與容器綁定在一起，實(shí)現(xiàn)在容器中插入元素的功能。

iostream 迭代器：這類迭代器可與輸入或輸出流綁定在一起，用于迭代遍歷所關(guān)聯(lián)的 IO 流。

反向迭代器：這類迭代器實(shí)現(xiàn)向后遍歷，而不是向前遍歷。所有容器類型都定義了自己的 reverse_iterator 類型，由 rbegin 和 rend 成員函數(shù)返回。

上述迭代器類型都在 iterator 頭文件中定義。

上述迭代器類型都在 iterator 頭文件中定義。

inserter 適配器提供更普通的插入形式。這種適配器帶有兩個(gè)實(shí)參：所關(guān)聯(lián)的容器和指示起始插入位置的迭代器。

     // position an iterator into ilst

     list<int>::iterator it =

      find (ilst.begin(), ilst.end(), 42);

     // insert replaced copies of ivec at that point in ilst

     replace_copy (ivec.begin(), ivec.end(),

                   inserter (ilst, it), 100, 0);

首先用 find 定位 ilst 中的某個(gè)元素。使用 inserter 作為實(shí)參調(diào)用 replace_copy，inserter 將會(huì)在 ilst 中由 find 返回的迭代器所指向的元素前面插入新元素。而調(diào)用 replace_copy 的效果是從 ivec 中復(fù)制元素，并將其中值為 100 的元素替換為 0 值。ilst 的新元素在 it 所標(biāo)明的元素前面插入。

也許我們會(huì)認(rèn)為可使用 inserter 和容器的 begin 迭代器來(lái)模擬 front_inserter 的效果。然而，inserter 的行為與 front_inserter 的有很大差別。在使用 front_inserter 時(shí)，元素始終在容器的第一個(gè)元素前面插入。而使用 inserter 時(shí)，元素則在指定位置前面插入。即使此指定位置初始化為容器中的第一個(gè)元素，但是，一旦在該位置前插入一個(gè)新元素后，插入位置就不再是容器的首元素了：

     list<int> ilst, ilst2, ilst3;     // empty lists

     // after this loop ilst contains: 3 2 1 0

     for (list<int>::size_type i = 0; i != 4; ++i)

          ilst.push_front(i);

     // after copy ilst2 contains: 0 1 2 3

     copy (ilst.begin(), ilst.end(), front_inserter(ilst2));

     // after copy, ilst3 contains: 3 2 1 0

     copy (ilst.begin(), ilst.end(),

                  inserter (ilst3, ilst3.begin()));

在復(fù)制并創(chuàng)建 ilst2 的過(guò)程中，元素總是在這個(gè) list 對(duì)象的所有元素之前插入。而在復(fù)制創(chuàng)建 ilst3 的過(guò)程中，元素則在 ilst3 中的固定位置插入。剛開始時(shí)，這個(gè)插入位置是此 list 對(duì)象的頭部，但插入一個(gè)元素后，就不再是首元素了。

流迭代器只定義了最基本的迭代器操作：自增、解引用和賦值。此外，可比較兩個(gè) istream 迭代器是否相等（或不等）。而 ostream 迭代器則不提供比較運(yùn)算（表 11.2）。

Table 11.2. istream_iterator Operations

表 11.2. istream_iterator 的操作

流迭代器的定義

流迭代器都是類模板：任何已定義輸入操作符（>> 操作符）的類型都可以定義 istream_iterator。類似地，任何已定義輸出操作符（<< 操作符）的類型也可定義 ostream_iterator。

在創(chuàng)建流迭代器時(shí)，必須指定迭代器所讀寫的對(duì)象類型：

     istream_iterator<int> cin_it(cin);    // reads ints1 from cin

     istream_iterator<int> end_of_stream;  // end iterator value

     // writes Sales_items from the ofstream named outfile

     // each element is followed by a space

     ofstream outfile;

     ostream_iterator<Sales_item> output(outfile, " ");

ostream_iterator 對(duì)象必須與特定的流綁定在一起。在創(chuàng)建 istream_iterator 時(shí)，可直接將它綁定到一個(gè)流上。另一種方法是在創(chuàng)建時(shí)不提供實(shí)參，則該迭代器指向超出末端位置。ostream_iterator 不提供超出末端迭代器。

在創(chuàng)建 ostream_iterator 對(duì)象時(shí)，可提供第二個(gè)（可選的）實(shí)參，指定將元素寫入輸出流時(shí)使用的分隔符。分隔符必須是 C 風(fēng)格字符串。因?yàn)樗?nbsp;C 風(fēng)格字符串，所以必須以空字符結(jié)束；否則，其行為將是未定義的。

istream_iterator 對(duì)象上的操作

構(gòu)造與流綁定在一起的 istream_iterator 對(duì)象時(shí)將對(duì)迭代器定位，以便第一次對(duì)該迭代器進(jìn)行解引用時(shí)即可從流中讀取第一個(gè)值。

考慮下面例子，可使用 istream_iterator 對(duì)象將標(biāo)準(zhǔn)輸入讀到 vector 對(duì)象中。

     istream_iterator<int> in_iter(cin); // read ints from cin

     istream_iterator<int> eof; // istream "end" iterator

     // read until end of file, storing what was read in vec

     while (in_iter != eof)

             // increment advances the stream to the next value

             // dereference reads next value from the istream

             vec.push_back(*in_iter++);

更有趣的是可以這樣重寫程序：

     istream_iterator<int> in_iter(cin); // read ints from cin

     istream_iterator<int> eof;      // istream "end" iterator

     vector<int> vec(in_iter, eof);  // construct vec from an iterator range

這里，用一對(duì)標(biāo)記元素范圍的迭代器構(gòu)造 vec 對(duì)象。這些迭代器是 istream_iterator 對(duì)象，這就意味著這段范圍的元素是通過(guò)讀取所關(guān)聯(lián)的流來(lái)獲得的。這個(gè)構(gòu)造函數(shù)的效果是讀 cin，直到到達(dá)文件結(jié)束或輸入的不是 int 型數(shù)值為止。讀取的元素將用于構(gòu)造 vec 對(duì)象。

ostream_iterator 對(duì)象和 ostream_iterator 對(duì)象的使用

可使用 ostream_iterator 對(duì)象將一個(gè)值序列寫入流中，其操作的過(guò)程與使用迭代器將一組值逐個(gè)賦給容器中的元素相同：

     // write one string per line to the standard output

     ostream_iterator<string> out_iter(cout, "\n");

     // read strings from standard input and the end iterator

     istream_iterator<string> in_iter(cin), eof;

     // read until eof and write what was read to the standard output

     while (in_iter != eof)

         // write value of in_iter to standard output

         // and then increment the iterator to get the next value from cin

        *out_iter++ = *in_iter++;

首先，定義一個(gè) ostream_iterator 對(duì)象，用于將 string 類型的數(shù)據(jù)寫到 cout 中，每個(gè) string 對(duì)象后跟一個(gè)換行符。定義兩個(gè) istream_iterator 對(duì)象，用于從 cin 中讀取 string 對(duì)象。while 循環(huán)類似前一個(gè)例子。但是這一次不是將讀取的數(shù)據(jù)存儲(chǔ)在 vector 對(duì)象中，而是將讀取的數(shù)據(jù)賦給 out_iter，從而輸出到 cout 上。

在類類型上使用 istream_iterator

提供了輸入操作符（>>）的任何類型都可以創(chuàng)建 istream_iterator 對(duì)象。例如，可如下使用 istream_iterator 對(duì)象讀取一系列的 Sales_iter 對(duì)象，并求和：

     istream_iterator<Sales_item> item_iter(cin), eof;

     Sales_item sum; // initially empty Sales_item

     sum = *item_iter++; // read first transaction into sum and get next record

     while (item_iter != eof) {

        if (item_iter->same_isbn(sum))

            sum = sum + *item_iter;

        else {

            cout << sum << endl;

            sum = *item_iter;

        }

        ++item_iter; // read next transaction

     }

     cout << sum << endl; // remember to print last set of records

流迭代器的限制

流迭代器有下面幾個(gè)重要的限制：

不可能從 ostream_iterator 對(duì)象讀入，也不可能寫到 istream_iterator 對(duì)象中。

一旦給 ostream_iterator 對(duì)象賦了一個(gè)值，寫入就提交了。賦值后，沒有辦法再改變這個(gè)值。此外，ostream_iterator 對(duì)象中每個(gè)不同的值都只能正好輸出一次。

ostream_iterator 沒有 -> 操作符。

正如大家所知，算法是基于迭代器操作實(shí)現(xiàn)的。如同前面所述，流迭代器至少定義了一些迭代器操作。由于流迭代器操作，因此，至少可在一些泛型算法上使用這類迭代器?？紤]下面的例子，從標(biāo)準(zhǔn)輸入讀取一些數(shù)，再將讀取的不重復(fù)的數(shù)寫到標(biāo)準(zhǔn)輸出：

     istream_iterator<int> cin_it(cin);    // reads ints from cin

     istream_iterator<int> end_of_stream;  // end iterator value

     // initialize vec from the standard input:

     vector<int> vec(cin_it, end_of_stream);

     sort(vec.begin(), vec.end());

     // writes ints to cout using " " as the delimiter

     ostream_iterator<int> output(cout, " ");

     // write only the unique elements in vec to the standard output

     unique_copy(vec.begin(), vec.end(), output);

如果程序的輸入是：

     23 109 45 89 6 34 12 90 34 23 56 23 8 89 23

輸出則是：

     6 8 12 23 34 45 56 89 90 109

假設(shè)有一個(gè) vector 容器對(duì)象，存儲(chǔ) 0-9 這 10 個(gè)以升序排列的數(shù)字：

     vector<int> vec;

     for (vector<int>::size_type i = 0; i != 10; ++i)

         vec.push_back(i); // elements are 0,1,2,...9

下面的 for 循環(huán)將以逆序輸出這些元素：

     // reverse iterator of vector from back to front

     vector<int>::reverse_iterator r_iter;

     for (r_iter = vec.rbegin(); // binds r_iter to last element

          r_iter != vec.rend();  // rend refers 1 before 1st element

          ++r_iter)              // decrements iterator one element

         cout << *r_iter << endl;    // prints 9,8,7,...0

雖然顛倒自增和自減這兩個(gè)操作符的意義似乎容易使人迷惑，但是它讓程序員可以透明地向前或向后處理容器。例如，為了以降序排列 vector，只需向 sort 傳遞一對(duì)反向迭代器：

     // sorts vec in "normal" order

     sort(vec.begin(), vec.end());

     // sorts in reverse: puts smallest element at the end of vec

     sort(vec.rbegin(), vec.rend());

反向迭代器需要使用自減操作符

從一個(gè)既支持 -- 也支持 ++ 的迭代器就可以定義反向迭代器，這不用感到吃驚。畢竟，反向迭代器的目的是移動(dòng)迭代器反向遍歷序列。標(biāo)準(zhǔn)容器上的迭代器既支持自增運(yùn)算，也支持自減運(yùn)算。但是，流迭代器卻不然，由于不能反向遍歷流，因此流迭代器不能創(chuàng)建反向迭代器。

如果要輸出列表中最后一個(gè)單詞，可使用反向迭代器：

     // find last element in a comma-separated list

     string::reverse_iterator rcomma = find(line.rbegin(), line.rend(), ',');

因?yàn)榇藭r(shí)傳遞的是 rbegin() 和 rend()，這個(gè)函數(shù)調(diào)用從 line 的最后一個(gè)字符開始往回搜索。當(dāng) find 完成時(shí)，如果列表中有逗號(hào)，那么 rcomma 指向其最后一個(gè)逗號(hào)，即指向反向搜索找到的第一個(gè)逗號(hào)。如果沒有逗號(hào)，則 rcomma 的值為 line.rend()。

在嘗試輸出所找到的單詞時(shí)，有趣的事情發(fā)生了。直接嘗試：

     // wrong: will generate the word in reverse order

     cout << string(line.rbegin(), rcomma) << endl;

會(huì)產(chǎn)生假的輸出。例如，如果輸入是：

     FIRST,MIDDLE,LAST

then this statement would print TSAL!

則將輸出 TSAL！

圖 11.2 闡明了這個(gè)問(wèn)題：使用反向迭代器時(shí)，以逆序從后向前處理 string 對(duì)象。為了得到正確的輸出，必須將反向迭代器 line.rbegin() 和 rcomma 轉(zhuǎn)換為從前向后移動(dòng)的普通迭代器。其實(shí)沒必要轉(zhuǎn)換 line.rbegin()，因?yàn)槲覀冎擂D(zhuǎn)換的結(jié)果必定是 line.end()。只需調(diào)用所有反向迭代器類型都提供的成員函數(shù) base 轉(zhuǎn)換 rcomma 即可

圖 11.2 顯示的對(duì)象直觀地解釋了普通迭代器與反向迭代器之間的關(guān)系。例如，正如 line_rbegin() 和 line.end() 一樣，rcomma 和 rcomma.base() 也指向不同的元素。為了確保正向和反向處理元素的范圍相同，這些區(qū)別必要的。從技術(shù)上來(lái)說(shuō)，設(shè)計(jì)普通迭代器與反向迭代器之間的關(guān)系是為了適應(yīng)左閉合范圍（第 9.2.1 節(jié)）這個(gè)性質(zhì)的，所以，[line.rbegin(), rcomma) 和 [rcomma.base(), line.end()) 標(biāo)記的是 line 中的相同元素。

反向迭代器用于表示范圍，而所表示的范圍是不對(duì)稱的，這個(gè)事實(shí)可推導(dǎo)出一個(gè)重要的結(jié)論：使用普通的迭代器對(duì)反向迭代器進(jìn)行初始化或賦值時(shí)，所得到的迭代器并不是指向原迭代器所指向的元素。

11.3.4. const 迭代器

細(xì)心的讀者可能已經(jīng)注意到，在第 11.1 節(jié)使用 find 的程序中，我們將 result 定義為 const_iterator 類型。這樣做是因?yàn)槲覀儾幌Ｍ褂眠@個(gè)迭代器來(lái)修改容器中的元素。

另一方面，雖然第 11.2.1 節(jié)的程序也不打算改變?nèi)萜鲀?nèi)的任何元素，但是它卻使用了普通的非 const 迭代器來(lái)保存 find_first_of 的返回值。這兩種處理存在細(xì)微的差別，值得解釋一下。

原因是，在第二個(gè)例子中，程序?qū)⒌饔米?nbsp;find_first_of 的實(shí)參：

     find_first_of(it, roster1.end(),

                   roster2.begin(), roster2.end());

該函數(shù)調(diào)用的輸入范圍由 it 和調(diào)用 roster1.end() 返回的迭代器指定。算法要求用于指定范圍的兩個(gè)迭代器必須具有完全一樣的類型。roster1.end() 返回的迭代器依賴于 roster1 的類型。如果該容器是 const 對(duì)象，則返回的迭代器是 const_iterator 類型；否則，就是普通的 iterator 類型。在這個(gè)程序中，roster1 不是 const 對(duì)象，因而 end 返回的只是一個(gè)普通的迭代器。

如果我們將 it 定義為 const_iterator，那么 find_first_of 的調(diào)用將無(wú)法編譯。用來(lái)指定范圍的兩個(gè)迭代器的類型不相同。it 是 const_iterator 類型的對(duì)象，而 rotser1.end() 返回的則是一個(gè) iterator 對(duì)象。

Table 11.3. Iterator Categories

表 11.3. 迭代器種類

輸入迭代器可用于讀取容器中的元素，但是不保證能支持容器的寫入操作。輸入迭代器必須至少提供下列支持。

相等和不等操作符（==，!=），比較兩個(gè)迭代器。

前置和后置的自增運(yùn)算（++），使迭代器向前遞進(jìn)指向下一個(gè)元素。

用于讀取元素的解引用操作符（*），此操作符只能出現(xiàn)在賦值運(yùn)算的右操作數(shù)上。

箭頭操作符（->），這是 (*it).member 的同義語(yǔ)，也就是說(shuō)，對(duì)迭代器進(jìn)行解引用來(lái)獲取其所關(guān)聯(lián)的對(duì)象的成員。

輸入迭代器只能順序使用；一旦輸入迭代器自增了，就無(wú)法再用它檢查之前的元素。要求在這個(gè)層次上提供支持的泛型算法包括 find 和 accumulate。標(biāo)準(zhǔn)庫(kù) istream_iterator 類型輸入迭代器。

輸出迭代器　可視為與輸入迭代器功能互補(bǔ)的迭代器；輸出迭代器可用于向容器寫入元素，但是不保證能支持讀取容器內(nèi)容。輸出迭代器要求：

前置和后置的自增運(yùn)算（++），使迭代器向前遞進(jìn)指向下一個(gè)元素。

解引用操作符（*），引操作符只能出現(xiàn)在賦值運(yùn)算的左操作數(shù)上。給解引用的輸出迭代器賦值，將對(duì)該迭代器所指向的元素做寫入操作。

輸出迭代器可以要求每個(gè)迭代器的值必須正好寫入一次。使用輸出迭代器時(shí)，對(duì)于指定的迭代器值應(yīng)該使用一次 * 運(yùn)算，而且只能用一次。輸出迭代器一般用作算法的第三個(gè)實(shí)參，標(biāo)記起始寫入的位置。例如，copy 算法使用一個(gè)輸出迭代器作為它的第三個(gè)實(shí)參，將輸入范圍內(nèi)的元素復(fù)制到輸出迭代器指定的目標(biāo)位置。標(biāo)準(zhǔn)庫(kù) ostream_iterator 類型輸出迭代器。

前向迭代器 用于讀寫指定的容器。這類迭代器只會(huì)以一個(gè)方向遍歷序列。前向迭代器支持輸入迭代器和輸出迭代器提供的所有操作，除此之外，還支持對(duì)同一個(gè)元素的多次讀寫。可復(fù)制前向迭代器來(lái)記錄序列中的一個(gè)位置，以便將來(lái)返回此處。需要前向迭代器的泛型算法包括 replace。

雙向迭代器　從兩個(gè)方向讀寫容器。除了提供前向迭代器的全部操作之外，雙向迭代器還提供前置和后置的自減運(yùn)算（--）。需要使用雙向迭代器的泛型算法包括 reverse。所有標(biāo)準(zhǔn)庫(kù)容器提供的迭代器都至少達(dá)到雙向迭代器的要求。

需要隨機(jī)訪問(wèn)迭代器的泛型算法包括 sort 算法。vector、deque 和 string 迭代器是隨機(jī)訪問(wèn)迭代器，用作訪問(wèn)內(nèi)置數(shù)組元素的指針也是隨機(jī)訪問(wèn)迭代器。

隨機(jī)訪問(wèn)迭代器　提供在常量時(shí)間內(nèi)訪問(wèn)容器任意位置的功能。這種迭代器除了支持雙向迭代器的所有功能之外，還支持下面的操作：

The relational operators <, <=, >, and >= to compare the relative positions of two iterators.

關(guān)系操作符 <、<=、> 和 >=，比較兩個(gè)迭代器的相對(duì)位置。

迭代器與整型數(shù)值 n 之間的加法和減法操作符 +、+=、- 和 -=，結(jié)果是迭代器在容器中向前（或退回）n 個(gè)元素。

兩個(gè)迭代器之間的減法操作符（--），得到兩個(gè)迭代器間的距離。

下標(biāo)操作符 iter[n]，這是 *(iter + n) 的同義詞。

盡管 map 和 set 類型提供雙向迭代器，但關(guān)聯(lián)容器只能使用算法的一個(gè)子集。問(wèn)題在于：關(guān)聯(lián)容器的鍵是 const 對(duì)象。因此，關(guān)聯(lián)容器不能使用任何寫序列元素的算法。只能使用與關(guān)聯(lián)容器綁在一起的迭代器來(lái)提供用于讀操作的實(shí)參。

向算法傳遞無(wú)效的迭代器類別所引起的錯(cuò)誤，無(wú)法保證會(huì)在編譯時(shí)被捕獲到。

11.4.1. 算法的形參模式

任何其他的算法分類都含有一組形參規(guī)范。理解這些形參規(guī)范有利于學(xué)習(xí)新的算法——只要知道形參的含義，就可專注于了解算法實(shí)現(xiàn)的操作。大多數(shù)算法采用下面四種形式之一：

     alg (beg, end, other parms);

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

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

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

其中，alg 是算法的名字，beg 和 end 指定算法操作的元素范圍。我們通常將該范圍稱為算法的“輸入范圍”。盡管幾乎所有算法都有輸入范圍，但算法是否使用其他形參取決于它所執(zhí)行的操作。這里列出了比較常用的其他形參：dest、beg2 和 end2，它們都是迭代器。這些迭代器在使用時(shí)，充當(dāng)類似的角色。除了這些迭代器形參之外，有些算法還帶有其他的菲迭代器形參，它們是這些算法特有的。

新對(duì)容器元素排序的算法要使用 < 操作符。這些算法的第二個(gè)重載版本帶有一個(gè)額外的形參，表示用于元素排序的不同運(yùn)算：

     sort (beg, end);         // use < operator to sort the elements

     sort (beg, end, comp);   // use function named comp to sort the elements

檢查指定值的算法默認(rèn)使用 == 操作符。系統(tǒng)為這類算法提供另外命名的（而非重載的）版本，帶有謂詞函數(shù)（第 11.2.3 節(jié)）形參。帶有謂詞函數(shù)形參的算法，其名字帶有后綴 _if：

檢查指定值的算法默認(rèn)使用 == 操作符。系統(tǒng)為這類算法提供另外命名的（而非重載的）版本，帶有謂詞函數(shù)（第 11.2.3 節(jié)）形參。帶有謂詞函數(shù)形參的算法，其名字帶有后綴 _if：

     find(beg, end, val);       // find first instance of val in the input range

     find_if(beg, end, pred);   // find first instance for which pred is true

上述兩個(gè)算法都在輸入范圍內(nèi)尋找指定元素的第一個(gè)實(shí)例。其中，find 算法查找一個(gè)指定的值，而 find_if 算法則用于查找一個(gè)使謂詞函數(shù) pred 返回非零值的元素。

區(qū)別是否實(shí)現(xiàn)復(fù)制的算法版本

無(wú)論算法是否檢查它的元素值，都可能重新排列輸入范圍內(nèi)的元素。在默認(rèn)情況下，這些算法將重新排列的元素寫回其輸入范圍。標(biāo)準(zhǔn)庫(kù)也為這些算法提供另外命名的版本，將元素寫到指定的輸出目標(biāo)。此版本的算法在名字中添加了 _copy 后綴：

     reverse(beg, end);

     reverse_copy(beg, end, dest);

reverse 函數(shù)的功能就如它的名字所意味的：將輸入序列中的元素反射重新排列。其中，第一個(gè)函數(shù)版本將自己的輸入序列中的元素反向重排。而第二個(gè)版本，reverse_copy，則復(fù)制輸入序列的元素，并將它們逆序存儲(chǔ)到 dest 開始的序列中。

list 容器上的迭代器是雙向的，而不是隨機(jī)訪問(wèn)類型。由于 list 容器不支持隨機(jī)訪問(wèn)，因此，在此容器上不能使用需要隨機(jī)訪問(wèn)迭代器的算法。這些算法包括 sort 及其相關(guān)的算法。還有一些其他的泛型算法，如 merge、remove、reverse 和 unique，雖然可以用在 list 上，但卻付出了性能上的代價(jià)。如果這些算法利用 list 容器實(shí)現(xiàn)的特點(diǎn)，則可以更高效地執(zhí)行。

如果可以結(jié)合利用 list 容器的內(nèi)部結(jié)構(gòu)，則可能編寫出更快的算法。與其他順序容器所支持的操作相比，標(biāo)準(zhǔn)庫(kù)為 list 容器定義了更精細(xì)的操作集合，使它不必只依賴于泛型操作。表 11.4 列出了 list 容器特有的操作，其中不包括要求支持雙向或更弱的迭代器類型的泛型算法，這類泛型算法無(wú)論是用在 list 容器上，還是用在其他容器上，都具有相同的效果。

Table 11.4. list-Specific Operations

表 11.4. list 容器特有的操作

大多數(shù) list 容器特有的算法類似于其泛型形式中已經(jīng)見過(guò)的相應(yīng)的算法，但并不相同：

     l.remove(val);     // removes all instances of val from 1

     l.remove_if(pred); // removes all instances for which pred is true from 1

     l.reverse();       // reverses the order of elements in 1

     l.sort();          // use element type < operator to compare elements

     l.sort(comp);      // use comp to compare elements

     l.unique();        // uses element == to remove adjacent duplicates

     l.unique(comp);    // uses comp to remove duplicate adjacent copies

list 容器特有的算法與其泛型算法版本之間有兩個(gè)至關(guān)重要的差別。其中一個(gè)差別是 remove 和 unique 的 list 版本修改了其關(guān)聯(lián)的基礎(chǔ)容器：真正刪除了指定的元素。例如，list::unique 將 list 中第二個(gè)和后續(xù)重復(fù)的元素刪除出該容器。

另一個(gè)差別是 list 容器提供的 merge 和 splice 運(yùn)算會(huì)破壞它們的實(shí)參。使用 merge 的泛型算法版本時(shí)，合并的序列將寫入目標(biāo)迭代器指向的對(duì)象，而它的兩個(gè)輸入序列保持不變。但是，使用 list 容器的 merge 成員函數(shù)時(shí)，則會(huì)破壞它的實(shí)參 list 對(duì)象——當(dāng)實(shí)參對(duì)象的元素合并到調(diào)用 merge 函數(shù)的 list 對(duì)象時(shí)，實(shí)參對(duì)象的元素被移出并刪除。