泛型算法
算法為了保持獨立性，不使用容器類型，而使用迭代器。
算法絕不執行容器操作。算法僅僅是根據迭代器和迭代器操作來操作的。因此所有會改變迭代器的操作在通用算法里都不會出現。例如增加或刪除元素。但是這些通用算法有可能會修改容器中元素的值，也可能會在容器中移動元素。
11.2 初窺算法
必須要包含一下的頭文件：
#include <algorithm>
#include <numeric>
只讀算法
accumulate
這個算法的參數很好說明了算法實際上是不知道元素的類型的。第三個參數指定了起始值，因為accumnulate不知道它正在匯總的元素的類型。
|
int sum = accumulate(vec.begin(), vec.end(), 42);
|
另一個例子：
|
string sum = accumulate(v.begin(), v.end(), string(""));
|
這里一定要指定起始值是string，而絕不能寫成字符串常量，因為字符串常量對應的數據類型是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 標準庫為 string 對象與 char* 對象定義了相等（==）操作符。
總結一下迭代器實參類型
l 標記范圍的兩個實參類型必須精確匹配，必須指向同一個容器中的元素（或者超出容器末端的下一位置），并且如果兩者不相等，則第一個迭代器通過不斷地自增，必須可以到達第二個迭代器。
l 帶有兩對迭代器參數。每對迭代器中，兩個實參的類型必須精確匹配，但不要求兩對之間的類型匹配。特別是，元素可存儲在不同類型序列中，只要這兩序列的元素可以比較即可。
寫容器算法
寫容器算法最重要的一點是必須保證算法所寫的序列至少要和被寫入的元素數目一樣大。（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.）就是說如果指定的要寫入的序列范圍必須是有效的，必須大于要寫入的元素數目，就是說不能越界。
看個最一目了然的例子就是：
|
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之所以安全，是因為如果指定的范圍越界，它執行的并不是數據修改操作而是數據添加操作。
容器元素重新排序算法
unique
sort
stable_sort
謂詞predicates
再次解讀迭代器Iterators
三類迭代器：
l insert iterators插入迭代器
l iostream iterators
l reverse iterators反向迭代器
insert iterators
inserter是迭代器適配器，它和容器綁定，產生一個迭代器，這個迭代器向綁定的容器插入元素。當我們通過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創建一個迭代器
- front_inserter: 使用push_front創建一個迭代器
- inserter：在指定的位置后創建迭代器
|
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這兩種迭代器的最經典的應用，輸入轉輸出，有這個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中讀入數據，同時也不能向istream_iterator寫入數據（It is not possible to read from an ostream_iterator, and it is not possible to write to an istream_iterator.）
2. 一旦給ostream_iterator賦值，這個寫入的操作就提交了。一旦賦值，在后續的操作中就不能修改。此外，每個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里沒有->操作。
基于流迭代器使用算法
既然流迭代器基本上可以看做一般意義上的迭代器，那么前面所描述的算法應該同時也適用在流迭代器上。于是，針對流迭代器，我們也可以進行排序，比較等算法操作。
|
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
從這張圖上可以看出普通迭代器和反向迭代器的區別，另外二者都能夠執行自增和自減操作，形式是一樣的，但本質是不同的。例如形式上都是自增，迭代器都會由begin向end方向移動，但是二者卻是反方向的。這樣做的最大好處是：我們能夠透明地使用算法向前或者向后處理容器。
利用迭代器處理string
可以達到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;
|
反向迭代器可以代表迭代器范圍以及這個范圍是不對稱的事實產生一個重要的結論。當我們用一般的迭代器對反向迭代器初始化或者賦值時，所得到的迭代器所指向的元素和初始值不一樣。（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.）
泛型算法結構
Nothing to say。
其實就是對算法進行了分類，同時對于算法的命名習慣加以闡述，看完了，覺得跳過也無妨哈。
容器特有算法
就是針對list，為了性能優化，對于算法，list重新實現。