【C++】泛型算法（三）：定制操作

10.3 定制操作

标准库为泛型算法提供了额外的版本，允许我们提供自定义的操作，来替代默认运算符。

比如，sort 算法默认使用元素类型的 < 运算符。但可能我们希望的排序顺序与 < 所定义的顺序不同，或是序列可能保存的是未定义 < 运算符的元素类型（比如之前文章中所定义的 Sales_data 类）。在上述情况下，都需要重载 sort 的默认行为。

10.3.1 向算法传递函数

假定针对一个元素类型为字符串 string 的 vector，且 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();
}
sort(words.begin(), words.end(), isShorter);

排序算法

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

elimDumps(words);
stable_sort(words.begin(), words.end(), isShorter);

10.3.2 lambda 表达式

根据算法接受一元谓词还是二元谓词，传递给算法的谓词必须严格接受一个或两个参数。

但有时我们希望进行的操作需要更多的参数，超出了算法对谓词的限制。（因此，引入 lambda 表达式的目的是突破一元谓词和二元谓词对参数个数限制的上限）

下面是一个例子，仍然是对上述存储 string 的 vector 容器进行操作，求大于等于一个给定长度的单词有多少。我们还会修改输出使得程序只打印大于等于给定长度的单词。

将函数命名为 biggies：

void biggies(vector<string> &words, vector<string>::size_type sz) {
	elimDumps(words);	// 首先按字典序排序, 然后去重
	stable_sort(words.begin(), words.end(), isShorter);
}

当前要解决的问题可以化简为寻找第一个大于等于给定长度的单词元素，根据其位置可以计算出有多少元素的长度是大于等于给定值的。

可以使用标准库 find_if 算法来查找第一个具有特定大小的元素。类似 find，find_if 接受一个迭代器范围以及一个谓词。find_if 对输入序列中的每个元素调用给定的谓词。find_if 返回第一个使谓词返回非 0 值的元素，如果不存在这样的元素则返回尾迭代器。

编写一个函数令其接受一个 string 和一个长度，并返回一个 bool 值表示该 string 的长度是否大于给定长度是很容易的事情。但是，find_if 接受的是一元谓词，因此我们传递给 find_if 的任何函数都必须严格接受一个参数，以便能用来自输入序列的一个元素调用它。

没有任何办法能传递给它第二个参数来表示长度。为了解决这一问题，引入一些额外的语言特性。

介绍 lambda

可以向一个算法传递任何类别的可调用对象（callable object）。

到目前为止，我们仅使用过函数和函数指针这两种可调用对象。

接下来要引入的 lambda 表达式也是一种可调用对象。一个 lambda 表达式表示一个可调用的代码单元。可以将其理解为一个未命名的内联函数。与任何函数类似，一个 lambda 具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda 可能定义在函数内部。

一个 lambda 表达式具有如下形式：

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

其中，capture list（捕获列表）是一个 lambda 所在函数中定义的局部变量的列表（通常为空）；return type、parameter list 和 function body 与任何普通函数都相同。然而，与普通函数不同的是，lambda 表达式必须使用尾置返回，来指定返回类型。

一个最简单的 lambda 表达式的例子如下，在此例中我们忽略了参数列表和返回类型，但必须永远包含捕获列表和函数体：

auto f = [] {return 42; }; // 注意 lambda 表达式的函数体定义结尾需要加上 ;

lambda 表达式忽略括号和参数列表等价于指定一个空参数列表。

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

向 lambda 传递参数

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

下面给出一个与 isShorter 函数功能相同的 lambda：

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

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

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

使用捕获列表

现在我们已经准备好解决最初的问题了——编写一个可以传递给 find_if 的可调用表达式。我们希望这个表达式能够将输入序列中每个 string 的长度与 biggies 函数中的 sz 参数的值进行比较。

一个 lambda 通过将局部变量包含在其捕获列表中来指出将会使用这些变量。捕获列表指引 lambda 在其内部包含访问局部变量所需要的信息。

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

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

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

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

调用 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() 的拷贝。

for_each 算法

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

for_each(wc, words.end(), [](const string &s) {cout << s << " ";});

捕获列表为空，是因为我们只对 lambda 所在函数中定义的变量使用捕获列表。一个 lambda 可以直接使用定义在函数之外的名字。在本例中，cout 不是定义在函数 biggies 中的局部名字，它定义在头文件 iostream 中。

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

完整的 biggies

void biggies(vector<string> &words, vector<string>::size_type sz) {
	elimDups(words);	// 按字典序排序后去重
	stable_sort(words.begin(), words.end(), [] (const string &a, const string &b)
		{ return a.size() < b.size(); });
	auto wc = find_if(words.begin(), words.end(), [sz] (const string &a) 
		{ return a.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;
}

10.3.3 lambda 捕获和返回

定义一个 lambda 时，编译器生成一个与 lambda 对应的新的（未命名的）类类型。

目前可以理解为，当向一个函数传递一个 lambda 时，同时定义了一个新类型和该类型的对象：传递的参数就是此编译器生成的类类型的未命名对象。类似的，当使用 auto 定义一个用 lambda 初始化的变量时，定义了一个从 lambda 生成的类型的对象。

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

值捕获

类似参数传递，lambda 当中变量的捕获方式也可以是值或引用。到目前为止，我们的 lambda 采用值捕获的方式。与传值参数类似，值捕获的前提是变量可拷贝。与参数不同，被捕获的变量是在 lambda 被创建时捕获，而不是在调用时捕获：

void fcn1() {
	size_t v1 = 42;
	auto f = [v1] { return v1; };
	v1 = 0;
	auto j = f();		// j 为 42, f 保存了创建它时 v1 的拷贝
}

引用捕获

同样可以采取引用的方式来对变量进行捕获：

void fcn2() {
	size_t v1 = 42;
	auto f2 = [&v1] { return v1; };
	v1 = 0;
	auto j = f2();	// j 为 0
}

如果我们采用引用方式捕获一个变量，就必须确保引用的对象在 lambda 执行的时候是存在的。

建议：尽量保持 lambda 的变量捕获简单化。

隐式捕获

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

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

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

void biggies(vector<string> &words, vector<string>::size_type, sz,
			 ostream &os = cout, char c = ' ') {
	for_each(words.begin(), words.end(), [&, c](const string &s) { os << s << c; });
	for_each(words.begin(), words.end(), [=, &os](const string &s) { os << s << c; });
}

注意，当混合使用隐式和显式捕获时，显示捕获的变量必须采用与隐式捕获不同的方式。即，如果隐式捕获采用引用捕获，则显示捕获必须采用值捕获。并且，在混合捕获时，捕获列表中的第一个元素必须是 = 或 &，来指定隐式捕获的方式（即隐式捕获必须在前，且隐式捕获和显式捕获的方式必须不同）。

可变 lambda

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

void fcn3() {
	size_t v1 = 42;
	auto f = [v1] () mutable { return ++ v1; };
	v1 = 0;
	auto j = f(); // j == 43
}

而一个引用捕获是否可以被改变取决于引用指向的是否为 const 类型。

指定 lambda 的返回类型

到目前为止，给出的例子当中都只包含单一的 return，尚未遇到必须指定返回类型的情况。默认情况下，如果一个 lambda 包含 return 之外的任何语句，则编译器假定此 lambda 返回 void。与其它返回 void 的函数类似，被推断返回 void 的lambda不能返回值。

以下给出一个简单的例子，该例中使用标准库当中的泛型算法 transform 和一个 lambda 来将序列中的每一个负数替换为其绝对值：

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

函数 transform 接受三个迭代器，前两个指明迭代器范围，第三个迭代器表示目的位置。算法对输入序列中每个元素调用可调用对象，并将结果写到目的位置。

本例中，传递给 transform 一个 lambda，它返回其参数的绝对值。lambda 体是单一的 return 语句，返回一个条件表达式的结果。因此我们无需指定返回类型，因为可以通过条件运算符的类型推断出来。

但是如果将 lambda 的返回值替换为等价的 if 语句，就会产生编译错误：

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

编译器推断这个版本的 lambda 返回 void，但实际返回 int。

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

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

10.3.4 参数绑定

对于只在一两个地方使用的简单操作，lambda 表达式是最有用的。而如果需要在很多地方使用相同的操作，则通常应该定义为一个哈含糊。

如果 lambda 的捕获列表为空，通常可以用函数来替代它。正如前面的例子中所提到的，既可以使用 lambda，也可以使用 isShorter，来自定义 sort 的二元谓词。

但是，对于捕获局部变量的 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 的可调用对象必须接受单一参数。biggies 传递给 find_if 的 lambda 使用捕获列表来保存 sz。为了用上例中的 check_size 替代 lambda，必须解决如何向 sz 形参传递一个参数的问题。

标准库 bind 函数

解决上述问题的方法是使用一个名为 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 是第二个参数，以此类推。

绑定 check_size 的 sz 参数

下例使用 bind 生成一个调用 check_size 的对象，如下所示，它用一个定值作为其大小参数来调用 check_size：

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

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

string s = "hello";
bool b1 = check6(s);

使用 bind，可以替换原来 lambda 版本的 find_if 为：

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

使用 placeholders 名字

名字_n 都定义在一个名为 placeholders 的命名空间中，这个命名空间本身定义在 std 命名空间中。

对于每一个占位符名字，我们都必须提供一个单独的 using 声明：

using namespace namespace_name;

这种形式说明希望来自 namespace_space 的名字可以在我们的程序中直接使用：

using namespace std::placeholders;

上述声明使得 placeholders 定义的所有名字都可以使用。placeholders 与 bind 一样定义在 functional 头文件中。

bind 的参数

上文提到，bind 可以修正参数的值。更一般地，可以用 bind 绑定给定可调用对象中的参数或重新安排其属顺序。例如，假定 f 是一个可调用对象，有 5 个参数，则：

auto g = bind(f, a, b, _2, c, _1)l

将生成一个新的可调用对象，它有两个参数，分别用占位符 _2 和 _1 表示。传递给 g 的参数按位置绑定到占位符。这个 bind 的调用会将：

g(_1, _2)

映射为

f(a, b, _2, c, _1)

例如，调用g(X, Y)实际上会调用：

f(a, b, Y, c, X)

用 bind 重排参数顺序

可以用 bind 颠倒 isShorter 的含义：

sort(words.begin(), words.end(), bind(isShorter, _2, _1));

等价于 sort 的谓词变为调用isShorter(B, A)。

绑定引用参数

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

例如：

for_each(words.begin(), words.end(), [&os, c] (const string &s) { os << s << c; });

可以很容易地编写一个函数，完成相同的工作：

ostream &print(ostream &os, const string &s, char c) {
	return os << s << c;
}

但是，不能直接用 bind 来替代 os 的捕获。原因在于 bind 会拷贝其参数，但是 ostream 不能拷贝。如果我们希望传递给 bind 一个对象而不是拷贝它，就必须使用标准库 ref 函数：

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

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