泛型算法
算法为了保持独立性，不使用容器类型，而使用迭代器。
算法绝不执行容器操作。算法仅仅是根据迭代器和迭代器操作来操作的。因此所有会改变迭代器的操作在通用算法里都不会出现。例如增加或删除元素。但是这些通用算法有可能会修改容器中元素的值，也可能会在容器中移动元素。
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重新实现。