一、只讀算法

    1、使用兩個(gè)迭代器和一個(gè)值調(diào)用 find 函數(shù)，檢查兩個(gè)迭代器實(shí)參標(biāo)記范圍內(nèi)的每一個(gè)元素。只要找到與給定值相等的元素，find 就會(huì)返回指向該元素的迭代器。如果沒有匹配的元素，find 就返回它的第二個(gè)迭代器實(shí)參，表示查找失敗。于是，只要檢查該函數(shù)的返回值是否與它的第二個(gè)實(shí)參相等，就可得知元素是否找到了。
     int search_value = 42;
     // call find to see if that value is present
     vector<int>::const_iterator result = find(vec.begin(), vec.end(), search_value);
     // report the result
     cout << "The value " << search_value

          << (result == vec.end()? " is not present" : " is present")
          << endl;

    2、許多算法只會(huì)讀取其輸入范圍內(nèi)的元素，而不會(huì)寫這些元素。find 就是一個(gè)這樣的算法。另一個(gè)簡(jiǎn)單的只讀算法是 accumulate，accumulate 帶有三個(gè)形參。頭兩個(gè)形參指定要累加的元素范圍。第三個(gè)形參則是累加的初值。

     // sum the elements in vec starting the summation with the value 42
     int sum = accumulate(vec.begin(), vec.end(), 42);

     // concatenate elements from v and store in sum
     string sum = accumulate(v.begin(), v.end(), string(""));

    3、find_first_of 函數(shù)。這個(gè)算法帶有兩對(duì)迭代器參數(shù)來標(biāo)記兩段元素范圍，在第一段范圍內(nèi)查找與第二段范圍中任意元素匹配的元素，然后返回一個(gè)迭代器，指向第一個(gè)匹配的元素。如果找不到元素，則返回第一個(gè)范圍的 end 迭代器。假設(shè) roster1 和 roster2 是兩個(gè)存放名字的 list 對(duì)象，可使用 find_first_of 統(tǒng)計(jì)有多少個(gè)名字同時(shí)出現(xiàn)在這兩個(gè)列表中：
     size_t cnt = 0;
     list<string>::iterator it = roster1.begin();
     // look in roster1 for any name also in roster2
     while   ((it = find_first_of(it, roster1.end(),roster2.begin(), roster2.end()))
               != roster1.end()) {
        ++cnt;
        // we got a match, increment it to look in the rest of roster1
        ++it;
     }
     cout << "Found " << cnt << " names on both rosters" << endl;

二、寫容器元素的算法

    1、寫入到輸入序列的算法本質(zhì)上是安全的——只會(huì)寫入與指定輸入范圍數(shù)量相同的元素，fill 帶有一對(duì)迭代器形參，用于指定要寫入的范圍，而所寫的值是它的第三個(gè)形參的副本。執(zhí)行時(shí)，將該范圍內(nèi)的每個(gè)元素都設(shè)為給定的值。如果輸入范圍有效，則可安全寫入。這個(gè)算法只會(huì)對(duì)輸入范圍內(nèi)已存在的元素進(jìn)行寫入操作。

     // reset each element to 0

     fill(vec.begin(), vec.end(), 0);    

     // set subsequence of the range to 10
     fill(vec.begin(), vec.begin() + vec.size()/2, 10);

    2、fill_n 函數(shù)帶有的參數(shù)包括：一個(gè)迭代器、一個(gè)計(jì)數(shù)器以及一個(gè)值。該函數(shù)從迭代器指向的元素開始，將指定數(shù)量的元素設(shè)置為給定的值。fill_n 函數(shù)假定對(duì)指定數(shù)量的元素做寫操作是安全的。初學(xué)者常犯的錯(cuò)誤的是：在沒有元素的空容器上調(diào)用 fill_n 函數(shù)（或者類似的寫元素算法）。

     vector<int> vec; // empty vector
     // disaster: attempts to write to 10 (nonexistent) elements in vec
     fill_n(vec.begin(), 10, 0);

    3、確保算法有足夠的元素存儲(chǔ)輸出數(shù)據(jù)的一種方法是使用插入迭代器。插入迭代器是可以給基礎(chǔ)容器添加元素的迭代器。通常，用迭代器給容器元素賦值時(shí)，被賦值的是迭代器所指向的元素。而使用插入迭代器賦值時(shí)，則會(huì)在容器中添加一個(gè)新元素，其值等于賦值運(yùn)算的右操作數(shù)的值。

      back_inserter 函數(shù)是迭代器適配器。與容器適配器一樣，迭代器適配器使用一個(gè)對(duì)象作為實(shí)參，并生成一個(gè)適應(yīng)其實(shí)參行為的新對(duì)象。本例中，傳遞給 back_inserter 的實(shí)參是一個(gè)容器的引用。back_inserter 生成一個(gè)綁定在該容器上的插入迭代器。在試圖通過這個(gè)迭代器給元素賦值時(shí)，賦值運(yùn)算將調(diào)用 push_back 在容器中添加一個(gè)具有指定值的元素。

     vector<int> vec; // empty vector
     // ok: back_inserter creates an insert iterator that adds elements to vec

     // appends 10 elements to vec
     fill_n (back_inserter(vec), 10, 0);

    4、向目標(biāo)迭代器寫入未知個(gè)數(shù)的元素。正如 fill_n 函數(shù)一樣，目標(biāo)迭代器指向存放輸出數(shù)據(jù)的序列中第一個(gè)元素。這類算法中最簡(jiǎn)單的是 copy 函數(shù)。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));

    5、有些算法提供所謂的“復(fù)制（copying）”版本。這些算法對(duì)輸入序列的元素做出處理，但不修改原來的元素，而是創(chuàng)建一個(gè)新序列存儲(chǔ)元素的處理結(jié)果。但不修改原來的元素，而是創(chuàng)建一個(gè)新序列存儲(chǔ)元素的處理結(jié)果。replace 算法就是一個(gè)很好的例子。該算法對(duì)輸入序列做讀寫操作，將序列中特定的值替換為新的值。該算法帶有四個(gè)形參：一對(duì)指定輸入范圍的迭代器和兩個(gè)值。每一個(gè)等于第一值的元素替換成第二個(gè)值。

     // replace any element with value of 0 by 42
     replace(ilst.begin(), ilst.end(), 0, 42);

     // create empty vector to hold the replacement
     vector<int> ivec;
     // use back_inserter to grow destination as needed

     //every element in ilst with the value 0 has the value 42 in ivec
     replace_copy (ilst.begin(), ilst.end(), back_inserter(ivec), 0, 42);

三、對(duì)容器元素重新排序的算法

    1、unique 算法帶有兩個(gè)指定元素范圍的迭代器參數(shù)。該算法刪除相鄰的重復(fù)元素，然后重新排列輸入范圍內(nèi)的元素，并且返回一個(gè)迭代器，表示無重復(fù)的值范圍的結(jié)束。

     // sort words alphabetically so we can find the duplicates

     //words:the quick red fox jumps over the slow red turtle
     sort(words.begin(), words.end());
   
     vector<string>::iterator end_unique = unique(words.begin(), words.end());
     words.erase(end_unique, words.end());

    2、如果要?jiǎng)h除重復(fù)的項(xiàng)，必須使用容器操作，在本例中調(diào)用 erase 實(shí)現(xiàn)該功能。這個(gè)函數(shù)調(diào)用從 end_unique 指向的元素開始刪除，直到 words 的最后一個(gè)元素也刪除掉為止。

    3、sort和stable_sort 算法，，stable_sort 保留相等元素的原始相對(duì)位置。sort 和 stable_sort 都是重載函數(shù)。其中一個(gè)版本使用元素類型提供的小于（<）操作符實(shí)現(xiàn)比較。在查找重復(fù)元素之前，我們就是用這個(gè) sort 版本對(duì)元素排序。第二個(gè)重載版本帶有第三個(gè)形參：比較元素所使用的謂詞函數(shù)的名字。這個(gè)謂詞函數(shù)必須接受兩個(gè)實(shí)參，實(shí)參的類型必須與元素類型相同，并返回一個(gè)可用作條件檢測(cè)的值。
     sort(words.begin(), words.end());

     // sort words by size, but maintain alphabetic order for words of the same size
     stable_sort(words.begin(), words.end(), isShorter);
    4、統(tǒng)計(jì)滿足指定條件的項(xiàng)數(shù)。執(zhí)行 count_if 時(shí)，首先讀取它的頭兩個(gè)實(shí)參所標(biāo)記的范圍內(nèi)的元素。每讀出一個(gè)元素，就將它傳遞給第三個(gè)實(shí)參表示的謂詞函數(shù)。此謂詞函數(shù)。此謂詞函數(shù)需要單個(gè)元素類型的實(shí)參，并返回一個(gè)可用作條件檢測(cè)的值。count_if 算法返回使謂詞函數(shù)返回條件成立的元素個(gè)數(shù)。

     //GT6 returns a bool value

     vector<string>::size_type wc = count_if(words.begin(), words.end(), GT6);

四、泛型算法中使用迭代器

    1、插入迭代器

       1.1 back_inserter，創(chuàng)建使用 push_back 實(shí)現(xiàn)插入的迭代器。

       1.2 front_inserter，使用 push_front 實(shí)現(xiàn)插入。該函數(shù)將創(chuàng)建一個(gè)迭代器，調(diào)用它所關(guān)聯(lián)的基礎(chǔ)容器的 push_front 成員函數(shù)代替賦值操作。只有當(dāng)容器提供 push_front 操作時(shí)，才能使用 front_inserter。在 vector 或其他沒有 push_front 運(yùn)算的容器上使用 front_inserter，將產(chǎn)生錯(cuò)誤。

       1.3 inserter，使用 insert 實(shí)現(xiàn)插入操作。這種適配器帶有兩個(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);

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

       list<int> ilst, ilst2, ilst3;

       // 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()));

    2、iostream 迭代器

       雖然 iostream 類型不是容器，但標(biāo)準(zhǔn)庫(kù)同樣提供了在 iostream 對(duì)象上使用的迭代器： istream_iterator用于讀取輸入流，而ostream_iterator則用于寫輸出流。這些迭代器將它們所對(duì)應(yīng)的流視為特定類型的元素序列。使用流迭代器時(shí)，可以用泛型算法從流對(duì)象中讀數(shù)據(jù)（或?qū)?shù)據(jù)寫到流對(duì)象中）。

       2.1 可使用 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++);

       2.2 可使用 ostream_iterator 對(duì)象將一個(gè)值序列寫入流中，其操作的過程與使用迭代器將一組值逐個(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++;

       2.3 流迭代器d的幾個(gè)重要限制：

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

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

           ostream_iterator 沒有 -> 操作符。
    3、反向迭代器
       反向迭代器是一種反向遍歷容器的迭代器。也就是，從最后一個(gè)元素到第一個(gè)元素遍歷容器。反向迭代器將自增（和自減）的含義反過來了：對(duì)于反向迭代器，++ 運(yùn)算將訪問前一個(gè)元素，而 -- 運(yùn)算則訪問下一個(gè)元素。

       // 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

    4、const 迭代器

       在之前使用 find 的程序中，我們將 result 定義為 const_iterator 類型。這樣做是因?yàn)槲覀儾幌Ｍ褂眠@個(gè)迭代器來修改容器中的元素。find_first_of程序中也不打算改變?nèi)萜鲀?nèi)的任何元素，但是它卻使用了普通的非 const 迭代器來保存 find_first_of 的返回值。

       原因是，在第二個(gè)例子中，程序?qū)⒌饔米?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è)普通的迭代器。

    5、迭代器分類

       Input iterator（輸入迭代器）              讀，不能寫；只支持自增運(yùn)算

       Output iterator（輸出迭代器）             寫，不能讀；只支持自增運(yùn)算

       Forward iterator（前向迭代器）            讀和寫；只支持自增運(yùn)算

       Bidirectional iterator（雙向迭代器）      讀和寫；支持自增和自減運(yùn)算

       Random access iterator（隨機(jī)訪問迭代器）  讀和寫；支持完整的迭代器算術(shù)運(yùn)算