C++ Primer 第十章 泛型算法

顺序容器只定义了很少的操作：在多数情况下，我们可以添加和删除元素。访问首尾元素、确定容器是否为空以及获得指向首元素或尾元素之后位置的迭代器。

如果我们想要做：查找特定元素、替换或删除一个特定值、重排元素顺序等。标准库并未给每个容器都定义成员函数来实现这些操作，而是定义了一组泛型算法：称它们为“算法”，是因为它们实现了一些经典算法的公共接口，如排序和搜索；称它们是“泛型的”，是因为它们可用于不同类型的元素和多种容器类型（不仅包括标准库类型，如vector或list，还包括内置的数组类型）。

10.1 概述

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

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

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

泛型算法本身不会执行容器的操作，它们只会运行与迭代器之上，执行迭代器的操作。泛型算法运行于迭代器之上而不会执行容器操作的特性带来了一个令人惊讶但非常必要的编程假定：算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素。

10.2 初识泛型算法

除了少数例外，标准库算法都对一个范围内的元素进行操作。我们将此元素范围称为“输入范围”。接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指想要处理的第一个元素和尾元素之后位置的迭代器。

10.2.1 只读算法

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

10.2.1.1 accumulate

另一个只读算法是accumulate，它定义在头文件numeric中。accumulate函数接受三个参数，前两个指出了需要求和的元素的范围，第三个参赛是和的初值。假定 vec 是一个整数序列，则：

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

这条语句将 sum 设置为 vec 中元素的和，和的初值被设置为0.

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

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

下面是另一个例子，由于string定义了+运算符，所有我们可以通过调用accumulate来将vector中所有string元素连接起来：

string sum = accumulate(v.cbegin(), v.cend(), string(""));

此调用将 v 中每个元素连接到一个string上，该string初始时是空串。注意，我们通过第三个参数显式地创建了一个string。将空串当做一个字符串字面值传递给第三个参数是不可以的，会导致一个编译错误：

//错误：const char*上没有定义+运算符
string sum = accumulate(v.cbegin(), v.cend(), "");

原因在于，如果我们传递了一个字符串字面值，用于保存和的对象的类型将是const char*。如前所述，此类型决定了使用哪个+运算符。由于const char*并没有+运算符，此调用将产生编译错误。

操作两个序列的算法

10.2.1.2 equal

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

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

由于equal利用迭代器完成操作，因此我们可以通过调用equal来比较两个不同类型的容器中的元素。而且，元素类型也不必一样，只要我们能用==来比较两个元素类型即可。例如，在此例中，roster1 可以是vector<string>,而 roster2 是list<const char*>。

但是，equal基于一个非常重要的假设：它假定第二个序列至少与第一个序列一样长。此算法要处理第一个序列中的每个元素，它假定每个元素在第二个序列中都有一个与之对应的元素。

那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。确保算法不会试图访问第二个序列中不存在的元素是程序员的责任。

10.2.2 写容器元素的算法

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

一些算法会自己向输入范围写入元素，这些算法本质上并不危险，它们最多写入与给定序列一样多的元素。

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

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

由于fill向给定输入序列中写入数据，因此，只要我们传递一个有效的输入序列，写入操作就是安全的。

算法不检查写操作

一些算法接受一个迭代器来指出一个单独的目的位置。这些算法将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。例如，函数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;  //空向量
//灾难：修改vec中10个（不存在）元素
fill_n(vec.begin(), 10, 0);

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

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

10.2.3 介绍 back_inserter

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

为了展示如何用算法向容器中写入数据，我们现在将使用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.

10.2.4 拷贝算法

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

我们可以用copy实现内置数组的拷贝，如下面代码所示：

int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int a2[sizeof(a1) / sizeof(*a1)];
auto ret = copy(begin(a1), end(a1), a2); //把a1的内容拷贝到a2

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

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

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

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

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

//使用back_inserter按需要增长目标序列
replace_copy(ilist.begin(), ilist.end(), back_inserter(ivec), 0, 42);

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

10.2.5 重排容器元素的算法

10.2.5.1 sort

某些算法会重排容器中元素的顺序，一个明显的例子是sort。调用sort会重排输入序列中的元素，使之有序，它是利用元素类型的<运算符来实现排序的。

10.2.5.2 unique

unique算法重排输入序列，将相邻的重复项“消除”，并返回一个指向不重复范围末尾的迭代器。

unique并不真正的删除任何元素，它只是覆盖相邻的重复元素，使得不重复元素出现在序列开始部分，unique返回的迭代器指向最后一个不重复元素之后的位置。此位置之后的元素仍然存在，但我们不知道它们的值是什么。

标准库算法对迭代器而不是容器进行操作。因此，算法不能（直接）添加或删除元素。为了真正删除无用元素，我们必须使用容器操作，例如erase。

10.3 定制操作

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

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

10.3.1 向算法传递函数

sort的第二个版本是重载过的，它接受三个参数，此参数是一个谓词。

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

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

stable_sort算法：这种稳定排序算法维持相等元素的原有顺序。

10.3.2 lambda 表达式

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

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

到目前为止，我们使用过的仅有的两种可调用对象是函数和函数指针。还有其他两种可调用对象：重载了函数调用运算符的类，以及lambda表达式。

一个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; };

此例中，我们定义了一个可调用对象，它不接受参数，返回42.

lambda的调用方式与普通函数的调用方式相同，都是使用调用运算符：

cout << f() << endl; //打印42

在lambda中忽略括号和参数列表等价于指定一个空参数列表。在此例中，当调用 f 时，函数参数列表是空的。如果忽略返回类型，则返回类型从返回的表达式的类型推断而来。否则，返回类型为void。

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

10.3.2.1 向 lambda 传递参数

与普通函数调用类似，调用一个lambda时给定的实参类型被用来初始化lambda的形参。通常，实参和形参的类型必须匹配，但与普通函数不同，lambda不能有默认参数。因此，一个lambda调用的实参数目永远与形参数目相等。一旦形参初始化完毕，就可以执行函数体了。

作为一个带参数的lambda的例子，我们可以编写一个与 isShorter 函数完成相同功能的lambda：

[] (const string &s1, const string &s2)
{ return s1.size() < s2.size(); }

空捕获列表表明此lambda不使用它所在函数中的任何局部变量。lambda的参数与 isShorter 的参数类似，是const string的引用。lambda的函数体也与 isShorter 类型，比较两个参数的size()，并根据两者的相对大小返回一个布尔值。

如下所示，可以使用此lambda来调用stable_sort：

stable_sort(words.begin(), words.end(), [] (const string &s1, const string &s2) { return s1.size()<s2.size(); });

当stable_sort需要比较两个元素时，它就会调用给定的这个lambda表达式。

10.3.2.2 使用捕获列表

编写一个可以传递给find_if的可调用表达式。我们希望这个表达式能将输入序列中每个string的长度与 biggies 函数中的 sz 参数的值进行比较。

虽然一个lambda可以出现在一个函数中，使用其局部变量，但它只能使用那些明确指明的变量。一个lambda通过将局部变量包含在其捕获列表中指出将会使用这些变量。捕获列表指引lambda在其内部包含访问局部变量所需的信息。

在本例中，我们的lambda会捕获 sz，并只有单一的string参数。其函数体会将string的大小与捕获的 sz 的值进行比较：

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

lambda以一对[]开始，我们可以在其中提供一个以逗号分隔的名字列表，这些名字都是它所在函数中定义的。

如果我们给lambda提供了一个空捕获列表，则代码会编译错误：

//错误：sz未捕获
[] (const string &s) { return s.size() >= sz; };

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

一个lambda可以直接使用定义在当前函数之外的名字。捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和在它所在函数之外声明的名字。

10.3.2.3 lambda 捕获和返回

当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象；传递的参数就是此编译器生成的类类型的未命名对象。类似的，当使用auto定义一个用lambda初始化的变量时，定义了一个从lambda生成的类型的对象。

默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员类似任何普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。

10.3.2.4 值捕获

类似参数传递，变量的捕获方式也可以是值或引用。到目前为止，我们的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创建时拷贝，因此随后对其修改不会影响到lambda内对应的值。

10.3.2.5 引用捕获

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

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

一个以引用方式捕获的变量与其他任何类型的引用的行为类似。当我们在lambda函数体内使用此变量时，实际上使用的是引用所绑定的对象。引用捕获与返回引用有着相同的问题和限制。如果我们采用引用方式捕获一个变量，就必须确保被引用的对象在lambda执行的时候是存在的。lambda捕获的都是局部变量，这些变量在函数结束后就不复存在了。如果lambda可能在函数结束后执行，捕获的引用指向的局部变量已经消失。

我们不能拷贝ostream对象，因此捕获os的唯一方式就是捕获其引用（或指向os的指针）。

我们也可以从一个函数返回lambda，函数可以直接返回一个可调用对象，或者返回一个类对象，该类含有可调用对象的数据成员。如果函数返回一个lambda，则与函数不能返回一个局部变量的引用类似，此lambda也不能包含引用捕获。

当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的。

10.3.2.6 隐式捕获

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

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

如果我们希望对一部分变量采用值捕获，对其它变量采用引用捕获，可以混合使用隐式捕获和显式捕获：

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; });
}

当我们混合使用隐式捕获和显式捕获时，捕获列表中的第一个元素必须是一个&或=，此符号指定了默认捕获方式为引用或值。

当混合使用隐式捕获和显式捕获时，显式捕获的变量必须使用与隐式捕获不同的方式。即，如果隐式捕获是引用方式（使用了&），则显示捕获命名变量必须采用值方式，因此不能在其名字前使用&。类似的，如果隐式捕获采用的是值方式（使用了=），则显式捕获命名变量必须采用引用方式，即，在名字前使用&。

10.3.2.7 可变 lambda

默认情况下，对于一个值被拷贝的变量，lambda不会改变其值。如果我们希望能改变一个捕获的变量的值，就必须在参数列表首加上关键字mutable。因此，可变lambda能省略参数列表：

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

一个引用捕获的变量是否（如往常一样）可以修改依赖于此引用指向的是一个const类型还是一个非const类型：

void fcn4()
{
　　size_t v1 = 42;  //局部变量
　　//v1 是一个非 const 变量的引用
　　//可以通过 f2 中的引用来改变它

　　auto f2 = [&v1] { return ++v1; };
　　v1=0;
　　auto j = f2(); //j为1
}

10.3.2.8 指定 lambda 返回类型

默认情况下，如果一个lambda体包含return之外的任何语句，则编译器假定此lambda返回void。与其它返回void的函数类型类似，被推断返回void的lambda不能返回值。

当我们需要为一个lambda定义返回类型时，必须使用尾置返回类型。

10.3.3 参数绑定

对于那种只有一两个地方使用的简单操作，lambda表达式是最有用的。如果我们需要在很多地方使用相同的操作，通常应该定义一个函数，而不是多次编写相同的lambda表达式。类似的，如果一个操作需要很多语句才能完成，通常使用函数更好。

但是，对于捕获局部变量的lambda，用函数来替换它就不是那么容易了。例如，我们用在find_if调用中的lambda比较一个string和一个给定大小。我们可以很容易地编写一个完成同样工作的函数：

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

但是，我们不能用这个函数作为find_if的一个参数。find_if接受一个一元谓词，因此传递给find_if的可调用对象必须接受单一参数。为了用 check_size 函数来代替lambda，必须解决如何向 sz 形参传递一个参数的问题。

10.3.3.1 标准库 bind 函数

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

调用bind的一般形式：

auto newCallable = bind(callable, arg_list);

其中，newCallable 本身是一个可调用对象，arg_list 是一个逗号分隔的参数列表，对应给定的 callable 的参数。即，当我们调用 newCallable 时，newCallable 会调用 callable，并传递给它 arg_list 中的参数。

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

10.3.3.2 绑定 check_size 的 sz 参数

作为一个简单的例子，我们将使用bind生成一个调用 check_size 的对象，如下所示，它用一个定值作为其大小参数来调用 check_size:

//check6 是一个可调用对象，接受一个 string 类型的参数
//并用此 string 和值6来调用 check_size
auto check6 = bind(check_size, _1, 6);

此bind调用只有一个占位符，表示 check6 只接受单一参数。占位符出现在 arg_list 的第一个位置，表示 check6 的此参数对应 check_size 的第一个参数。此参数是一个const string&。因此，调用 check6 必须传递给它一个string类型的参数，check6 会将此参数传递给 check_size。

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(), [sz] (const string &s)

替换为如下使用 check_size 的版本：

auto wc = find_if(words.begin(), words.end(), bind(check_size, _1, sz));

此bind调用生成一个可调用对象，将 check_size 的第二个参数绑定到 sz 的值。

10.3.3.3 placeholders

名字_n都定义在一个名为placeholders的命名空间中，而这个命名空间本身定义在std命名空间中。为了使用这些名字，两个命名空间都要写上。例如，_1对应的using声明为：

using std::placeholders::_1;

此声明说明我们要使用的名字_1定义在命名空间placeholders中，而此命名空间又定义在命名空间std中。

对每个占位符名字，我们都必须提供一个单独的using声明。编写这样的声明很烦人，也很容易出错。可以使用另外一种不同形式的using语句，而不是分别声明每个占位符，如下所示：

using namespace namespace_name;

这种形式说明希望所有来自namespace_name的名字都可以在我们的程序中直接使用。例如：

using namespace std::placeholders;

使得由placeholders定义的所有名字都可用。与bind函数一样，placeholders命名空间也定义在functional头文件中。

10.3.3.4 绑定引用参数

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

bind拷贝其参数，而我们不能拷贝一个ostream，如果我们希望传递给bind一个对象而又不是拷贝它，就必须使用标准库ref函数：

for_each(words.begin(), words.end(), bind(print, ref(os), _1,' '));

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

10.4 再探迭代器

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

10.4.1 插入迭代器

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

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

• 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.begin(), lst.end(), front_inserter(lst2));
//拷贝完成之后 lst3 包含1 2 3 4
copy(lst.begin(), lst.end(), inserter(lst3,lst.begin()));

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

10.4.2 流迭代器

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

10.4.2.1 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_in(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错误，迭代器的值就与尾后迭代器相等。

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

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

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

10.4.2.2 使用算法操作流迭代器

由于算法使用迭代器操作来处理数据，而流迭代器又至少支持某种迭代器操作，因此我们至少可以用某些算法来操作流迭代器。下面是一个例子，我们可以用一对istream_iterator来调用accumulate，此调用会计算出从标准输入读取的值的和:

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

10.4.2.3 istream_iterator 允许使用懒惰求值

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

10.4.2.4 ostream_iterator

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

我们可以使用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
cout << end;

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

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

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

10.4.3 反向迭代器

反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。对于反向迭代器，递增（以及递减）操作的含义会颠倒过来。递增一个反向迭代器（++it）会移动到前一个元素；递减一迭代器（--it）会移动到下一个元素。

除了forward_list之外，其他容器都支持反向迭代器。我们可以通过调用rbegin、rcend、crbegin和crend成员函数来获得反向迭代器。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。与普通迭代器一样，反向迭代器也有const和非const版本。

10.4.3.1 反向迭代器需要递减运算符

我们只能从既支持++也支持--的迭代器来定义反向迭代器。毕竟反向迭代器的目的是在序列中反向移动。除了forward_list之外，标准容器上的其他迭代器都既支持递增运算又支持递减运算。但是，流迭代器不支持递减运算，因为不可能在一个流中反向移动。因此，不可能从一个forward_list或一个流迭代器创建反向迭代器。

10.4.3.2 反向迭代器与其他迭代器间的关系

假定有一个名为 line 的string，保存着一个逗号分隔的单词列表，我们希望打印 line 中的第一个单词，使用find可以很容易地完成这一任务：

//在一个逗号分隔的列表中查找一个元素
auto comma = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), comma) << endl;

如果 line 中有逗号，那么 comma 将指向这个逗号；否则，它将等于 line.cend().当我们打印从 line.cbegin() 到 comma 之间的内容时，将打印到逗号为止的序列，或者打印整个string（如果其中不含逗号的话）。

如果希望打印最后一个单词，可以改用反向迭代器：

//在一个逗号分隔的列表中查找最后一个元素
auto rcomma = find(line.crbegin(), line.crend(), ',');

由于我们将crbegin和crend传递给find，find将从 line 的最后一个字符开始向前搜索。当find完成后，如果 line 中有逗号，则 rcomma 指向最后一个逗号——即，它指向反向搜索中找到的第一个逗号。如果 line 中没有逗号，则 rcomma 指向 line.crend()。

但我们试图打印找到的单词时，看起来下面的代码是显然的方法

//错误:将逆序输出单词的字符
cout << string(line.crbegin(), rcomma) << endl;

但它会生成错误的输出结果。例如，如果我们的输入是：FIRST,MIDOLE,LAST

则这条语句会打印：TSAL

问题所在：我们使用的是反向迭代器，会反向处理string。因此，上述输出语句从crbegin开始反向打印 line 中内容。而我们希望按正常顺序打印从 rcomma 开始到 line 末尾间的字符。但是，我们不能直接使用 rcomma。因为它是一个反向迭代器，意味着它会反向朝着string的开始位置移动。需要做的是，将 rcomma 转换回一个普通迭代器，能在 line 中正向移动。我们通过调用reverse_iterator的base成员函数来完成这一转换，此成员函数会返回其对应的普通迭代器：

//正确：得到一个正向迭代器，从逗号开始读取字符直到 line 末尾
cout << string(rcomma.base(), line.cend()) << endl;

rcomma 和 rcomma.base() 指向了不同的元素，line.crbegin() 和 line.cend() 也是如此。这些不同保证了元素范围无论是正向处理还是反向出来都是相同的。从技术上讲，普通迭代器与反向迭代器的关系反映了左闭合区间的特征。关键点在于 [line.crbegin(),rcomma) 和 [rcomma.base(),line.cend()) 指向 line 中相同的元素范围。

10.5 泛型算法结构

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

10.5.1 5类迭代器

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

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

10.5.1.1 输入迭代器

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

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

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

10.5.1.2 输出迭代器

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

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

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

10.5.1.3 前向迭代器

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

10.5.1.4 双向迭代器

双向迭代器：可以正向/反向读写序列中的元素。除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减运算符（--）。算法reverse要求双向迭代器，除了forward_list之外，其他标准库都提供符合双向迭代器要求的迭代器。

10.5.1.5 随机迭代器

随机访问迭代器：提供在常量时间内访问序列中的任意元素的能力。此类迭代器支持双向迭代器的所有功能，此外还支持如下的操作：

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

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

10.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);

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

10.5.3 算法命名规范

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

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

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

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

10.5.3.2 _if 版本的算法

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

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

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

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

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

10.6 特定容器算法

与其他容器不同，链表类型list与forward_list定义了几个成员函数形式的算法。特别是，它们定义了独有的sort、merge、remove、reverse和unique。通用版本的sort要求随机访问迭代器，因此不能用于list和forward_list，因为这两个类型分别提供双向迭代器和前向迭代器。

链表类型定义的其他算法的通用版本可以用于链表，但代价太高。这些算法需要交换输入序列中的元素。一个链表可以通过改变元素间的链接而不是真正的交换它们的值来传递“交换”元素。因此，这些链表版本的算法的性能比对应的通用版本好很多。

对于list和forward_list应该优先使用成员函数版本的算法而不是通用算法。

list和forward_list成员函数版本的算法，这些操作都返回void：

• lst.merge(lst2)、lst.merge(lst2, comp)：将来自 lst2 的元素合并入 lst。lst 和 lst2 都必须是有序的。元素将从 lst2 中删除。在合并之后，lst2 变为空。第一个版本使用 < 运算符；第二个版本使用给定的比较操作
• lst.remove(val)、lst.remove_if(pred)：调用 erase 删除掉与给定值相等（==）或令一元谓词为真的每个元素
• lst.reverse()：反转 lst 中元素的顺序
• lst.sort()、lst.sort(comp)：使用 < 或给定比较操作排序元素
• lst.unique()、lst.unique(pred)：调用 erase 删除同一值的连续拷贝。第一个版本使用 ==；第二个版本使用给定的二元谓词

10.6.1 splice 成员

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

list和forward_list的splice成员函数的参数：

lst.splice(args)或flst.splice_after(args)

• (p,lst2)：p 是一个指向 lst 中元素的迭代器，或一个指向 flst 首前位置的迭代器。函数将 lst2 的所有元素移动到 lst 中 p 之前的位置或是 flst 中 p 之后的位置。将元素从 lst2 中删除。lst2 的类型必须与 lst 或 flst 相同，且不能是同一个链表
• (p,lst2,p2)：p2 是一个指向 lst2 中位置的有效的迭代器。将 p2 指向的元素移动到 lst 中，或将 p2 之后的元素移动到 flst 中。lst2 可以是与 lst 或 flst 相同的链表
• (p,lst2,b,e)：b 和 e 必须表示 lst2 中的合法范围。将给定范围中的元素从 lst2 移动到 lst 或 flst。lst2 与 lst（或 flst）可以是相同的链表，但 p 不能指向给定范围中元素

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

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

类似的，merge和splice会销毁其参数。例如，通用版本的remove将合并的序列写给一个给定的目的迭代器：两个输入序列是不变的。而链表版本的merge函数会销毁给定的链表——元素从参数指定的链表中删除，被合并到调用merge的链表对象中。在merge之后，来自两个链表中的元素仍然存在，但它们都已在同一个链表中。