題記：本系列學習筆記（C++ Primer學習筆記）主要目的是討論一些容易被大家忽略或者容易形成錯誤認識的內容。只適合于有了一定的C++基礎的讀者（至少學完一本C++教程）。
作者： tyc611, 2007-01-27
本文主要討論C++標準庫中的泛型算法(generic algorithm)。泛型算法是使用容器的強有力的輔助工具。
如果文中有錯誤或遺漏之處，敬請指出，謝謝！
標準庫為容器類型定義的操作很少，并沒有為每個容器實現更多的操作。因為這部分操作可以抽象出來為所有的容器工作，那就是泛型算法。所謂“泛型”是指這些算法可以應用于多種容器類型上，而容器內的元素類型也可以多樣化。標準庫提供了100多個泛型算法，主要定義于頭文件<algorithm>中，還有一組泛化的算術算法定義于頭文件<numeric>中。
大多數泛型算法是工作于容器的一對迭代器所標識的范圍，并完全通過迭代器來實現其功能。這段由迭代器指定的范圍稱為“輸入范圍”。帶有輸入范圍參數的算法總是使用前兩個參數標記該范圍，分別指向要處理的第一個元素和最后一個元素的下一個位置。
這些算法一般可劃分為只讀算法、改寫元素算法或對元素重新排序算法，下面分別敘述之。
只讀算法
find算法
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);
查詢迭代器指定范圍[first, last)范圍內是否有val值。如果有，則返回該值對應的迭代器；否則，返回last表示查找失敗。
accumulate算法
template<class InIt, class T>
T accumulate(InIt first, InIt last, T val);
template<class InIt, class T, class Pred>
T accumulate(InIt first, InIt last, T val, Pred pr);
累加迭代器指定范圍[first, last)范圍內所有元素，再加上累加的初值val，返回累加的結果。第二個函數自定義操作：val = pr(val, *it)。
| 注：用于指定累加起始值的第三個參數是必要的，因為算法對將要累加的元素類型一無所知，沒有別的辦法創建合適的起始值或者關聯的類型。 |
find_first_of算法
template<class FwdIt1, class FwdIt2>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2);
template<class FwdIt1, class FwdIt2, class Pred>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2, Pred pr);
查詢第一段范圍內與第二段范圍內任意元素匹配的元素的位置。如果找到，返回該元素對應的迭代器；否則，返回last1。第二個函數使用判斷：pr(*it1, *it2)來代替第一個函數中的判斷：*it1 == *it2。
寫容器元素的算法
在使用寫元素的算法時，必須確保算法所寫的序列至少足以存儲要寫入的元素。有些算法直接將數據寫入到輸入序列，另外一些則帶有一個額外的迭代器參數指定寫入目標。這類算法將目標迭代器用作輸出的位置。還有第三種算法將指定數目的元素寫入某個序列。
寫入輸入序列的元素
寫入到輸入序列的算法本質上是案例的，因為只會寫入與指定輸入范圍數量相同的元素。如fill算法：
template<class FwdIt, class T>
void fill(FwdIt first, FwdIt last, const T& x);
這個算法將指定范圍內的每個元素都設定為給定的值。如果輸入范圍有效，則可以安全寫入。這個算法只會對輸入范圍內已存在的元素進行寫入操作。
不檢查寫入操作的算法
這類算法如fill_n算法：
template<class OutIt, class Size, class T>
void fill_n(OutIt first, Size n, const T& x);
該算法從迭代器指向的元素開始，將指定數量的元素設置為給定的值。如果目標范圍內的某些元素不存在，則該操作未定義。如下面的代碼將發生不可預料的結果：
vector<int> vec; // empty vector
fill_n(vec.begin(), 10, 0); // disaster behavior
| 注：對指定數目的元素做寫入運算，或者寫到目標迭代的算法，都不檢查目標的大小是否足以存儲要寫入的元素。 |
back_inserter
確保算法有足夠的元素存儲輸出數據的一種方法是使用插入迭代器(insert iterator)。插入迭代器是可以給基礎容器添加元素的迭代器。通常，用迭代器給容器元素賦值時，被賦值的是迭代器所指向的元素。而使用插入迭代器賦值時，則會在容器中添加一個新元素，其值等于賦值運算的右操作數的值。
back_inserter函數是迭代器適配器，其使用一個對象作為實參，并生成一個適應其實參行為的新對象。比如，在下例中，傳遞給back_inserter的實參是一個容器的引用。back_inserter生成一個綁定在該容器上的插入迭代器。在試圖通過這個迭代器給元素賦值時，賦值運算將調用push_back在容器中添加一個具有指定值的元素。因此，用back_inserter改寫上面的代碼可以有效地工作：
vector<int> vec; // empty vector
fill_n(back_inserter(vec), 10, 0); // ok: appends 10 elements to vec
寫入到目標迭代器的算法
第三類算法向目標迭代器寫入未知個數的元素。這類算法最簡單的如copy算法：
template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
copy算法帶有三個迭代器參數：前兩個指定輸入范圍，第三個指向目標序列的第一個元素。
算法的_copy版本
有些算法提供所謂的“_copy”版本。這些算法對輸入序列的元素做處理，但不修改原來的元素，而是創建一個新序列存儲元素的處理結果。
例如，replace算法：
template<caass FwdIt, class T>
void replace(FwdIt first, FwdIt last, const T& vold, const T& vnew);
該算法指定范圍[first, last)內的所有元素值為vold替換為vnew。
如果不想改變原序列，可以用replace_copy算法：
template<class InIt, class OutIt, class T>
OutIt replace_copy(InIt first, InIt last, OutIt x, const T& vold, const T& vnew);
這個算法接受第三個迭代器參數，指定保存替換后的序列的目標位置。例如：
vector<int> vec;
replace(ilist.begin(), ilist.end(), back_inserter(ivec), 1, 10);
調用該函數后，ilist沒有改變，而ivec存儲ilist的一份替換后的副本。
對容器元素重新排序的算法
sort算法
這里只介紹sort和stable_sort這個類排序算法：
template<class RanIt>
void sort(RanIt first, RanIt last);
template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);
template<class RanIt>
void stable_sort(RanIt first, RanIt last);
template<class RanIt, class Pred>
void stable_sort(RanIt first, RanIt last, Pred pr);
sort排序算法是最一般的類型，而stable_sort排序算法是穩定排序。
unique和unique_copy
unique函數“刪除”指定范圍內的重復元素。注意：這里的“刪除”不是真正意義上的刪除，只是在有重復元素時，把后面的元素向前移動覆蓋了原來的元素。函數返回的迭代器指向無重復元素序列最后一個元素的下一個位置。而unique_copy是它的“_copy”版本，返回的是生成的序列的最后一個元素的下一個位置。
template<class FwdIt>
FwdIt unique(FwdIt first, FwdIt last);
template<class FwdIt, class Pred>
FwdIt unique(FwdIt first, FwdIt last, Pred pr);
template<class InIt, class OutIt>
OutIt unique_copy(InIt first, InIt last, OutIt x);
template<class InIt, class OutIt, class Pred>
OutIt unique_copy(InIt first, InIt last, OutIt x, Pred pr);
注意：unique調用后，原序列的前面部分是無重復元素的序列，而后半部分是剩下沒有被覆蓋的序列。這里，需要手動刪除后面的元素序列，范圍由返回的迭代器和容器末端決定。
迭代器
插入迭代器
插入迭代器是一種迭代器適配器，帶有一個容器參數，并生成一個迭代器，用于在指定的容器中插入元素。通過插入迭代器賦值時，迭代器將會插入一個新的元素。C++語言提供了三種插入器，其差別在于插入元素的位置不同：
1）back_inserter，創建使用push_back實現插入的迭代器；
2）front_inserter，使用push_front實現插入；
3）inserter，使用insert實現插入操作。除了所關聯的容器外，inserter還帶有第二個實參：指向插入起始位置的迭代器。
front_inserter的操作類似于back_inserter：該函數將創建一個迭代器，調用它所關聯的基礎容器的push_front成員函數代替賦值操作。注意：只有當容器提供push_front操作時，才能使用front_inserter。在vector或其他沒有push_front運算的容器上使用front_inserter，將產生錯誤。
inserter將產生在指定位置實現插入的迭代器，inserter總是在它的迭代器參數所標明的位置前面插入新元素。看看下面的例子：
list<int> ilst, ilst2, ilst3; //empty lists
// after this loop ilst contains: 1 2 3 4
for (list<int>::value_type i = 0; i != 4; ++i)
ilst.push_front(i + 1);
// after copy ilst2 contains: 4 3 2 1
copy (ilst.begin(), ilst.end(), front_inserter(ilst2));
// after copy ilst3 contains: 1 2 3 4
copy (ilst.begin(), ilst.end(), inserter(ilst3, ilst3.begin()));
iostream 迭代器
雖然iostream類型不是容器，但標準庫同樣提供了在iostream對象上使用的迭代器：istream_iterator用于讀取讀入流，而ostream_iterator用于寫輸出流。這些迭代器將它們所對應的流視為特定類型的元素序列。使用流迭代器時，可以用泛型算法從流對象中讀數據（或將數據寫到流對象中）。
| istream_iterator<T> in(strm); |
創建從輸入流strm中讀取T類型對象的istream_iterator對象 |
| istream_iterator<T> in; |
istream_iterator對象的超出末端迭代器 |
| ostream_iterator<T> out(strm); |
創建將T類型的對象寫到輸出流strm的ostream_iterator對象 |
| ostream_iterator<T> out(strm, delim); |
創建將T類型的對象寫到輸出流strm的ostream_iterator對象，在寫入過程中使用delim作為元素的分隔符。delim是以空字符結束的字符數組 |
流迭代器只定義了最基本的迭代器操作：自增、解引用和賦值。此外，可比較兩個istream迭代器是否相等（或不等）。而ostream迭代器則不提供比較運算。
| it1 == it2 |
比較兩個istream_iterator是否相等（不等）。迭代器讀取的必須是
相同的類型。如果兩個迭代器都是end值，則它們相等。對于兩個都不
|
| it1 != it2 |
指向流結束位置的迭代器，如果它們使用同一個輸入流構造，則它們
相等。
|
| *it |
返回從流中讀取的值 |
| it->mem |
是(*it).mem的同義詞。返回從流中讀取的對象的mem成員 |
| ++it |
通過使用元素類型提供的>>操作符從個輸入流中讀取下一個元素值，
使迭代器向前移動。通常，前綴版本使迭代器在流中向前移動，并返
回對加1后的迭代器的引用。
|
| it++ |
而后綴版本使迭代器在流中向前移動后，返回原值。 |
流迭代器是類模板：任何已定義輸入操作符(>>操作符)的類型都可以定義istream_iterator。類似地，任何已定義輸出操作符(<<操作符)的類型也可以ostream_iterator。
istream_iterator使用舉例：
|
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
int main() {
istream_iterator<int> in_iter(cin);
istream_iterator<int> eof;
//vector<int> vec(in_iter, eof); //do the same work as following loop
vector<int> vec;
while (in_iter != eof)
vec.push_back(*in_iter++);
vector<int>::const_iterator it = vec.begin();
for(; it != vec.end(); ++it)
cout<<*it<<endl;
return 0;
}
|
ostream_iterator使用舉例：
|
#include <iostream>
#include <iterator>
using namespace std;
int main() {
ostream_iterator<string> out_iter(cout, "\n");
istream_iterator<string> in_iter(cin), eof;
while (in_iter != eof)
*out_iter++ = *in_iter++;
return 0;
}
|
流迭代器的限制：
1）不可能從ostream_iterator對象讀入，也不可能寫到istream_iterator對象中；
2）一旦給ostream_iterator對象賦了一個值，寫入就提交了。賦值后，沒有辦法再改變這個值。此外，ostream_iterator對象中每個不同的值都只能正好輸出一次。
3）ostream_iterator沒有->操作符。
與算法一起使用流迭代器，如下面的示例實現從標準輸入讀取一些數，然后將不重復的數寫到標準輸出：
|
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
int main() {
istream_iterator<int> in_it(cin), eof;
vector<int> vec(in_it, eof);
sort(vec.begin(), vec.end());
ostream_iterator<int> out_it(cout, " ");
unique_copy(vec.begin(), vec.end(), out_it);
return 0;
}
|
反向迭代器
反向迭代器是一種反向遍歷容器的迭代器。也就是，從最后一個元素到第一個元素遍歷容器。反向迭代器將自增（和自減）的含義反過來了：對于反向迭代器，++運算將訪問前一個元素，而--運算則訪問下一個元素。
begin(), end(), rbegin(), rend()與容器序列關系示意圖如下：
500)this.width=500;" border=0>
1）反向迭代器需要使用自減操作符：標準容器上的迭代器（reverse_iterator)既支持自增運算，也支持自減運算。但是，流迭代器由于不能反向遍歷流，因此流迭代器不能創建反向迭代器。
2）可以通過reverse_iterator::base()將反向迭代器轉換為普通迭代器使用，從逆序得到普通次序。如下面的例子所示：
|
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
using namespace std;
int main() {
string str = "this 'sentence' is a test";
cout<<"String: "<<str<<endl;
string::iterator it1 = find(str.begin(), str.end(), '\'');
string::iterator it2 = find(++it1, str.end(), '\'');
// output: sentence
cout<<"B-E: "<<string(it1, it2)<<endl;
string::reverse_iterator rit1 = find(str.rbegin(), str.rend(), '\'');
string::reverse_iterator rit2 = find(++rit1, str.rend(), '\'');
// output: ecnetnes
cout<<"R-B-E 1: "<<string(rit1, rit2)<<endl;
// output: sentence
cout<<"R-B-E 2: "<<string(rit2.base(), rit1.base())<<endl;
return 0;
}
|
const 迭代器
在標準庫中，有輸入范圍的泛型算法要求其兩個迭代器類型完全一樣，包括const屬性。要么都是const，要么都是非const，否則無法通過編譯。同樣，它們的返回值迭代器也與參數類型保持一致。
迭代器分類
不同的迭代器支持不同的操作集，而各種算法也要求相應的迭代器具有最小的操作集。因此，可以將算法的迭代器分為下面五類：
| 輸入迭代器
(input iterator)
|
讀，不能寫。支持的操作集：==, !=, 前綴++, 后綴++, *, ->。例如，find, accumulate算法要求這類迭代器。 |
| 輸出迭代器
(output iterator)
|
寫，不能讀。支持的操作集：前綴++, 后綴++, *（只能出現在賦值運算的左操作數上)。推出迭代器要求每個迭代器必須正好寫入一次。例如，ostream_iterator是輸出迭代器，copy算法使用這類迭代器。 |
| 前向迭代器(forward iterator) |
讀和寫，支持輸入迭代器和輸出迭代器提供的所有操作，還支持對同一個元素的多次讀寫。例如，replace算法需要這種迭代器。 |
| 雙向迭代器(bidirectional iterator) |
讀和寫，除了支持前向迭代器的所有操作，還支持前綴--和后綴--，即支持雙向遍歷容器。例如，reverse算法要求這類迭代器。標準庫容器中提供的迭代器都至少達到雙向迭代器的要求。 |
| 隨機訪問迭代器(random-access iterator) |
讀和寫。提供在常量時間內訪問容器任意位置的功能。支持完整的迭代器操作集：1）關系運算：==, !=, <, <=, >, >=；2）算術運算：it + n, it - n, it += n, it -= n以及it1 - it2；3）下標運算：it[n]，等價于*(it + n)。需要隨機訪問迭代器的泛型算法包括sort算法。例如，vector, deque, string迭代器是隨機訪問迭代器，用作訪問內置數組元素的指針也是隨機訪問迭代器。 |
除了輸出迭代器，其他類別的迭代器形成了一個層次結構：需要低級類別迭代器的地方，可使用任意一種更高級的迭代器。例如，對于需要輸入迭代器的算法，可傳遞前向、雙向或隨機訪問迭代器調用該算法。而反之則不行。注意：向算法傳遞無效的迭代器類別所引起的錯誤，無法保證會在編譯時被捕獲到。
map, set, list類型提供雙向迭代器，而string, vector和deque容器上定義的迭代器都是隨機訪問迭代器，用作訪問內置數組元素的指針也是隨機訪問迭代器。istream_iterator是輸入迭代器，ostream_iterator是輸出迭代器。
另外，雖然map和set類型提供雙向迭代器，但關聯容器只能使用這部分算法的一個子集。因為關聯容器的鍵是const對象。因此，關聯容器不能使用任何寫序列元素的算法。只能使用與關聯容器綁在一起的迭代器來提供用于讀操作的實參。因此，在處理算法時，最好將關聯容器上的迭代器視為支持自減運算的輸入迭代器，而不是完整的雙向迭代器。
泛型算法的結構
就像所有的容器都建立在一致的設計模式上一樣，算法也具有共同的設計基礎。
算法最基本的性質是需要使用的迭代器種類。
另一種算法分類方法是前面介紹的按實現的功能分類：只讀算法，不改變元素的值和順序；給指定元素賦新值的算法；將一個元素的值移給另一個元素的算法。
另外，算法還有兩種結構上的算法模式：一種模式是由算法所帶的形參定義；另一種模式則通過兩種函數命名和重載的規范定義。
算法的形參模式
大多數算法采用下面四種形式之一：
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)是輸入范圍，beg, end, dest, beg2, end2都是迭代器。
對于帶有單個目標迭代器的算法：dest形參是一個迭代器，用于指定存儲輸出數據的目標對象。算法假定無論需要寫入多少個元素都是安全的。注意：調用這類算法時，算法是將輸出內容寫到容器中已存在的元素上，所以必須確保輸出容器中有足夠大的容量存儲輸出數據，這也正是通過使用插入迭代器或者ostream_iterator來調用這些算法的原因。
對于帶第二個輸入序列的算法：beg2和end2標記了完整的輸出范圍。而只有beg2的算法將beg2視為第二個輸入范圍的首元素，算法假定以beg2開始的范圍至少與beg和end指定的范圍一樣大。
算法的命名規范
包括兩種重要模式：第一種模式包括測試輸入范圍內元素的算法，第二種模式則應用于輸入范圍內元素的重新排序的算法。
1）區別帶有一個值或一個謂詞函數參數的算法版本
很多算法通過檢查其輸入范圍內的元素實現其功能。這些算法通常要用到標準關系操作符：== 或 < 。其中的大部分算法都提供了第二個版本的算法，允許程序員提供比較或測試函數取代默認的操作符的使用。
例如， 排序算法默認使用 < 操作符，其重載版本帶有一個額外的形參，表示取代默認的 < 操作符。
sort (beg, end); // use < operator to sort the elements
sort (beg, end, comp); // use function named comp to sort the elements
又如，查找算法默認使用 == 操作符。標準庫為這類算法提供另外命名的（而非重載的）版本，帶有謂詞函數形參。對于帶有謂詞函數形參的算法，其名字帶有后綴 _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
標準庫為這類算法提供另外命名的版本，而非重載版本，原因在于這兩種版本的算法帶有相同的參數個數，容易導致二義性。
2）區別是否實現復制的算法版本
默認情況下，算法將重新排列的寫回其范圍。標準庫也為這類算法提供了另外命名的版本，將元素寫到指定的輸出目標。此版本的算法在名字中添加 _copy后綴，例如：
reverse (beg, end);
reverse_copy (beg, end, dest);
第一個版本將輸入序列中的元素反向重新排列；而第二個版本將復制輸入序列中的元素，并將它們以逆序存儲到dest開始的序列中。
容器特有的算法
list容器上的迭代器是雙向的，而不是隨機訪問類型。由于list容器不支持隨機訪問，因此，在此容器上不能使用需要隨機訪問迭代器的算法。如sort類算法。其它有些算法，如merge, remove, reverse, unique等，雖然可以用在list上，但性能太差。list容器結合自己的結構專門實現了更為高效的算法。因此，對于list對象，應該優先使用list容器特有的成員版本，而不是泛型算法。
下表列出了list容器特有的操作：
| lst.merge(lst2)
lst.merge(lst2, comp)
|
將lst2的元素合并到lst中。這兩個list對象必須都已排序。合并后，lst2中元素被刪除，為空。返回void類型
|
| lst.remove(val)
lst.remove_if(unaryPred))
|
調用lst.erase刪除所有等于指定值或滿足謂詞的元素，返回void類型。 |
| lst.reverse() |
反向排列lst中的元素 |
| lst.sort() |
對lst中的元素排序 |
| lst.splice(it, lst2)
lst.splice(it, lst2, it2)
lst.splice(it, beg, end)
|
將lst2的元素移到lst中迭代器it所指向的元素前面。在lst2中刪除移出的元素。第一個版本將lst2的所有元素移到lst中，合并后，lst2為空。lst和lst2不能是同一個list對象。第二個版本只移動it2所指向的元素，這個元素必須是lst2的元素。在這種情況下，lst和lst2可以是同一list對象。第三個版本移動迭代器beg和end標記的范圍內的元素。這兩個可以標記任意list對象的范圍，包括lst。當它們指定lst的一段范圍時，如果it也指向這個范圍內的一個元素，則該操作未定義。 |
| lst.unique()
lst.unique(binaryPred)
|
調用erase刪除同一值的連續版本。第一個版本使用 == 操作符判斷元素是否相等；第二個版本則使用指定的謂詞函數實現判斷。 |
list容器特有的算法與其泛型算法版本之間有兩個重要的差別：1）remove和unique的list版本修改了其關聯的基礎容器：真正刪除了指定的元素；2）list容器提供的merge和splice操作會破壞它們的實參。使用泛型算法的merge版本，合并的序列將寫入目標迭代器指向的對象，而它的兩個輸入序列保持不變。
如果文中有錯誤或遺漏之處，敬請指出，謝謝