泛型算法 - 二【C++ Primer 学习笔记 - 第十一章】
流迭代器都是类模板：
任何已定义输入操作符（>>） 的类型都可以定义 istream_iterator
任何已定义输出操作符（<<） 的类型都可以定义 ostream_iterator
vector<int> ivec; // istream_iterator 可以与特定流绑定， // 也可以不提供实参，指向超出末端位置 istream_iterator<int> in_iter(cin); istream_iterator<int> eof; // #include <fstream> ofstream outfile; // ostream_iterator 必须绑定特定流 // 第二个参数可选，指定写入输出流时的分隔符（必须是C风格字符串） ostream_iterator<int> output(outfile, " "); // 读取 cin，直到文件结束，或者输入的不是 int 类型为止 while(in_iter != eof) ivec.push_back(*in_iter++); // 等效于上面的循环 vector<int> ivec2(in_iter, eof);
ostream_iterator<string> out_iter(cout, "\n"); istream_iterator<string> in_iter(cin); istream_iterator<string> eof; while(in_iter != eof) *out_iter++ = *in_iter++;
// P352：类类型上使用 istream_iterator
istream_iterator<int> cin_it(cin); istream_iterator<int> end_of_stream; vector<int> ivec(cin_it, end_of_stream); sort(ivec.begin(), ivec.end()); ostream_iterator<int> output(cout, " "); unique_copy(ivec.begin(), ivec.end(), output);
反向迭代器
vector<int> ivec; for (vector<int>::size_type i=0; i != 10; i++) ivec.push_back(i); // 反向输出 vector<int>::reverse_iterator r_iter; for(r_iter=ivec.rbegin(); r_iter!=ivec.rend(); ++r_iter) cout << *r_iter << endl; // 正常的升序排列 sort(ivec.begin(), ivec.end()); // 利用反向迭代器，实现降序排列 sort(ivec.rbegin(), ivec.rend());
显然，反向迭代器，必须支持 ++ 和 -- 的操作。
因为，它的目的就是移动迭代器进行反向遍历。
流迭代器，由于无法反向遍历流，因此流迭代器不能创建反向迭代器。
string line("zhangsan,lisi,wanggang");
string::iterator comma = find(line.begin(), line.end(), ',');
cout << string(line.begin(), comma) << endl;
// find 的第三个参数，注意：单引号，而非双引号
string::reverse_iterator rcomma = find(line.rbegin(), line.rend(), ',');
// line.end() 指向超出末端元素
// line.rbegin() 指向最后一个元素
// 同理：comma 指向的元素， 和 rcomma指向的元素是不同的
// gnaggnaw
cout << string(line.rbegin(), rcomma) << endl;
// wanggang
cout << string(rcomma.base(), line.end()) << endl;
const 迭代器
不希望使用该迭代器来修改容器中的元素，则可以使用 const 迭代器
五种迭代器
输入迭代器：读，不能写；只支持自增运算
输出迭代器：写，不能读；只支持自增运算
前向迭代器：读、写；只支持自增运算
双向迭代器：读、写；支持自增、自减运算
随机访问迭代器：读、写；支持完整的迭代器算术运算
1、输入迭代器，可用于读取容器中的元素，但是，不保证能支持容器的写入操作。（如：istream_iterator）
2、输出迭代器，可用于向容器写入元素，但是，不保证能支持读取容器内容。（如：ostream_iterator）
对于指定的迭代器值，只能使用一次解引用操作
3、前向迭代器，只会以一个方向遍历序列，支持对同一个元素的多次读写。（replace 算法，需要前向迭代器）
4、双向迭代器，提供前向迭代器的所有操作，另外，还提供前置、后置的自减运算（--）。
标准库容器提供的迭代器，至少达到双向迭代器的要求。（reverse 算法，需要双向迭代器）
5、随机访问迭代器。vector、deque、 string 等，它们的迭代器是随机访问迭代器，
内置数组的指针也是随机访问迭代器
map、set、list 类型提供的是双向迭代器，
string、vector、deque 容器，提供的是随机访问迭代器
内置数组的指针，也是随机访问迭代器
istream_iterator 是，输入迭代器
ostream_iterator 是，输出迭代器
事实上， 虽然 map 、set 提供的是双向迭代器，但却只能使用算法的子集。
因为，关联容器的键是 const 对象，无法使用任何写序列元素的算法。
算法最基本的性质，是需要使用的迭代器类型。
算法的形参模式
多数算法，都采用以下4 种形式中的一种：
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 指定算法操作的元素范围（输入范围）；
dest、beg2、end2， 都是迭代器
带有单个目标迭代器的算法
dest 形参是一个迭代器，用于指定，存储输出数据的目标对象。
为保证写入安全，通常使用插入迭代器 或 ostream_iterator 来调用算法，
否则，算法将假定容器内有足够多个需要的元素
带第二个输入序列的算法
有些算法，带有一个beg2，或者带有beg2 和 end2，用于指定第二个输入范围。
算法的命名规范
标准库使用一组相同的命名和重载规范
它们包括2 种模式：
1、检测输入范围内元素的算法
2、应用于对输入范围内元素重新排序的算法
重新排序的算法，要使用 < 操作符。此类算法的第二个重载版本带有额外形参，表示用于排序的不同运算
sort (beg, end);
sort (beg, end, comp);
检查指定值的算法，默认使用 == 操作符。此类算法，会提供另外命名的版本，而不是重载版本。
因为，这两种版本的算法，带有相同数目的形参。如果使用重载，容易混淆。
find ( beg, end, val);
find_if (beg, end, pred);
区别是否实现复制的算法版本
算法的执行，很可能会重新排列输入范围内的元素，
而排列之后的元素会被写回输入范围。
标准库提供了另外命名的版本，将元素写到指定的输出目标。
reverse( beg, end);
reverse_copy (beg, end, dest);
list 容器上的迭代器是双向的，而不是随机访问类型。
因此，一些泛型算法，用在 list 容器上，会付出更多的性能上的代价。
于是，标准库为 list 容器定义了更精细的操作集合，使其不必只依赖于泛型操作。
list 容器特有的操作
lst.merge (lst2)
lst.merge (lst2, comp)
将 lst2 的元素合并到 lst 中。这两个 list 容器对象都必须排序。
lst2 中的元素将被删除。合并后，lst2 为空。返回 void
第一个版本，使用 < 操作符
第二个版本，使用 comp 指定的比较运算
lst.remove (val)
lst.remove_if (unaryPred)
调用 lst.erase 删除所有等于指定值 或 使指定的谓词函数返回非零值的元素。返回void
lst.reverse ()
反向排列 lst 中的元素
lst.sort ()
对 lst 中的元素排序
lst.splice (iter, lst2)
lst.splice (iter, lst2, iter2)
lst.splice (iter, beg, end)
将 lst2 的元素移动到 lst 中迭代器 iter 所指向的元素前面。在 lst2 中删除移出的元素。
第一个版本将 lst2 的所有元素移动到 lst 中，合并后， lst2 为空。
lst1 和 lst2 不能是同一个对象
第二个版本只移动 iter2 所指向的元素，这个元素必须是 lst2 中的元素。
lst1 和 lst2 可以是同一个对象。即：可以在 list 对象中使用 splice 运算移动一个元素
第三个版本，移动迭代器 beg 和 end 标记的范围内的元素。该范围必须有效。
beg 和 end 可以标记任意的 list 对象内的范围，包括 lst 自身。
但是，如果，iter 指向的元素，在标记范围之中，则，运算未定义
lst.unique ()
lst.unique (binaryPred)
调用 erase 删除同一个值的连续副本。
第一个版本使用 == 操作符，判断元素是否相等。
第二个版本使用指定的谓词函数实现判断
对于 list 对象，应该优先使用 list 容器特有的成员版本，而不是泛型算法。
list 容器特有的算法，与泛型算法之间，有两个至关重要的差别。
1、 remove 和 unique 的 list 版本，修改了其关联的基础容器，即：真正删除了指定的元素。
2、 merge 和 splice 的 list 版本，会破坏它们的实参。
使用 merge 的泛型算法时，合并的序列将写入目标迭代器指向的对象，
而它的两个输入序列保持不变。
而，list 容器的 merge 成员函数，会破坏它的实参 list 对象：
实参对象的元素合并到调用 merge 函数的 list 对象时，实参对象的元素将被移出并删除。