015 泛型算法

迭代器参数

一些算法从两个序列中读取元素。构成这两个序列的元素可以来自于不同类型的容器。例如，第一个序列可能保存于一个 vector 中，而第二个序列可能保存于一个 list、deque、内置数组或其他容中。而且，两个序列中元素的类型也不要求严格匹配。算法要求的只是能够比较两个序列中的元素。例如，对 equal 算法，元素类型不要求相同，但是我们必须能使用 == 来比较来自两个序列中的元素。

操作两个序列的算法之间的区别在于我们如何传递第二个序列。一些算法，例如 equal，接受三个迭代器：前两个表示第一个序列的范围，第三个表示第二个序列中的首元素。其他算法接受四个迭代器：前两个表示第一个序列的元素范围，后两个表示第二个序列的范围。

用一个单一迭代器表示第二个序列的算法都假定第二个序列至少与第一个一样长。确保算法不会试图访问第二个序列中不存在的元素是程序员的责任。例如，算法 equal 会将其第一个序列中的每个元素与第二个序列中的对应元素近行比较。如果第二个序列是第一个序列的一个子集，则程序会产生一个严重错误 —— equal 会试图访问第二个序列中末尾之后(不存在)的元素。

算法不检查写操作

一些算法接受一个迭代器来指出一个单独的目的位置。这些算法将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。例如，函数 fill_n 接受一个单迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定个元素。我们可以用 fill_n 将一个新值赋予 vector 中的元素:

vector<int>  vec; //  空 vector
// 使用 vec，赋予它不同值
fill_n(vec.begin(), vec.size(), 0); // 将所有元素重置为 0

函数fill_n假定写入指定个元素是安全的。即,如下形式的调用

fill_n(dest, n, val);

fill_n 假定 dest 指向一个元素，而从 dest 开始的序列至少包含 n 个元素。

一个初学者非常容易犯的错误是在一个空容器上调用 fill_n (或类似的写元素的算法)：

vector<int> vec; // 空 vector
// 灾难：修改 vec 中的 10 个（不存在）元素
fill_n(vec.begin(), 10, 0); 

这个调用是一场灾难。我们指定了要写入 10 个元素，但 vec 中并没有元素 —— 它是空的。这条语句的结果使未定义的。

注意：向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。

介绍 back_inserter

一种保证算法有足够元素空间来容纳输出数据的方法是使用 插入迭代器( Insert Iterator)。插入迭代器是一种向容器中添加元素的迭代器。通常情况，当我们通过一个迭代器向容器元素赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。

我们将使用 back_inserter，它是定义在头文件 iterator 中的一个函数。

back_inserter 接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器当我们通过此迭代器赋值时，赋值运算符会调用 push_back 将一个具有给定值的元素添加到容器中:

vector<int> vec; // 空向量
auto it =  back_inserter(vec); // 通过它赋值会将元素添加到 vec 中
*it = 42; // vec 中现在有一个元素,值为 42

我们常常使用 back_inserter 来创建一个迭代器，作为算法的目的位置来使用。例如：

vector<int>  vec; // 空向量
// 正确: back_inserter 创建一个插入迭代器,可用来向 vec 添加元素
fill_n(back_inserter(vec), 10, 0); // 添加 10 个元素到 vec

在每步迭代中，fill_n 向给定序列的一个元素赋值。由于我们传递的参数是 back_inserter 返回的迭代器，因此每次赋值都会在 vec 上调用 push_back。最终，这条 fill_n 调用语句向 vec 的末尾添加了 10 个元素，每个元素的值都是 0。

拷贝算法

copy：

int a1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int a2[sizeof(a1)/sizeof(*a1)]; // 设置与 a1 一样的大小
// result 指向拷贝到 a2 的尾元素之后的位置
auto result = copy(begin(a1), end(a1), a2); // 把 a1 的内容拷贝给 a2

copy 返回的是其目的位置迭代器(递增后)的值。即，result 恰好指向拷贝到 a2 的尾元素之后的位置。

多个算法都提供所谓的“拷贝”版本。这些算法计算新元素的值，但不会将它们放置在输入序列的末尾，而是创建一个新序列保存这些结果。

例如，replace 算法读入一个序列，并将其中所有等于给定值的元素都改为另一个值。此算法接受 4 个参数：前两个是迭代器，表示输入序列，后两个一个是要搜索的值，另一个是新值。它将所有等于第一个值的元素替换为第二个值：

// 将所有值为0的元素改为42
replace(ilst.begin(),  ilst.end(), 0,  42);

此调用将序列中所有的 0 都替换为 42。如果我们希望保留原序列不变，可以调用 replace_copy。此算法接受额外第三个迭代器参数，指出调整后序列的保存位置：

// 使用 back_inserter 按需要增长目标序列
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec),  0,  42);

此调用后，ilst 并未改变，ivec 包含 ilst 的一份拷贝，不过原来在 ilst 中值为 0 的元素在 ivec 中都变为 42。

重排容器元素的算法

某些算法会重排容器中元素的顺序，一个明显的例子是 sort。调用 sort 会重排输入序列中的元素，使之有序，它是利用元素类型的 < 运算符来实现排序的。
例如，假定我们想分析一系列儿童故事中所用的词汇。假定已有一个 vector，保存了多个故事的文本。我们希望化简这个 vector，使得每个单词只出现一次，而不管单词在任意给定文档中到底出现了多少次。
为了便于说明问题,我们将使用下面简单的故事作为输入：

the quick red fox jumps over the slow red turtle

给定此输入，我们的程序应该生成如下 vector：

0	1	2	3	4	5	6	7
fox	jumps	over	quick	red	slow	the	turtle

为了消除重复单词，首先将 vector 排序，使得重复的单词都相邻出现。一旦 vector 排序完毕，我们就可以使用另一个称为 unique 的标准库算法来重排 vector，使得不重复的元素出现在 vector 的开始部分。由于算法不能执行容器的操作，我们将使用 vector 的 erase 成员来完成真正的删除操作：

void elimDups(vector<string> &words) {
  // 按照字典排序 words，以便查找重复的单词
  sort(word.begin(), words.end());
  // unique 重排输入范围，使得每个单词只出现一次
  // 排列在范围的前部，返回指向不重复区域之后一个位置的迭代器
  auto end_unique = unique(words.begin(), words.end());
  // 使用向量操作 erase 删除重复单词
  words.erase(end_unique, words.end());
}

sort 算法接受两个迭代器，表示要排序的元素范围。在上面的例子中，我们排序整个 vector。完成 sort 后，words 的顺序如下所示：

0	1	2	3	4	5	6	7	8	9
fox	jumps	over	quick	red	red	slow	the	the	turtle

单词 red 和 the 各出现了两次。

words 排序完成之后，我们希望将每个单词都只保存一次。unique 算法重排输入序列，将相邻的重复项“消除”，并返回一个指向不重复值范围末尾的迭代器。调用 unique 之后，vector 将变成：

0	1	2	3	4	5	6	7	8	9
fox	jumps	over	quick	red	slow	the	turtle	???	???

words 的大小并未改变，它仍有 10 个元素。但这些元素的顺序被改变了 —— 相邻的重复元素被“删除”了。我们将删除打引号是因为 unique 并不真的删除任何元素，它只是覆盖相邻的重复元素，使得不重复元素出现在序列开始部分。unique 返回的迭代器指向最后一个不重复元素之后的位置。此位置之后的元素仍然存在，但我们不知道它们的值是什么。

注意：标准库算法对迭代器而不是容器进行操作。因此，算法不能（直接）添加或删除元素。

值得注意的是，即使 words 中没有重复单词，这样调用 erase 也是安全的。在此情况下，unique 会返回 words.end()。因此，传递给 erase 的两个参数具有相同的值： words.end()。迭代器相等意味着传递给 erase 的元素范围为空。删除一个空范围没有什么不良后果，因此程序即使在输入中无重复元素的情况下也是正确的。

向算法传递函数

很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的 < 或 == 运算符完成比较。标准库还为这些算法定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符。

例如，sort 算法默认使用元素类型的 < 运算符。但可能我们希望的排序顺序与 < 所定义的顺序不同，或是我们的序列可能保存的是未定义 < 运算符的元素类型。在这两种情况下，都需要重载 sort 的默认行为。

作为一个例子，假定希望在调用 elimDups 后打印 vector 的内容。此外还假定希望单词按其长度排序，大小相同的再按字典序排列。为了按长度重排 vector，我们将使用 sort 的第二个版本，此版本是重载过的，它接受第三个参数，此参数是一个 谓词（predicate）。

谓词 是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：一元谓词（unary predicate,意味着它们只接受单一参数）和二元谓词（binary predicate,意味着它们有两个参数）。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。

接受一个二元谓词参数的 sort 版本用这个谓词代替 < 来比较元素。当前，我们需知道，此操作必须在输入序列中所有可能的元素值上定义一个一致的序。isShorter 就是一个满足这些要求的函数，因此可以将 isShorter 传递给 sort。这样做会将元素按大小重新排序：

// 比较函数，用来按长度排序单词
bool isShorter(const string &s1, const string &s2) {
  return s1.size() < s2.size();
}

// 按长度由短到长排序 words
sort(words.begin(), words.end(), isShorter);

在我们将 words 按大小重排的同时，还希望具有相同长度的元素按字典序排列。为了保持相同长度的单词按字典序排列，可以使用 stable_sort 算法。这种稳定排序算法维持相等元素的原有顺序。

通常情况下，我们不关心有序序列中相等元素的相对顺序，它们毕竞是相等的。但是，在本例中，我们定义的“相等”关系表示“具有相同长度”。而具有相同长度的元素，如果看其内容，其实还是各不相同的。通过调用 stable_sort，可以保持等长元素间的字典顺序：

// 将 words 按字典顺序排序，并消除重复的单词
elimDups(words);
// 按长度重新排序，长度相同的单词维持字典顺序
stable_sort(words.begin(), words.end(), isShorter);
for (const auto &s : words) {
  cout << s << " ";
}
cout << endl;

假定在此调用前 words 是按照字典顺序排序的，则调用之后，words 会按照元素大小排序，而长度相同的单词会保持字典顺序。输出结果为：

fox red the over slow jumps quick turtle

调用 find_if

使用 lambda，我们就可以查找第一个长度大于等于 sz 的元素：

auto wc = find_if(words.begin(), words.end(), 
                  [sz](const string &a){ return a.size() >= sz; });

这里对 find_if 的调用返回一个迭代器，指向第一个长度不小于给定参数 sz 的元素。如果这样的元素不存在，则返回 words.end() 的一个拷贝。
我们可以使用 find_if 返回的迭代器来计算从它开始到 words 的末尾一共有多少个元素：

// 计算满足 size>=sz 的元素的数目
auto  count = words.end() -  wc;
cout  <<  count  <<  make_plural(count, "word", "s")
      << " of  length " << sz << " or  longer" << endl;

我们的输出语句调用 make_plural 来输出“word”或“words”，具体输出哪个取决于 count 是否等 1。

for_each 算法

问题的最后一部分是打印 words 中长度大于等于 sz 的元素。为了达到这一目的,我们可以使用 for_each 算法。此算法接受一个可调用对象，并对输入序列中每个元素调用此对象：

// 打印长度大于等于给定值的单词,每个单词后面接一个空格
for_each(wc,  words.end(),
          [](const  string  &s)(cout << s << " ";});
cout << endl;

此 lambda 中的捕获列表为空，但其函数体中还是使用了两个名字：s 和 cout，前者是它自己的参数。

捕获列表为空，是因为我们只对 lambda 所在函数中定义的（非 static）变量使用捕获列表。一个 lambda 可以直接使用定义在当前函数之外的名字。在本例中，cout 不是定义在 biggies 中的局部名字，而是定义在头文件 iostream 中。因此，只要在 biggies 出现的作用域中包含了头文件 iostream，我们的 lambda 就可以使用 cout。

注意：捕获列表只用于局部非 static 变量，lambda 可以直接使用局部 static 变量和它所在函数之外声明的名字。

完整的 biggies 程序：

void biggies(vector<string>  &words, vector<string>::size_type sz) {
// 将 words 按字典序排序，删除重复单词
elimDups(words);
// 按长度排序，长度相同的单词维持字典序
stable_sort(words.begin(), words.end(),
      [](const string &a, const string &b){ return a.size() < b.size();});
// 获取一个选代器，指向第一个满足 size() >= sz 的元素
auto wc = find_if(words.begin(), words.end(),
                  [sz](const  string  &a){ return a.size() >=  sz; });
// 计算满足 size>=sz 的元素的数目
auto count = words.end() - wc;
cout << count  << " " << make_plural(count, "word", "s")
      << " of  length " <<  sz << " or  longer" << endl;
// 打印长度大于等于给定值的单词，每个单词后面接一个空格
for_each(wc, words.end(),
        [](const  string  &s){cout << s << " ";});
cout << endl；

插入迭代器

插入器是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定的容器插入元素。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定位置插入一个元素。

插入迭代器操作	说明
it = t	在 it 指定的当前位置插入值 t。假定 c 是 it 绑定的容器，依赖于插入迭代器的不同种类，此赋值会分别调用 c.push_back(t)、c.push_front(t) 或 c.insert(t,p)，其中 p 为传递给 inserter 的迭代器位置
*it,++it,it++	这些操作虽然存在，但不会对 it 做任何事情。每个操作都返回 it

插入器有三种类型，差异在于元素插入的位置：

• back_inserter 创建一个使用 push_back 的迭代器。
• front_inserter 创建一个使用 push_front 的迭代器。
• inserter 创建一个使用 insert 的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

注意：只有在容器支持 push_front 的情况下，我们才可以使用 front_inserter。类似的，只有在容器支持 push_back 的情况下，我们才可以使用 back_inserter。

理解插入器的工作过程是很重要的：当调用 inserter(c, iter) 时，我们得到一个迭代器，接下来使用它时，会将元素插入到 iter 原来所指向的元素之前的位置。即，如果 it 是由 inserter 生成的迭代器，则下面这样的赋值语句：

*it = val;

其效果与下面代码一样：

it = c.insert(it, val); // it 指向新加入的元素
++it; // 递增 it 使它指向原来的元素

front_inserter 生成的迭代器的行为与 inserter 生成的迭代器完全不一样。当我们使用 front_inserter 时，元素总是插入到容器第一个元素之前。即使我们传递给 inserter 的位置原来指向第一个元素，只要我们在此元素之前插入一个新元素，此元素就不再是容器的首元素了：

list<int> lst = {1, 2, 3, 4};
list<int> lst2, lst3; // 空 list
// 拷贝完成之后，lst2 包含 4，3，2，1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
// 拷贝完成之后，lst3 包含 4，3，2，1
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

当调用 front_inserter(c) 时，我们得到一个插入迭代器，接下来会调用 push_front。当每个元素被插入容器 c 时，它变为 c 的新的首元素。因此，front_inserter 生成的迭代器会将插入的元素序列的顺序颠倒过来，而 inserter 和 back_inserter 则不会。

iostream 迭代器

虽然 iostream 类型不是容器，但标准库定义了可以用于这些 IO 类型对象的迭代器。istream_terator 读取输入流，ostream_iterator 向一个输出流写数据。这些迭代器将它们对应的流当作一个特定类型的元素序列来处理。通过使用流迭代器，我们可以用泛型算法从流对象读取数据以及向其写入数据。

istream_iterator 操作

当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。一个 istream_iterator 使用 >> 来读取流。因此，istream_iterator 要读取的类型必须定义了输入运算符。当创建一个 istream_iterator 时，我们可以将它绑定到一个流。当然，我们还可以默认初始化选代器，这样就创建了一个可以当作尾后值使用的选代器。

istream_iterator<int> int_it(cin); // 从 cin 读取 int
istream_iterator<int> int_eof; // 尾后选代器
ifstream in("afile");
istream_iterator<string> str_it(in); // 从 ”afile” 读取字符串

下面是一个用 istream_iterator 从标准输入读取数据，存入一个 vector 的例子：

istream_iterator<int> in_iter(cin); // 从 cin 读取 int
istream_iterator<int> eof; // istream 尾后选代器
while (in_iter != eof) { // 当有数据可供读取时
    // 后置递增运算读取流，返回迭代器的旧值
    // 解引用迭代器，获得从流读取的前一个值
    vec.push_back(*in_iter++);
}

此循环从 cin 读取 int 值，保存在 vec 中。在每个循环步中，循环体代码检查 in_iter 是否等于 eof。eof 被定义为空的 istream_iterator，从而可以当作尾后选代器来使用。对于一个绑定到流的选代器,一旦其关联的流遇到文件尾或遇到 IO 错误，迭代器的值就与尾后迭代器相等。

此程序最困难的部分是传递给 push_back 的参数，其中用到了解引用运算符和后置递增运算符。该表达式的计算过程与我们之前写过的其他结合解引用和后置递增运算的表达式一样。后置递增运算会从流中读取下一个值，向前推进，但返回的是迭代器的旧值。选代器的旧值包含了从流中读取的前一个值，对迭代器进行解引用就能获得此值。

我们可以将程序重写为如下形式，这体现了 istream_iterator 更有用的地方：

istream_iterator<int> in_iter(cin), eof; // 从 cin 读取 int
vector<int> vec(in_iter, eof); // 从迭代器范围构造 vec

本例中我们用一对表示元素范围的迭代器来构造 vec。这两个迭代器是 istream_iterator，这意味着元素范围是通过从关联的流中读取数据获得的。这个构造函数从 cin 中读取数据，直至遇到文件尾或者遇到一个不是 int 的数据为止。从流中读取的数据被用来构造 vec。

istream_iterator 操作	说明
istream_iterator<T> in(is);	in 从输入流 is 读取类型为 T 的值
istream_iterator<T> end;	读取类型为 T 的值的 istream_iterator 迭代器，表示尾后位置
in1 == in2	in1 和 in2 必须读取相同类型。如果它们都是尾后迭代器，或绑定到相同的输入，则两者相等
in1 != in2	同上
*in	返回从流着读取的值
in->mem	与 (*in).mem 的含义相同
++in, in++	使用元素类型所定义的 >> 运算符从输入流中读取下一个值。与以往一样，前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值

使用算法操作流迭代器

由于算法使用迭代器操作来处理数据，而流迭代器又至少支持某些选代器操作，因此我们至少可以用某些算法来操作流选代器。下面是一个例子，我们可以用一对 istream_iterator 来调用 accumulate：

istream_iterator<int> in(cin), eof；
cout << accumulate(in, eof, 0) << endl;

此调用会计算出从标准输入读取的值的和。如果输入为:

23 109 45 89 6 34 12 90 34 23 56 23 8 89 23

则输出为 664。

istream_iterator 允许使用懒惰求值

当我们将一个 istream_iterator 绑定到一个流时，标准库并不保证迭代器立即从流读取数据。具体实现可以推迟从流中读取数据，直到我们使用迭代器时才真正读取。标准库中的实现所保证的是，在我们第一次解引用迭代器之前，从流中读取数据的操作已经完成了。对于大多数程序来说，立即读取还是推迟读取没什么差别。但是，如果我们创建了一个 istream_iterator，没有使用就销毁了，或者我们正在从两个不同的对象同步读取同一个流，那么何时读取可能就很重要了。

ostream_iterator操作

我们可以对任何具有输出运算符（<<运算符）的类型定义 ostream_iterator。当创建一个 ostream_iterator 时，我们可以提供(可选的)第二参数，它是一个字符串，在输出每个元素后都会打印此字符串。此字符串必须是一个 C 风格字符串（即，一个字符串字面常量或者一个指向以空字符结尾的字符数组的指针）必须将 ostream_iterator 绑定到一个指定的流，不允许空的或表示尾后位置的 ostream_iterator。

ostream_iterator 操作	说明
ostream_iterator<T> out(os);	out 将类型为 T 的值写到输出流 os 中
ostream_iterator<T> out(os, d);	out 将类型为 T 的值写到输出流 os 中，每个值后面都输出一个 d。d 指向一个空字符结尾的字符数组
out = val	用 << 运算符将 val 写入到 out 所绑定的 ostream 中。val 的类型必须与 out 可写的类型兼容
*out, ++out, out++	这些运算符是存在的，但不对 out 做任何事情。每个运算符都返回 out

我们可以用 ostream_iterator 来输出值的序列：

ostream_iterator<int> out_iter(cout," ");
for (auto e : vec) {
    *out_iter++ = e; // 赋值语句实际上将元素写到 cout
}
cout << endl;

此程序将 vec 中的每个元素写到 cout，每个元素后加一个空格。每次向 out_iter 赋值时，写操作就会被提交。

值得注意的是，当我们向 out_iter 赋值时，可以忽略解引用和递增运算。即，循环可以重写成下面的样子：

for (auto e : vec) {
    out_iter = e; // 赋值语句将元素写到 cout
}

运算符 * 和 ++ 实际上对 ostream_iterator 对象不做任何事情，因此忽略它们对我们的程序没有任何影响。但是，推荐第一种形式。在这种写法中，流迭代器的使用与其他迭代器的使用保持一致。如果想将此循环改为操作其他迭代器类型，修改起来非常容易。而且，对于读者来说，此循环的行为也更为清晰。

可以通过调用 copy 来打印vec中的元素，这比编写循环更为简单：

copy(vec.begin(), vec.end(), out_iter);
cout << endl;

使用流迭代器处理类类型

我们可以为任何定义了输入运算符（>>）的类型创建 istream_iterator 对象。类似的，只要类型有输出运算符（<<），我们就可以为其定义 ostream_iterator：

istream_iterator<Sales_item> item_iter(cin), eof;
ostream_iterator<Sales_item> out_iter(cout, "\n");
// 将第一笔交易记录存在 sum 中，并读取下一条记录
Sales_item sum = *item_iter++;

while (item_iter != eof) {
    // 如果当前交易记录（存在 item_iter 中）有着相同的 ISBN 号
    if (item_iter->isbn() == sum.isbn()) {
        sum += *item_iter++; // 将其加到 sum 上并读取下一条记录
    } else {
        out_iter = sum; // 输出 sum 当前值
        sum = *item_iter++; // 读取下一条记录
    }
}
out_iter = sum; // 记得打印最后一组记录的和

此程序使用 item_iter 从 cin 读取 Sales_item 交易记录，并将和写入 cout，每个结果后面都跟一个换行符。定义了自己的选代器后，我们就可以用 item_iter 读取第一条交易记录，用它的值来初始化 sum：

// 将第一条交易记录保存在 sum 中，并读取下一条记录
Sales_item sum = *item_iter++;

此处，我们对 item_iter 执行后置递增操作，对结果进行解引用操作。这个表达式读取下一条交易记录，并用之前保存在 item_iter 中的值来初始化 sum。

while 循环会反复执行，直至在 cin 上遇到文件尾为止。在 while 循环体中，我们检查 sum 与刚刚读入的记录是否对应同一本书。如果两者的 ISBN 不同，我们将 sum 赋予 out_iter，这将会打印 sum 的当前值，并接着打印一个换行符。在打印了前一本书的交易金额之和后，我们将最近读入的交易记录的副本赋予 sum，并递增迭代器，这将读取下一条交易记录。循环会这样持续下去，直至遇到错误或文件尾。在退出之前，记住要打印输入中最后一本书的交易金额之和。

范型算法结构

任何算法的最基本的特性是它要求其迭代器提供哪些操作。某些算法，如find，只要求通过迭代器访问元素、递增迭代器以及比较两个迭代器是否相等这些能力。其他一些算法，如sort，还要求读、写和随机访问元素的能力。算法所要求的迭代器操作可以分为 5 个迭代器类别（Iterator category），如下表所示。每个算法都会对它的每个选代器参数指明须提供哪类迭代

迭代器类别	须提供哪类迭代
输入迭代器	只读，不写：单遍扫描，只能递增
输出迭代器	只写，不读：单遍扫描，只能递增
前向迭代器	可读写：多遍扫描，只能递增
双向迭代器	可读写：多遍扫描，可递增递减
随机访问迭代器	可读写：多遍扫描，支持全部迭代器运算

第二种算法分类的方式是按照是否读、写或是重排序列中的元素来分类。

5 类迭代器

类似容器，迭代器也定义了一组公共操作。一些操作所有选代器都支持，另外一些只有特定类别的迭代器才支持。例如，ostream_iterator 只支持递增、解引用和赋值。vector、string 和 deque 的迭代器除了这些操作外，还支持递减、关系和算术运算。

迭代器是按它们所提供的操作来分类的，而这种分类形成了一种层次。除了输出迭代器之外，一个高层类别的迭代器支持低层类别选代器的所有操作。

C++ 标准指明了泛型和数值算法的每个迭代器参数的最小类别。例如，find 算法在一个序列上进行一遍扫描，对元素进行只读操作，因此至少需要输入迭代器。replace 函数需要一对迭代器，至少是前向迭代器。类似的,replace_copy 的前两个迭代器参数也要求至少是前向迭代器。其第三个迭代器表示目的位置，必须至少是输出迭代器。其他的例子类似。对每个迭代器参数来说，其能力必须与规定的最小类别至少相当。向算法传递一个能力更差的选代器会产生错误。

输入迭代器（input iterator）：可以读取序列中的元素。

一个输入选代器必须支持：

• 用于比较两个迭代器的相等和不相等运算符（==、!=）
• 用于推进迭代器的前置和后置递增运算（++）
• 用于读取元素的解引用运算符（*）：解引用只会出现在赋值运算符的右侧
• 箭头运算符（->），等价于(*it).member，即，解引用选代器，并提取对象的成员

输入选代器只用于顺序访问。对于一个输入迭代器，*it++ 保证是有效的，但递增它可能导致所有其他指向流的迭代器失效。其结果就是，不能保证输入迭代器的状态可以保存下来并用来访问元素。因此，输入迭代器只能用于单遍扫描算法。算法 find 和 accumulate 要求输入选代器：而 istream_iterator 是一种输入选代器。

输出迭代器（output iterator）：可以看作输入迭代器功能上的补集 —— 只写而不读元素。

输出迭代器必须支持：

• 用于推进迭代器的前置和后置递增运算（++）
• 解引用运算符（*），只出现在赋值运算符的左侧（向一个已经解引用的输出迭代器赋值，就是将值写入它所指向的元素）

我们只能向一个输出迭代器赋值一次。类似输入迭代器，输出迭代器只能用于单遍扫描算法。用作目的位置的迭代器通常都是输出选代器。例如，copy 函数的第三个参数就是输出迭代器。ostream_iterator 类型也是输出迭代器。

前向迭代器（forward iterator）：可以读写元素。

这类迭代器只能在序列中沿一个方向移动。前向选代器支持所有输入和输出选代器的操作，而且可以多次读写同一个元素。因此，我们可以保存前向迭代器的状态，使用前向迭代器的算法可以对序列进行多遍扫描。算法 replace 要求前向迭代器，forward_list 上的迭代器是前向迭代器。

双向迭代器（bidirectional iterator）：可以正向/反向读写序列中的元素。

除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减运算符（--）。算法 reverse 要求双向迭代器，除了 forward_list 之外，其他标准库都提供符合双向迭代器要求的迭代器。

随机访问迭代器（random-access iterator）：提供在常量时间内访问序列中任意元素的能力。

此类迭代器支持双向迭代器的所有功能：

• 用于比较两个迭代器相对位置的关系运算符（<、<=、> 和 >=）
• 迭代器和一个整数值的加减运算（+、+=、- 和 -=），计算结果是迭代器在序列中前进（或后退）给定整数个元素后的位置
• 用于两个迭代器上的减法运算符（-），得到两个迭代器的距离
• 下标运算符（iter[n]），与*(iter[n])等价

算法 sort 要求随机访问迭代器。array、deque、string 和 vector 的迭代器都是随机访问迭代器，用于访问内置数组元素的指针也是。

算法形参模式

在任何其他算法分类之上，还有一组参数规范。理解这些参数规范对学习新算法很有帮助 —— 通过理解参数的含义，你可以将注意力集中在算法所做的操作上。大多数算法具有如下4种形式之一：

alg(beg, end, other_args);
alg(beg, end, dest, other_args);
alg(beg, end, beg2, other_args);
alg(beg, end, beg2, end2, other_args);

其中 alg 是算法的名字，beg 和 end 表示算法所操作的输入范围。几乎所有算法都接受一个输入范围，是否有其他参数依赖于要执行的操作。这里列出了常见的一种 —— dest、beg2 和 end2，都是选代器参数。顾名思义，如果用到了这些选代器参数，它们分别承担指定目的位置和第二个范围的角色。除了这些选代器参数,一些算法还接受额外的、非迭代器的特定参数。

接受单个目标迭代器的算法

dest 参数是一个表示算法可以写入的目的位置的选代器。算法假定（assume）：按其需要写入数据，不管写入多少个元素都是安全的。

注意：向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据

如果 dest 是一个直接指向容器的迭代器，那么算法将输出数据写到容器中已存在的元素内。更常见的情况是，dest 被绑定到一个插入迭代器或是一个 ostream_iterator。插入迭代器会将新元素添加到容器中，因而保证空间是足够的。ostream_iterator 会将数据写入到一个输出流，同样不管要写入多少个元素都没有问题。

接受第二个输入序列的算法

接受单独的 beg2 或是接受 beg2 和 end2 的算法用这些迭代器表示第二个输入范围。这些算法通常使用第二个范围中的元素与第一个输入范围结合来进行一些运算。

如果一个算法接受 beg2 和 end2，这两个迭代器表示第二个范围。这类算法接受两个完整指定的范围：[beg, end)表示的范围和 [beg2,end2) 表示的第二个范围。

只接受单独的 beg2（不接受end2）的算法将 beg2 作为第二个输入范围中的首元素。此范围的结束位置未指定，这些算法假定从 beg2 开始的范围与 beg 和 end 所表示的范围至少一样大。

算法命名规范

除了参数规范，算法还遵循一套命名和重载规范。这些规范处理诸如：如何提供一个操作代替默认的 < 或 == 运算符以及算法是将输出数据写入输入序列还是一个分离的目的位置等问题。

一些算法使用重载形式传递一个谓词

接受谓词参数来代替 < 或 == 运算符的算法，以及那些不接受额外参数的算法，通常都是重载的函数。函数的一个版本用元素类型的运算符来比较元素：另一个版本接受一个额外谓词参数，来代替 < 或 ==。

unique(beg, end); // 使用=运算符比较元素
unique(beg, end, comp); // 使用 comp 比较元素

两个调用都重新整理给定序列，将相邻的重复元素删除。第一个调用使用元素类型的 == 运算符来检查重复元素：第二个则调用 comp 来确定两个元素是否相等。由于两个版本的函数在参数个数上不相等，因此具体应该调用哪个版本不会产生歧义。

_if 版本的算法

接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的 _if：

find(beg, end, val); // 查找输入范围中 val 第一次出现的位置
find_if(beg, end, pred); // 查找第一个令 pred 为真的元素

这两个算法都在输入范围中查找特定元素第一次出现的位置，算法 find 查找一个指定值
；算法 find_if 查找使得 pred 返回非零值的元素。

这两个算法提供了命名上差异的版本，而非重载版本，因为两个版本的算法都接受相同数目的参数。因此可能产生重载歧义，虽然很罕见，但为了避免任何可能的歧义，标准库选择提供不同名字的版本而不是重载。

区分拷贝元素的版本和不拷贝的版本

默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。如我们所见，写到额外目的空间的算法都在名字后面附加一个 copy：

reverse(beg, end); // 反转输入范国中元素的顺序
reverse_copy(beg, end, dest); // 将元素按逆序拷贝到 dest

一些算法同时提供 copy 和 if 版本。这些版本接受一个目的位置迭器和一个谓词：

// 从 v1 中删除奇数元素
remove_if(v1.begin(), v1.end(), [](int i){ return i % 2; });
// 将偶数元素从 v1 拷贝到 v2；v1 不变
remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), [](int i){ return i % 2; });

两个算法都调用了 lambda 来确定元素是否为奇数。在第一个调用中，我们从输入序列中将奇数元素删除。在第二个调用中，我们将非奇数（亦即偶数）元素从输入范围拷贝到 v2 中。