題記：本系列學(xué)習(xí)筆記（C++ Primer學(xué)習(xí)筆記）主要目的是討論一些容易被大家忽略或者容易形成錯(cuò)誤認(rèn)識(shí)的內(nèi)容。只適合于有了一定的C++基礎(chǔ)的讀者（至少學(xué)完一本C++教程）。
作者： tyc611, 2007-01-27
本文主要討論C++標(biāo)準(zhǔn)庫(kù)中的泛型算法(generic algorithm)。泛型算法是使用容器的強(qiáng)有力的輔助工具。
如果文中有錯(cuò)誤或遺漏之處，敬請(qǐng)指出，謝謝！
標(biāo)準(zhǔn)庫(kù)為容器類(lèi)型定義的操作很少，并沒(méi)有為每個(gè)容器實(shí)現(xiàn)更多的操作。因?yàn)檫@部分操作可以抽象出來(lái)為所有的容器工作，那就是泛型算法。所謂“泛型”是指這些算法可以應(yīng)用于多種容器類(lèi)型上，而容器內(nèi)的元素類(lèi)型也可以多樣化。標(biāo)準(zhǔn)庫(kù)提供了100多個(gè)泛型算法，主要定義于頭文件<algorithm>中，還有一組泛化的算術(shù)算法定義于頭文件<numeric>中。
大多數(shù)泛型算法是工作于容器的一對(duì)迭代器所標(biāo)識(shí)的范圍，并完全通過(guò)迭代器來(lái)實(shí)現(xiàn)其功能。這段由迭代器指定的范圍稱(chēng)為“輸入范圍”。帶有輸入范圍參數(shù)的算法總是使用前兩個(gè)參數(shù)標(biāo)記該范圍，分別指向要處理的第一個(gè)元素和最后一個(gè)元素的下一個(gè)位置。
這些算法一般可劃分為只讀算法、改寫(xiě)元素算法或?qū)υ刂匦屡判蛩惴ǎ旅娣謩e敘述之。
只讀算法
find算法
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);
查詢(xún)迭代器指定范圍[first, last)范圍內(nèi)是否有val值。如果有，則返回該值對(duì)應(yīng)的迭代器；否則，返回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)范圍內(nèi)所有元素，再加上累加的初值val，返回累加的結(jié)果。第二個(gè)函數(shù)自定義操作：val = pr(val, *it)。
| 注：用于指定累加起始值的第三個(gè)參數(shù)是必要的，因?yàn)樗惴▽?duì)將要累加的元素類(lèi)型一無(wú)所知，沒(méi)有別的辦法創(chuàng)建合適的起始值或者關(guān)聯(lián)的類(lèi)型。 |
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);
查詢(xún)第一段范圍內(nèi)與第二段范圍內(nèi)任意元素匹配的元素的位置。如果找到，返回該元素對(duì)應(yīng)的迭代器；否則，返回last1。第二個(gè)函數(shù)使用判斷：pr(*it1, *it2)來(lái)代替第一個(gè)函數(shù)中的判斷：*it1 == *it2。
寫(xiě)容器元素的算法
在使用寫(xiě)元素的算法時(shí)，必須確保算法所寫(xiě)的序列至少足以存儲(chǔ)要寫(xiě)入的元素。有些算法直接將數(shù)據(jù)寫(xiě)入到輸入序列，另外一些則帶有一個(gè)額外的迭代器參數(shù)指定寫(xiě)入目標(biāo)。這類(lèi)算法將目標(biāo)迭代器用作輸出的位置。還有第三種算法將指定數(shù)目的元素寫(xiě)入某個(gè)序列。
寫(xiě)入輸入序列的元素
寫(xiě)入到輸入序列的算法本質(zhì)上是案例的，因?yàn)橹粫?huì)寫(xiě)入與指定輸入范圍數(shù)量相同的元素。如fill算法：
template<class FwdIt, class T>
void fill(FwdIt first, FwdIt last, const T& x);
這個(gè)算法將指定范圍內(nèi)的每個(gè)元素都設(shè)定為給定的值。如果輸入范圍有效，則可以安全寫(xiě)入。這個(gè)算法只會(huì)對(duì)輸入范圍內(nèi)已存在的元素進(jìn)行寫(xiě)入操作。
不檢查寫(xiě)入操作的算法
這類(lèi)算法如fill_n算法：
template<class OutIt, class Size, class T>
void fill_n(OutIt first, Size n, const T& x);
該算法從迭代器指向的元素開(kāi)始，將指定數(shù)量的元素設(shè)置為給定的值。如果目標(biāo)范圍內(nèi)的某些元素不存在，則該操作未定義。如下面的代碼將發(fā)生不可預(yù)料的結(jié)果：
vector<int> vec; // empty vector
fill_n(vec.begin(), 10, 0); // disaster behavior
| 注：對(duì)指定數(shù)目的元素做寫(xiě)入運(yùn)算，或者寫(xiě)到目標(biāo)迭代的算法，都不檢查目標(biāo)的大小是否足以存儲(chǔ)要寫(xiě)入的元素。 |
back_inserter
確保算法有足夠的元素存儲(chǔ)輸出數(shù)據(jù)的一種方法是使用插入迭代器(insert iterator)。插入迭代器是可以給基礎(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è)綁定在該容器上的插入迭代器。在試圖通過(guò)這個(gè)迭代器給元素賦值時(shí)，賦值運(yùn)算將調(diào)用push_back在容器中添加一個(gè)具有指定值的元素。因此，用back_inserter改寫(xiě)上面的代碼可以有效地工作：
vector<int> vec; // empty vector
fill_n(back_inserter(vec), 10, 0); // ok: appends 10 elements to vec
寫(xiě)入到目標(biāo)迭代器的算法
第三類(lèi)算法向目標(biāo)迭代器寫(xiě)入未知個(gè)數(shù)的元素。這類(lèi)算法最簡(jiǎn)單的如copy算法：
template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
copy算法帶有三個(gè)迭代器參數(shù)：前兩個(gè)指定輸入范圍，第三個(gè)指向目標(biāo)序列的第一個(gè)元素。
算法的_copy版本
有些算法提供所謂的“_copy”版本。這些算法對(duì)輸入序列的元素做處理，但不修改原來(lái)的元素，而是創(chuàng)建一個(gè)新序列存儲(chǔ)元素的處理結(jié)果。
例如，replace算法：
template<caass FwdIt, class T>
void replace(FwdIt first, FwdIt last, const T& vold, const T& vnew);
該算法指定范圍[first, last)內(nèi)的所有元素值為vold替換為vnew。
如果不想改變?cè)蛄校梢杂胷eplace_copy算法：
template<class InIt, class OutIt, class T>
OutIt replace_copy(InIt first, InIt last, OutIt x, const T& vold, const T& vnew);
這個(gè)算法接受第三個(gè)迭代器參數(shù)，指定保存替換后的序列的目標(biāo)位置。例如：
vector<int> vec;
replace(ilist.begin(), ilist.end(), back_inserter(ivec), 1, 10);
調(diào)用該函數(shù)后，ilist沒(méi)有改變，而ivec存儲(chǔ)ilist的一份替換后的副本。
對(duì)容器元素重新排序的算法
sort算法
這里只介紹sort和stable_sort這個(gè)類(lèi)排序算法：
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排序算法是最一般的類(lèi)型，而stable_sort排序算法是穩(wěn)定排序。
unique和unique_copy
unique函數(shù)“刪除”指定范圍內(nèi)的重復(fù)元素。注意：這里的“刪除”不是真正意義上的刪除，只是在有重復(fù)元素時(shí)，把后面的元素向前移動(dòng)覆蓋了原來(lái)的元素。函數(shù)返回的迭代器指向無(wú)重復(fù)元素序列最后一個(gè)元素的下一個(gè)位置。而unique_copy是它的“_copy”版本，返回的是生成的序列的最后一個(gè)元素的下一個(gè)位置。
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調(diào)用后，原序列的前面部分是無(wú)重復(fù)元素的序列，而后半部分是剩下沒(méi)有被覆蓋的序列。這里，需要手動(dòng)刪除后面的元素序列，范圍由返回的迭代器和容器末端決定。
迭代器
插入迭代器
插入迭代器是一種迭代器適配器，帶有一個(gè)容器參數(shù)，并生成一個(gè)迭代器，用于在指定的容器中插入元素。通過(guò)插入迭代器賦值時(shí)，迭代器將會(huì)插入一個(gè)新的元素。C++語(yǔ)言提供了三種插入器，其差別在于插入元素的位置不同：
1）back_inserter，創(chuàng)建使用push_back實(shí)現(xiàn)插入的迭代器；
2）front_inserter，使用push_front實(shí)現(xiàn)插入；
3）inserter，使用insert實(shí)現(xiàn)插入操作。除了所關(guān)聯(lián)的容器外，inserter還帶有第二個(gè)實(shí)參：指向插入起始位置的迭代器。
front_inserter的操作類(lèi)似于back_inserter：該函數(shù)將創(chuàng)建一個(gè)迭代器，調(diào)用它所關(guān)聯(lián)的基礎(chǔ)容器的push_front成員函數(shù)代替賦值操作。注意：只有當(dāng)容器提供push_front操作時(shí)，才能使用front_inserter。在vector或其他沒(méi)有push_front運(yùn)算的容器上使用front_inserter，將產(chǎn)生錯(cuò)誤。
inserter將產(chǎn)生在指定位置實(shí)現(xiàn)插入的迭代器，inserter總是在它的迭代器參數(shù)所標(biāo)明的位置前面插入新元素。看看下面的例子：
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類(lèi)型不是容器，但標(biāo)準(zhǔn)庫(kù)同樣提供了在iostream對(duì)象上使用的迭代器：istream_iterator用于讀取讀入流，而ostream_iterator用于寫(xiě)輸出流。這些迭代器將它們所對(duì)應(yīng)的流視為特定類(lèi)型的元素序列。使用流迭代器時(shí)，可以用泛型算法從流對(duì)象中讀數(shù)據(jù)（或?qū)?shù)據(jù)寫(xiě)到流對(duì)象中）。
| istream_iterator<T> in(strm); |
創(chuàng)建從輸入流strm中讀取T類(lèi)型對(duì)象的istream_iterator對(duì)象 |
| istream_iterator<T> in; |
istream_iterator對(duì)象的超出末端迭代器 |
| ostream_iterator<T> out(strm); |
創(chuàng)建將T類(lèi)型的對(duì)象寫(xiě)到輸出流strm的ostream_iterator對(duì)象 |
| ostream_iterator<T> out(strm, delim); |
創(chuàng)建將T類(lèi)型的對(duì)象寫(xiě)到輸出流strm的ostream_iterator對(duì)象，在寫(xiě)入過(guò)程中使用delim作為元素的分隔符。delim是以空字符結(jié)束的字符數(shù)組 |
流迭代器只定義了最基本的迭代器操作：自增、解引用和賦值。此外，可比較兩個(gè)istream迭代器是否相等（或不等）。而ostream迭代器則不提供比較運(yùn)算。
| it1 == it2 |
比較兩個(gè)istream_iterator是否相等（不等）。迭代器讀取的必須是
相同的類(lèi)型。如果兩個(gè)迭代器都是end值，則它們相等。對(duì)于兩個(gè)都不
|
| it1 != it2 |
指向流結(jié)束位置的迭代器，如果它們使用同一個(gè)輸入流構(gòu)造，則它們
相等。
|
| *it |
返回從流中讀取的值 |
| it->mem |
是(*it).mem的同義詞。返回從流中讀取的對(duì)象的mem成員 |
| ++it |
通過(guò)使用元素類(lèi)型提供的>>操作符從個(gè)輸入流中讀取下一個(gè)元素值，
使迭代器向前移動(dòng)。通常，前綴版本使迭代器在流中向前移動(dòng)，并返
回對(duì)加1后的迭代器的引用。
|
| it++ |
而后綴版本使迭代器在流中向前移動(dòng)后，返回原值。 |
流迭代器是類(lèi)模板：任何已定義輸入操作符(>>操作符)的類(lèi)型都可以定義istream_iterator。類(lèi)似地，任何已定義輸出操作符(<<操作符)的類(lèi)型也可以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對(duì)象讀入，也不可能寫(xiě)到istream_iterator對(duì)象中；
2）一旦給ostream_iterator對(duì)象賦了一個(gè)值，寫(xiě)入就提交了。賦值后，沒(méi)有辦法再改變這個(gè)值。此外，ostream_iterator對(duì)象中每個(gè)不同的值都只能正好輸出一次。
3）ostream_iterator沒(méi)有->操作符。
與算法一起使用流迭代器，如下面的示例實(shí)現(xiàn)從標(biāo)準(zhǔn)輸入讀取一些數(shù)，然后將不重復(fù)的數(shù)寫(xiě)到標(biāo)準(zhǔn)輸出：
|
#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;
}
|
反向迭代器
反向迭代器是一種反向遍歷容器的迭代器。也就是，從最后一個(gè)元素到第一個(gè)元素遍歷容器。反向迭代器將自增（和自減）的含義反過(guò)來(lái)了：對(duì)于反向迭代器，++運(yùn)算將訪問(wèn)前一個(gè)元素，而--運(yùn)算則訪問(wèn)下一個(gè)元素。
begin(), end(), rbegin(), rend()與容器序列關(guān)系示意圖如下：
500)this.width=500;" border=0>
1）反向迭代器需要使用自減操作符：標(biāo)準(zhǔn)容器上的迭代器（reverse_iterator)既支持自增運(yùn)算，也支持自減運(yùn)算。但是，流迭代器由于不能反向遍歷流，因此流迭代器不能創(chuàng)建反向迭代器。
2）可以通過(guò)reverse_iterator::base()將反向迭代器轉(zhuǎn)換為普通迭代器使用，從逆序得到普通次序。如下面的例子所示：
|
#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 迭代器
在標(biāo)準(zhǔn)庫(kù)中，有輸入范圍的泛型算法要求其兩個(gè)迭代器類(lèi)型完全一樣，包括const屬性。要么都是const，要么都是非const，否則無(wú)法通過(guò)編譯。同樣，它們的返回值迭代器也與參數(shù)類(lèi)型保持一致。
迭代器分類(lèi)
不同的迭代器支持不同的操作集，而各種算法也要求相應(yīng)的迭代器具有最小的操作集。因此，可以將算法的迭代器分為下面五類(lèi)：
| 輸入迭代器
(input iterator)
|
讀，不能寫(xiě)。支持的操作集：==, !=, 前綴++, 后綴++, *, ->。例如，find, accumulate算法要求這類(lèi)迭代器。 |
| 輸出迭代器
(output iterator)
|
寫(xiě)，不能讀。支持的操作集：前綴++, 后綴++, *（只能出現(xiàn)在賦值運(yùn)算的左操作數(shù)上)。推出迭代器要求每個(gè)迭代器必須正好寫(xiě)入一次。例如，ostream_iterator是輸出迭代器，copy算法使用這類(lèi)迭代器。 |
| 前向迭代器(forward iterator) |
讀和寫(xiě)，支持輸入迭代器和輸出迭代器提供的所有操作，還支持對(duì)同一個(gè)元素的多次讀寫(xiě)。例如，replace算法需要這種迭代器。 |
| 雙向迭代器(bidirectional iterator) |
讀和寫(xiě)，除了支持前向迭代器的所有操作，還支持前綴--和后綴--，即支持雙向遍歷容器。例如，reverse算法要求這類(lèi)迭代器。標(biāo)準(zhǔn)庫(kù)容器中提供的迭代器都至少達(dá)到雙向迭代器的要求。 |
| 隨機(jī)訪問(wèn)迭代器(random-access iterator) |
讀和寫(xiě)。提供在常量時(shí)間內(nèi)訪問(wèn)容器任意位置的功能。支持完整的迭代器操作集：1）關(guān)系運(yùn)算：==, !=, <, <=, >, >=；2）算術(shù)運(yùn)算：it + n, it - n, it += n, it -= n以及it1 - it2；3）下標(biāo)運(yùn)算：it[n]，等價(jià)于*(it + n)。需要隨機(jī)訪問(wèn)迭代器的泛型算法包括sort算法。例如，vector, deque, string迭代器是隨機(jī)訪問(wèn)迭代器，用作訪問(wèn)內(nèi)置數(shù)組元素的指針也是隨機(jī)訪問(wèn)迭代器。 |
除了輸出迭代器，其他類(lèi)別的迭代器形成了一個(gè)層次結(jié)構(gòu)：需要低級(jí)類(lèi)別迭代器的地方，可使用任意一種更高級(jí)的迭代器。例如，對(duì)于需要輸入迭代器的算法，可傳遞前向、雙向或隨機(jī)訪問(wèn)迭代器調(diào)用該算法。而反之則不行。注意：向算法傳遞無(wú)效的迭代器類(lèi)別所引起的錯(cuò)誤，無(wú)法保證會(huì)在編譯時(shí)被捕獲到。
map, set, list類(lèi)型提供雙向迭代器，而string, vector和deque容器上定義的迭代器都是隨機(jī)訪問(wèn)迭代器，用作訪問(wèn)內(nèi)置數(shù)組元素的指針也是隨機(jī)訪問(wèn)迭代器。istream_iterator是輸入迭代器，ostream_iterator是輸出迭代器。
另外，雖然map和set類(lèi)型提供雙向迭代器，但關(guān)聯(lián)容器只能使用這部分算法的一個(gè)子集。因?yàn)殛P(guān)聯(lián)容器的鍵是const對(duì)象。因此，關(guān)聯(lián)容器不能使用任何寫(xiě)序列元素的算法。只能使用與關(guān)聯(lián)容器綁在一起的迭代器來(lái)提供用于讀操作的實(shí)參。因此，在處理算法時(shí)，最好將關(guān)聯(lián)容器上的迭代器視為支持自減運(yùn)算的輸入迭代器，而不是完整的雙向迭代器。
泛型算法的結(jié)構(gòu)
就像所有的容器都建立在一致的設(shè)計(jì)模式上一樣，算法也具有共同的設(shè)計(jì)基礎(chǔ)。
算法最基本的性質(zhì)是需要使用的迭代器種類(lèi)。
另一種算法分類(lèi)方法是前面介紹的按實(shí)現(xiàn)的功能分類(lèi)：只讀算法，不改變?cè)氐闹岛晚樞颍唤o指定元素賦新值的算法；將一個(gè)元素的值移給另一個(gè)元素的算法。
另外，算法還有兩種結(jié)構(gòu)上的算法模式：一種模式是由算法所帶的形參定義；另一種模式則通過(guò)兩種函數(shù)命名和重載的規(guī)范定義。
算法的形參模式
大多數(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)是輸入范圍，beg, end, dest, beg2, end2都是迭代器。
對(duì)于帶有單個(gè)目標(biāo)迭代器的算法：dest形參是一個(gè)迭代器，用于指定存儲(chǔ)輸出數(shù)據(jù)的目標(biāo)對(duì)象。算法假定無(wú)論需要寫(xiě)入多少個(gè)元素都是安全的。注意：調(diào)用這類(lèi)算法時(shí)，算法是將輸出內(nèi)容寫(xiě)到容器中已存在的元素上，所以必須確保輸出容器中有足夠大的容量存儲(chǔ)輸出數(shù)據(jù)，這也正是通過(guò)使用插入迭代器或者ostream_iterator來(lái)調(diào)用這些算法的原因。
對(duì)于帶第二個(gè)輸入序列的算法：beg2和end2標(biāo)記了完整的輸出范圍。而只有beg2的算法將beg2視為第二個(gè)輸入范圍的首元素，算法假定以beg2開(kāi)始的范圍至少與beg和end指定的范圍一樣大。
算法的命名規(guī)范
包括兩種重要模式：第一種模式包括測(cè)試輸入范圍內(nèi)元素的算法，第二種模式則應(yīng)用于輸入范圍內(nèi)元素的重新排序的算法。
1）區(qū)別帶有一個(gè)值或一個(gè)謂詞函數(shù)參數(shù)的算法版本
很多算法通過(guò)檢查其輸入范圍內(nèi)的元素實(shí)現(xiàn)其功能。這些算法通常要用到標(biāo)準(zhǔn)關(guān)系操作符：== 或 < 。其中的大部分算法都提供了第二個(gè)版本的算法，允許程序員提供比較或測(cè)試函數(shù)取代默認(rèn)的操作符的使用。
例如， 排序算法默認(rèn)使用 < 操作符，其重載版本帶有一個(gè)額外的形參，表示取代默認(rèn)的 < 操作符。
sort (beg, end); // use < operator to sort the elements
sort (beg, end, comp); // use function named comp to sort the elements
又如，查找算法默認(rèn)使用 == 操作符。標(biāo)準(zhǔn)庫(kù)為這類(lèi)算法提供另外命名的（而非重載的）版本，帶有謂詞函數(shù)形參。對(duì)于帶有謂詞函數(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
標(biāo)準(zhǔn)庫(kù)為這類(lèi)算法提供另外命名的版本，而非重載版本，原因在于這兩種版本的算法帶有相同的參數(shù)個(gè)數(shù)，容易導(dǎo)致二義性。
2）區(qū)別是否實(shí)現(xiàn)復(fù)制的算法版本
默認(rèn)情況下，算法將重新排列的寫(xiě)回其范圍。標(biāo)準(zhǔn)庫(kù)也為這類(lèi)算法提供了另外命名的版本，將元素寫(xiě)到指定的輸出目標(biāo)。此版本的算法在名字中添加 _copy后綴，例如：
reverse (beg, end);
reverse_copy (beg, end, dest);
第一個(gè)版本將輸入序列中的元素反向重新排列；而第二個(gè)版本將復(fù)制輸入序列中的元素，并將它們以逆序存儲(chǔ)到dest開(kāi)始的序列中。
容器特有的算法
list容器上的迭代器是雙向的，而不是隨機(jī)訪問(wèn)類(lèi)型。由于list容器不支持隨機(jī)訪問(wèn)，因此，在此容器上不能使用需要隨機(jī)訪問(wèn)迭代器的算法。如sort類(lèi)算法。其它有些算法，如merge, remove, reverse, unique等，雖然可以用在list上，但性能太差。list容器結(jié)合自己的結(jié)構(gòu)專(zhuān)門(mén)實(shí)現(xiàn)了更為高效的算法。因此，對(duì)于list對(duì)象，應(yīng)該優(yōu)先使用list容器特有的成員版本，而不是泛型算法。
下表列出了list容器特有的操作：
| lst.merge(lst2)
lst.merge(lst2, comp)
|
將lst2的元素合并到lst中。這兩個(gè)list對(duì)象必須都已排序。合并后，lst2中元素被刪除，為空。返回void類(lèi)型
|
| lst.remove(val)
lst.remove_if(unaryPred))
|
調(diào)用lst.erase刪除所有等于指定值或滿足謂詞的元素，返回void類(lèi)型。 |
| lst.reverse() |
反向排列l(wèi)st中的元素 |
| lst.sort() |
對(duì)lst中的元素排序 |
| lst.splice(it, lst2)
lst.splice(it, lst2, it2)
lst.splice(it, beg, end)
|
將lst2的元素移到lst中迭代器it所指向的元素前面。在lst2中刪除移出的元素。第一個(gè)版本將lst2的所有元素移到lst中，合并后，lst2為空。lst和lst2不能是同一個(gè)list對(duì)象。第二個(gè)版本只移動(dòng)it2所指向的元素，這個(gè)元素必須是lst2的元素。在這種情況下，lst和lst2可以是同一list對(duì)象。第三個(gè)版本移動(dòng)迭代器beg和end標(biāo)記的范圍內(nèi)的元素。這兩個(gè)可以標(biāo)記任意list對(duì)象的范圍，包括lst。當(dāng)它們指定lst的一段范圍時(shí)，如果it也指向這個(gè)范圍內(nèi)的一個(gè)元素，則該操作未定義。 |
| lst.unique()
lst.unique(binaryPred)
|
調(diào)用erase刪除同一值的連續(xù)版本。第一個(gè)版本使用 == 操作符判斷元素是否相等；第二個(gè)版本則使用指定的謂詞函數(shù)實(shí)現(xiàn)判斷。 |
list容器特有的算法與其泛型算法版本之間有兩個(gè)重要的差別：1）remove和unique的list版本修改了其關(guān)聯(lián)的基礎(chǔ)容器：真正刪除了指定的元素；2）list容器提供的merge和splice操作會(huì)破壞它們的實(shí)參。使用泛型算法的merge版本，合并的序列將寫(xiě)入目標(biāo)迭代器指向的對(duì)象，而它的兩個(gè)輸入序列保持不變。
如果文中有錯(cuò)誤或遺漏之處，敬請(qǐng)指出，謝謝