泛型算法
算法為了保持獨(dú)立性，不使用容器類型，而使用迭代器。
算法絕不執(zhí)行容器操作。算法僅僅是根據(jù)迭代器和迭代器操作來操作的。因此所有會改變迭代器的操作在通用算法里都不會出現(xiàn)。例如增加或刪除元素。但是這些通用算法有可能會修改容器中元素的值，也可能會在容器中移動元素。
11.2 初窺算法
必須要包含一下的頭文件：
#include <algorithm>
#include <numeric>
只讀算法
accumulate
這個算法的參數(shù)很好說明了算法實際上是不知道元素的類型的。第三個參數(shù)指定了起始值，因為accumnulate不知道它正在匯總的元素的類型。
|
int sum = accumulate(vec.begin(), vec.end(), 42);
|
另一個例子：
|
string sum = accumulate(v.begin(), v.end(), string(""));
|
這里一定要指定起始值是string，而絕不能寫成字符串常量，因為字符串常量對應(yīng)的數(shù)據(jù)類型是const char*。
有趣！
find_first_of
需要兩對迭代器：
|
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;
}
|
roster1是list，roster2可以是deque，vector，只要我們可以用==操作比較這兩個序列中的元素。尤其是：如果 roster1 是 list<string> 對象，則 roster2 可以是 vector<char*> 對象，因為 string 標(biāo)準(zhǔn)庫為 string 對象與 char* 對象定義了相等（==）操作符。
總結(jié)一下迭代器實參類型
l 標(biāo)記范圍的兩個實參類型必須精確匹配，必須指向同一個容器中的元素（或者超出容器末端的下一位置），并且如果兩者不相等，則第一個迭代器通過不斷地自增，必須可以到達(dá)第二個迭代器。
l 帶有兩對迭代器參數(shù)。每對迭代器中，兩個實參的類型必須精確匹配，但不要求兩對之間的類型匹配。特別是，元素可存儲在不同類型序列中，只要這兩序列的元素可以比較即可。
寫容器算法
寫容器算法最重要的一點(diǎn)是必須保證算法所寫的序列至少要和被寫入的元素數(shù)目一樣大。（we must take care to ensure that the sequence into which the algorithm writes is at least as large as the number of elements being written.）就是說如果指定的要寫入的序列范圍必須是有效的，必須大于要寫入的元素數(shù)目，就是說不能越界。
看個最一目了然的例子就是：
|
vector<int> vec; // empty vector
// disaster: attempts to write to 10 (nonexistent) elements in vec
fill_n(vec.begin(), 10, 0);
|
back_inserter
使用back_inserter之所以安全，是因為如果指定的范圍越界，它執(zhí)行的并不是數(shù)據(jù)修改操作而是數(shù)據(jù)添加操作。
容器元素重新排序算法
unique
sort
stable_sort
謂詞predicates
再次解讀迭代器Iterators
三類迭代器：
l insert iterators插入迭代器
l iostream iterators
l reverse iterators反向迭代器
insert iterators
inserter是迭代器適配器，它和容器綁定，產(chǎn)生一個迭代器，這個迭代器向綁定的容器插入元素。當(dāng)我們通過inserter迭代器賦值時，迭代器插入新的元素。（An inserter is an iterator adaptor that takes a container and yields an iterator that inserts elements into the specified container. When we assign through an insert iterator, the iterator inserts a new element.）
又分成3類：
- back_inserter：使用push_back創(chuàng)建一個迭代器
- front_inserter: 使用push_front創(chuàng)建一個迭代器
- inserter：在指定的位置后創(chuàng)建迭代器
|
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()));
|
iostream iterators
istream_iterator:讀input stream
ostream_iterator:寫output stream
定義流迭代器stream Iterators
流迭代器都是模板Templates。Example:
|
istream_iterator<int> cin_it(cin); // reads ints1 from cin
istream_iterator<int> end_of_stream; // end iterator value
while(cin_it != end_of_stream)
{
//do something
}
// writes Sales_items from the ofstream named outfile
// each element is followed by a space
ofstream outfile;
ostream_iterator<Sales_item> output(outfile, " ");
|
istream_iterator上的操作
++it & it++
迭代器加1，一般前綴加1，返回的是增加后的迭代器的引用。后綴加1，迭代器也加1，但是返回的是未加1的那個值。
大師給出了一個istream_iterator和ostream_iterator這兩種迭代器的最經(jīng)典的應(yīng)用，輸入轉(zhuǎn)輸出，有這個sample這是很容易理解這兩個東西：
|
// 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++;
|
流迭代器的限制
1. 不能從ostream_iterator中讀入數(shù)據(jù)，同時也不能向istream_iterator寫入數(shù)據(jù)（It is not possible to read from an ostream_iterator, and it is not possible to write to an istream_iterator.）
2. 一旦給ostream_iterator賦值，這個寫入的操作就提交了。一旦賦值，在后續(xù)的操作中就不能修改。此外，每個ostream_iterator只能用作輸出一次。（Once we assign a value to an ostream_iterator, the write is committed. There is no way to subsequently change a value once it is assigned. Moreover, each distinct value of an ostream_iterator is expected to be used for output exactly once.）
3. 在ostream_iterator里沒有->操作。
基于流迭代器使用算法
既然流迭代器基本上可以看做一般意義上的迭代器，那么前面所描述的算法應(yīng)該同時也適用在流迭代器上。于是，針對流迭代器，我們也可以進(jì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);
|
reverse iterators
從這張圖上可以看出普通迭代器和反向迭代器的區(qū)別，另外二者都能夠執(zhí)行自增和自減操作，形式是一樣的，但本質(zhì)是不同的。例如形式上都是自增，迭代器都會由begin向end方向移動，但是二者卻是反方向的。這樣做的最大好處是：我們能夠透明地使用算法向前或者向后處理容器。
利用迭代器處理string
可以達(dá)到java中StringToken的功能：我喜歡這段代碼
|
// find first element in a comma-separated list
string::iterator comma = find(line.begin(), line.end(), ',');
cout << string(line.begin(), comma) << endl;
|
反向迭代器獲得最后一個單詞：
|
// find last element in a comma-separated list
string::reverse_iterator rcomma = find(line.rbegin(), line.rend(), ',');
// wrong: will generate the word in reverse order
cout << string(rcomma.base(), line.end()) << endl;
|
反向迭代器可以代表迭代器范圍以及這個范圍是不對稱的事實產(chǎn)生一個重要的結(jié)論。當(dāng)我們用一般的迭代器對反向迭代器初始化或者賦值時，所得到的迭代器所指向的元素和初始值不一樣。（The fact that reverse iterators are intended to represent ranges and that these ranges are asymmetric has an important consequence. When we initialize or assign a reverse iterator from a plain iterator, the resulting iterator does not refer to the same element as the original.）
泛型算法結(jié)構(gòu)
Nothing to say。
其實就是對算法進(jìn)行了分類，同時對于算法的命名習(xí)慣加以闡述，看完了，覺得跳過也無妨哈。
容器特有算法
就是針對list，為了性能優(yōu)化，對于算法，list重新實現(xiàn)。