第10章 泛型算法(C++ Primer 5th)

1. 概述

大多数算法都定义在头文件 algorithm 中。标准库还在头文件 numeric 中定义了一组数值泛型算法。

一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。

find 算法示例

int val = 42;	// 我们将查找的值
// 如果在vec 中找到想要的元素，则返回结果指向它，否则返回结果为vec.cend()
auto result = find(vec.cbegin(), vec.cend(), val);
// 报告结果
cout << "The value " << val
    << (result == vec.cend()
       ? " is not present" : " is present") << endl;

算法如何工作

以 find 为例：

1. 访问序列中的首元素。
2. 比较此元素于我们要查找的元素。
3. 如果此元素于我们要查找的值匹配，find 返回标识此元素的值。
4. 否则，find 前进到下一个元素，重复执行步骤 2 和 3。
5. 如果达到序列尾，find 应停止。
6. 如果 find 达到序列末尾，它应该返回一个指出元素未找到的值。此值和步骤 3 返回的值必须具有相容的类型。

这些步骤都不依赖于容器所保存的元素类型。 因此，只要有一个迭代器可用来访问元素， find 就完全不依赖于容器类型。

迭代器令算法不依赖于容器，······

在上述的 find 函数的流程中，除了第 2 步外，其他步骤都可以用迭代器操作来实现。

······，但算法依赖于元素类型的操作

虽然迭代器的使用令算法不依赖于容器类型，但大多数算法都使用了一个（或多个）元素类型上的操作。例如，在步骤 2 中，find 用元素类型的 == 运算符完成每个元素与给定值的比较。其他算法可能要求元素类型支持 < 运算符。不过，我们将看到，大多数算法提供了一种方法，允许我们使用自定义的操作来替代默认的运算符。

算法永远不会执行容器的操作

2. 初始泛型算法

标准库提供了超过100个算法，这些算法都是有一致的结构，下面以几种具体的算法为例介绍标准库中算法的结构。

2.1 只读算法

只读算法只会读取输入范围内的元素，不改变元素。find 就是这样一种算法。

以 accumulate 为例，它定义在头文件 numeric 中，这个函数的功能时求和。它接受三个参数，前两个指出了需要求和的元素的范围，第三个参数是和的初值。

// vec 是一个整数序列
// 对 vec 中的元素求和，和的初值是0
int sum = accumulate(vec.cbegin(), vec.cend(), 0);

accumulate 的第三个参数的类型决定了函数中使用哪个加法运算符以及返回的类型

算法和元素类型

accumulate 将第三个参数作为求和起点，这蕴含这一个编程假定： 将元素类型加到和的类型上的操作必须可行。 即序列中的元素的类型必须与第三个参数匹配，或者能够转换为第三个参数的类型，如果类型是自定义类型，那么自定义类型必须定义 + 运算符。

下面两个例子

// v 的类型是 vector<string>
string sum = accumulate(v.cbegin(), v.cend(), string(""));  // 正确
string sum = accumulate(v.cbegin(), v.cend(), "");  // 错误： const char* 上没有定义 + 运算符

在第二个求和的调用中，第三个参数是字符串字面值，类型是 const char* ，由于 const char* 并没有 + 运算符，此调用将产生编译错误。

对于只读取而不改变元素的算法，通常最好使用 cbegin() 和 cend() 。如果需要改变元素则使用 begin() 和 end()。

操作两个序列的算法

equal 算法，用于确定两个序列是否保存相同的值。它将第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果所有对应元素都相等，则返回 true ， 否则返回 false 。此算法接受三个迭代器：前两个表示第一个序列中的元素范围，第三个表示第二个序列的首元素（指需要比较的元素范围的起始位置）

// roster2 中的元素数目应该至少与 roster1 一样多
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

由于 equal 利用迭代器完成，因此我们可以调用 equal 来比较两个不同类型的容器中的元素。而且元素类型也不必一样，只要我们能用 == 来比较两个元素类型即可（即两个类型需要有重载的 == 支持它们之间进行比较）。

但是，equal 基于一个非常重要的假设：它假定第二个序列至少与第一个序列一样长。

那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二序列至少与第一个序列一样长。

2.2写容器元素的算法

一些算法将心智赋予序列中的元素。当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入的元素数目。因为算法不会执行容器操作，它们自身不能改变容器的大小。

算法 fill ，它的接受一对迭代器表示一个范围，还接受一个值作为第三个参数。 fill 将给定的这个值赋予输入序列中的每个元素

fill(vec.begin(), vec.end(), 0);		// 将每个元素重置 0
// 将容器的一个子序列设置为10
fill(vec.begin()， vec.end() + vec.size()/2, 10)

算法不检查写操作

一些算法接受一个迭代器来指出起始位置，使用一个计数值表示需要写入的个数。例如 fill_n 函数接受一个单迭代器、一个计数值和一个值，它的功能是从给定迭代器的位置写入 “计数值” 个数，这个数是由第三个参数给出。

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 个元素。

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

上面 fill_n 调用指定写入10 个元素，但 vec 的大小并没有 10，这条语句的结果是未定义的。

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

算法并不会检查写入元素的个数，也不会自动改变容器的大小

介绍 back_inserter

使用插入迭代器可以保证调用写入算法有足够的空间来容纳输出数据。插入迭代器是一种向容器添加元素的迭代器。通常情况，当我们通过一个迭代器向容器元素赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值话右侧值相等的元素被添加到容器。调用back_inserter 即可获取到容器的插入迭代器，它定义在头文件 iterator

vector<int> vec;   // 空 vector
// it 的类型为 std::back_insert_iterator<std::vector<int>>
auto it = back_inserter(vec);	// 通过它赋值会将元素添加到 vec 中
*it = 42;	// 42会添加到vec中

在算法中作为目的位置使用

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

当我们传递的是插入迭代器，每次赋值都会在 vec 上调用 push_back ，在容器的末尾添加元素。

拷贝算法

拷贝算法是一个向目的位置迭代器指向的输出序列的元素写入数据的算法。此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。 目的序列至少要包含与输出序列一样多的元素

使用 copy 实现内置数组的拷贝

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

copy 放回的是其目的物质迭代器（递增后）的值。即，ret 指向拷贝到 a2 的尾元素之后的位置。

有些算法提供所谓的 “拷贝” 版本，比如 replace 和 replace_copy （拷贝版本）

这两个函数都是替换序列中元素的值。replace 接受 4 个参数： 前两个是迭代器，表示输出序列，后两个一个是要被替换的值，另一个是替换后的新值。

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

replace 是在原始序列上改动，而 replace_copy 是将改动后的序列拷贝一份，原序列保持不变。此算法接受额外第三个迭代器参数，指出调整后序列的保存位置

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

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

2.3 重排容器元素的算法

排序算法，这类算法是利用元素类型的 < 运算符来实现排序的。

下面以一段文本为例，这段文本保存在 vector 中，我们希望简化这个 vector ，使得每个单词只出现一次。

the quick red fox jumps over the slow red turtle

去重排序后的 vector

fox jumps over quick red slow the turtle

消除重复单词

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

在完成 sort 后，words 的顺序如下

fox jumps over quick red red slow the the turtl

使用 unique

调用 unique 后 vector 将变为：

words 的大小并没有改变，它仍有10个元素。但这些元素的顺序被改变了——相邻的重复元素被 “移动”到了最后。unique 返回的迭代器指向最后一个不重复元素之后的位置。此位置之后的元素依然存在，但我们不知道它们的值是什么。

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

使用容器操作删除元素

为了删除无用的元素，我们必须使用容器操作。所有最后使用了 erase 删除重复的元素。

3. 定制操作

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

3.1 向算法传递函数

对于 elimDups （2.3 小节）还希望单词按其长度排序，大小相同的再按字典序排列。为了实现按长度重排 vector ，我们可以使用 sort 的第二个版本，它接受第三个参加，参数是一个 谓词。

谓词

谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。可调用表达式是指以 express(args) 这种方式调用，这里的 “可调用的表达式"可以简单的理解为就是函数指针（目前我们只知道函数和函数指针这两种可调用对象，后面章节还会介绍其他可调用对象）。

标准库算法所使用的谓词分类两类：一元谓词，只接受单一参数；二元谓词，可接受两个参数。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。

接受一个二元谓词参数的 sort 版本用这个谓词来代替 < 来比较元素。

// 比较函数，用来按长度排序单词， 作为一个二元谓词传递给 sort
bool isShorter(const string& s1, const string& s2)
{
    return s1.size() < s2.size();
}
// 按长度有短至长排序 words
sort(words.begin(), words.end(), isShorter);

排序算法

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

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

输出结果：

fox red the over slow jumps quick turtle

3.2 lambda 表达式

根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。

一个例子，我们修改 3.1 节的程序，求大于等于一个给定长度的单词有多少，并将这些单词打印出来。

void biggies(vector<string>& words, 
             vector<string>::size_type sz)
{
    elimDups(words);  // 将words按字典序重排，并消除重复单词
    // 按长度重新排序，长度相同的单词维持字典序
	stable_sort(words.begin(), words.end(), isShorter);
    // 1. 获取一个迭代器，指向第一个满足 size() >= sz 的元素
    // 2. 计算满足 size() >= sz 的元素的数目
    // 3. 打印
 }

在步骤1，我们科室使用标准库 find_if 算法来查找第一个具有特定大小的元素。find_if 算法接受一对迭代器，表示一个范围，第三个参数是一个谓词。find_if 算法对输入序列中的每个元素调用给定的这个谓词。它返回第一个使谓词返回非0值得元素，如果不存在这样得元素，则返回尾迭代器。

编写一个函数，令其接受一个 string 和一个长度，并返回一个 bool 值表示该 string 的长度是否大于给定长度。但是，find_if 接受一元谓词，不能传递一个二元谓词，为了解决此问题，需要使用 lambda表达式。

介绍 lambda

我们可以向一个算法传递任何类别的可调用对象 。对于一个对象或一个表达式，如果可以对其使用调用运算符() ，则称它为可调用对象。即，如果 e 是一个可调用表达式，则我们可以编写代码 e(args)，其中 args 是一个逗号分隔得一个或多个参数得列表。

可调用对象有：

• 函数
• 函数指针
• 重载了函数调用运算符的类
• lambda 表达式

C++11 一个 lambda 表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个 lambda 具有返回类型、参数列表和函数体。但与函数不同，lambda 可能定义在函数内部。

lambda 表达式形式

[capture list] (parameter list) -> return type { function body }

**capture list : ** 捕获列表是一个 lambda 所在函数中定义的局部变量

return type、parameter list 和 function body 与普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同，lambda 必须使用尾置返回。

示例

// 可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体
auto f = [] { return 42; };   // 定义一个可调用对象 f
cout << f() << endl;	// 调用，打印42

在 lambda 中忽略括号和参数列表等价于指定一个空参数列表。如果忽略返回类型，lambda 根据函数体中的代码推断出返回类型。如果函数体只要一个 return 语句，则返回类型从返回的表达式的类型推断而来。否则返回类型为 void。

如果 lambda d的函数体包含任何单一 return 语句之外的内容，且未指定返回类型，则返回 void

向 lambda 传递参数

与普通函数调用类似，调用一个 lambda 是给定的实参被用来初始化 lambda 的形参。通常，实参和形参的类型必须匹配。但与普通函数不同，lambda不用有默认参数。

一个带参数的lambda的例子

[] (const string &a, const string &b)
{ return a.size() < b.size(); }

使用捕获列表

示例，lambda 捕获 sz 并只有单一的 string 参数

[sz] (const string &a) 
{ return a.size() >= sz; }

一个 lambda 只有在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数提中使用该变量。

关于lambda 的捕获方式在后续的章节中有详细的描述。

调用 find_if

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

// 获取一个迭代器，指向第一个满足 size() >= sz 的元素
auto wc = find_if(words.begin(), words.end(),
	[sz] (const string &a)
		{ return a.size() >= sz; });

for_each 算法

问题的最后一部分是打印 words 中长度大于等于 sz 的元素

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

完整的biggies

下面是完整中的程序

void biggies(vector<string> &words,
             vector<string>::size_type sz)
{
    elimDups(words);        // 将 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, "words", "s")
         << " of length " << sz << " or longer" << endl;
    // 打印长度大于等于给定值的单词，每个单词后面接一个空格
    for_each(wc, words.end(),
            [] (const string &s) {cout << s << " ";});
    cout << endl;

}

3.3 lambda 捕获和返回

当定义一个 lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。在14.8.1将介绍这种类时如何生成的。目前，可以这样理解。当向一个函数传递一个lambda时，同时定义一个新类型和该类型的一个对象：传递的参数就是此编译器生成的类类型的未命名对象。

lambda捕获方式和参数传递类似，可以时值或引用，下表列出了几种不同的捕获列表方式

值捕获

值捕获，与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在 lambda创建时拷贝，而不是调用时拷贝：

void fcn1()
{
    size_t v1 = 42;		// 局部变量
    // 将 v1 拷贝到名为f的可调用对象
    auto f = [v1] { return v1; }
    v1 = 0;
    auto j = f();	// j 为42；f将保存类我们创建它时v1的拷贝
}

引用捕获

我们定义lambda 时可以采用引用方式捕获变量

void fcn2()
{
    size_t v1 = 42;
    auto f2 = [&v1] {return v1;};
    v1 = 0;
    auto j = f2();		// j 为0； f2保存v1的引用，而非拷贝
}

引用捕获和返回引用有着相同的问题和限制。在调用lambda表达式和返回引用的时候，我们要保证捕获的引用变量是存在的，而没有被销毁。

引用捕获有时是必要的，有些对象是不允许拷贝的，比如输入和输出流

void biggies(vector<string> &words,
             vector<string>::size_type sz，
            ostream &os = cout , char c = ' ')
{
    // 与z
    
	// 打印 count 的语句改为打印到 os
    for_each(words.begin(), words.end(),
            [&os, c] (const string &s) {os << s << c;});

}

隐式捕获

除了显式的列出我们希望使用来自所在函数的变量之外，还可以让编译器根据 lambda 体中的代码来推断我们要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个 & 或 = 。& 告诉编译器采用捕获引用方式， = 则表示采用值捕获方式。

// sz 为隐式捕获，值捕获方式
wc = find_if(words.begin(), words.end(),
            [=] (const string &s)
             { return s.size() >= sw; });

混合使用隐式和显式捕获：

void biggies(vector<string> &words,
            vector<string>::size_type sz,
            ostream &os = cout, char c = ' ')
{
    // 其他处理与前例一样
    // os 隐式捕获，引用捕获方式； c显式捕获，值捕获方式
    for_each(words.begin(), words.end(),
            [&, c](const string &s) { os << s << c; });
    // os 显式捕获，引用捕获方式； c 隐式捕获，值捕获方式
    for_each(words.begin(), words.end(),
            [=, &os](const string &s) {os << s << c;});
}

但我们混合使用隐式捕获和显式捕获时，捕获列表中的第一个元素必须是一个 & 或 =

可变lambda

默认情况下，值拷贝的变量，lambda不会改变其值，如果需要改变，就必须在参数列表后加上关键字 mutable

void fcn3()
{
    size_t v1 = 42;		// 局部变量
    // f 可以改变它所捕获的变量的值
    auto f = [v1] ()mutable {return ++v1;};
    v1 = 0;
    auto j = f();		// j 为 43
}

对于引用方式捕获的变量，依赖于引用是否为 const

void fcn4()
{
    size_t v1 = 42;		// 局部变量
    // v1 是一个非 const 变量的引用
    // 可以通过f2中的引用来改变它
    auto f2 = [&v1] {return ++v1;};
    v1 = 0;
    auto j = f2();	// j 为1
}

指定 lambda的返回类型

到目前为止，我们所编写的lambda都只包含单一的 return 语句，这种形式的 lambda表达式无须指定返回类型，编译器会自动推断返回类型。如果一个lambda表达式包含 return 之外的任何语句，则编译器假定此 lambda 表达式返回 void .

示例

transform(vi.begin(), vi.end(), vi.begin(),
         [](int i) { return i < 0 ? -i : i; });

如果就上面改成 if 语句，就会产生编译错误

transform(vi.begin(), vi.end(), vi.begin(),
         [](int i) {if (i < 0) return -1; else return i; });

编译器推断的返回类型是 void , 但它返回了一个 int 值，正确的做法是指定返回类型，而且必须使用尾置返回类型

transform(vi.begin(), vi.end(), vi.begin(),
         [](int i) -> int
         {if (i < 0) return -1; else return i; });

3.4 参数绑定

在使用一个接受一元谓词的算法 find_if , 我们通过给算法传递lambda表达式实现调用外部的变量，除了lambda表达式的方法，还可以使用参数绑定。

以下面这个函数为例，介绍参数绑定的用法

bool check_size(const string &s, string::size_type sz)
{
    return s.size() >= sz;
}

标准库 bind 函数

check_size 是有两个参数的，我们可以使用一个名为 bind 的标准库函数，它定义在头文件 functional 中。可以将 bind 函数看作一个通用的函数适配器，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。

调用 bind 的一般形式为：

auto newCallable = bind(callable, arg_list);

newCallable 本身是一个可调用对象，arg_list 是一个逗号分隔的参数列表，对应给定的callable 的参数。

arg_list 中的参数可能包含形如 _n 的名字， 其中 n 是一个整数。这些参数是 “占位符”，表示 newCallable 的参数，它们占据了传递给newCallable的参数的“位置”。数值 n 表示生成的可调用对象中参数的位置：_1 为 newCallable 的第一个参数，_2为第二个参数，依此类推。

绑定 check_size 的sz参数

auto check6 = bind(check_size, _1, 6);
//调用
string s = "hello";
bool b1 = check6(s);	// check6(s) 会调用check_size(s,6)
// 使用bind,我们可以将原来基于 lambda 的 find_if 调用：
auto wc = find_if(words.begin(), words.end(),
            	[=] (const string &s) { return s.size() >= sw; });
//替换为：
auto wc = find_if(words.begin(), words.end(),
                  bind(check_size, _1, sz)));

使用 placeholders 名字

名字 _1 都定义在一个名为 placeholders 的命名空间中，而这个命名空间本身定义在 std 命名空间中。为了使用这些名字，我们可以使用以下声明

using std::placeholders::_1;		// 只使用 _1
// 或者
using namespace std::placeholders;	//使用全部的参数

bind参数

假定 f 是一个可调用对象，它有5个参数，则下面对 bind 的调用：

// g 是一个有两个参数的可调用对象
auto g = bind(f, a, b, _2, c, _1);

传递给 g 的参数按位置绑定到占位符。即，第一个参数绑定到 _1, 第二个参数绑定到 _2 。

g（x,y);
// 实际调用：
f(a, b, y, x, e);

用 bind 重排参数顺序

下面是用 bind 重排参数顺序的一个具体例子，我们可以用bind颠倒 isShroter 的含义

// 按单词长度有短至长排序
sort(words.begin(), words.end(), isShorter);
// 按单词长度有长至短排序
sort(words.begin(), words.end(), bind(isShorter, _2, _1));

绑定引用参数

默认情况下， bind 的那些不是占位符的参数被拷贝到 bind 返回的可调用对象中。但是，与lambda类似，有时对有些绑定的参数我们希望以引用的方式传递，或是要绑定参数的类型无法拷贝。

例如，为了替换一个引用方式捕获 ostream 的lambda:

// os 是一个局部变量，引用一个输出流
// c 是一个局部变量，类型为char
for_each(words.begin(), words.begin(),
        [&os, c](const string &s){os << s << c;});
// 
ostream &print(ostream &os, const string &s, char c)
{
    return os << s << c;
}
// 错误：不能拷贝 os
for_each(words.begin(), words.begin(),
        bind(print, os, _1, ' '));
// 使用标准库ref函数，传递引用
for_each(words.begin(), words.begin(),
        bind(print, ref(os), _1, ' '));

函数 ref 返回一个对象，包含给定的引用，此对象是可以拷贝的。标准库中还有一个 cref 函数，生成一个保存 const 引用的类。它们都定义在头文件 functional 中。

4. 再谈迭代器

除了为每个容器定义的迭代器之外，标准在头文件 iterator 中还定义了额外几种迭代器。这些迭代器包括以下几种

• 插入迭代器：这些迭代器被绑定到一个容器上，可用来向容器插入元素
• 流迭代器：这些容器被绑定到一个输入或输出流上，可用来遍历所关联的IO流
• 反向迭代器：这些迭代器向后而不是向前移动。除了 forward_list 之外的标准容器都有反向迭代器
• 移动迭代器：这些专用的迭代器不是拷贝其他的元素，而是移动它们

4.1 插入迭代器

插入迭代器是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素。

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

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

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 包含 1 2 3 4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

4.2 iostream 迭代器

• TODO

4.3 反向迭代器

• TODO

5. 泛型算法结构

C++ STL 提供的泛型算法不是直接操作容器的，而是通过迭代器操作数据的，这些算法所需要的迭代器操作可以分为5个迭代器类别

5.1 5类迭代器

迭代器是按他们所提供的操作来分类的，而这种分类形成了一种层次。除了输出迭代器之外，一个高层次类别的迭代器支持低层类别迭代器的所有操作。C++ 标准指明了泛型和数值算法的每个迭代器参数的最小类别。例如， find 算法在一个序列上进行一遍扫描，对元素进行只读操作，因此至少需要输入迭代器。

对于向一个算法传递错误类别的迭代器的问题，很多编译器不会给出任何警告或提示

迭代器类别

输入迭代器 ： 可以读取序列中的元素。一个输入迭代器必须支持

• 用于比较两个迭代器的相等和不相等运算符 (==、!=)

• 用于推进迭代器的前置和后置递增运算 (++)

• 用于读取元素的解引用运算符（*）；解引用只会出现在赋值运算符的右侧

• 箭头运算符（->），等价于 (*it).member，即，解引用迭代器，并提取对象的成员

输出迭代器 : 可以看作输入迭代器功能上的补集——只写而不读元素。输入迭代器必须支持

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

前向迭代器：可以读写元素。这类迭代器只能在序列中沿一个方向移动。

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

随机访问迭代器：提供在常量时间内访问序列中任意元素的能力。此外还支持以下操作：

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

5.2 算法形参模式

大多数算法具有如下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);

beg 和 end 表示算法所操作的输入范围。几乎所有算法都接受一个输入范围，是否有其他参数依赖于要执行的操作。这里列出了常见的一种——dest 、beg2 和 end2，都是迭代器参数。

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

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

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

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

接受单独的 beg2 或者接受beg2 和 end2 的算法用这些迭代器表示第二个输入范围。

5.3 算法命名规范

除了参数规范，算法还遵循一套命名和重载规范。

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

接受谓词参数来代替 <= 或 == 运算符的算法，以及那些不接受额外参数的算法，通常都是重载的函数。

例如

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

_if 版本的算法

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

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

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

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

reverse(beg, end);		// 将反转输入范围中元素的顺序
reverse(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; });

6. 特定容器算法

链表类型 list 和 forward_list 定义了几个成员函数形式的算法，如下表

对于 list 和 forward_list ，通用版本的算法相比没有成员函数版本的算法高效

splice 成员

链表类型还定义了 splice 算法，此算法是链表数据结构所特有的，因此不需要通用版本

链表特有的操作会改变容器

多数链表特有的算法都与其通用版本很相似，但不完全相同。链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层容器。例如， remove 的链表版本会删除元素。