【C++基础】系列博客为参考《C++ Primer中文版（第5版）》（C++11标准）一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.定制操作
很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的<或==运算符完成比较。标准库还为这些算法定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符。
例如，sort算法默认使用元素类型的<运算符。但可能我们希望的顺序排序与<所定义的顺序不同，或是我们的序列可能保存的是未定义<运算符的元素类型（如Sales_data）。在这两种情况下，都需要重载sort的默认行为。
2.向算法传递函数
作为一个例子，假定希望在调用elimDups后打印vector的内容。此外还假定希望单词按其长度排序，大小相同的再按字典序排列。为了按长度重排vector，我们将使用sort的第二个版本，此版本是重载过的，它接受第三个参数，此参数是一个谓词（predicate）。
2.1.谓词
谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：一元谓词（unary predicate，意味着它们只接受单一参数）和二元谓词（binary predicate，意味着它们有两个参数）。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。
接受一个二元谓词参数的sort版本用这个谓词代替<来比较元素。我们提供给sort的谓词必须满足一定条件（后续博文会有详细介绍）。当前，我们只需知道，此操作必须在输入序列中所有可能的元素值上定义一个一致的序。比如：
1
2
3
4
5
6
7
//比较函数，用来按长度排序单词
bool isShorter(const string &s1, const string &s2)
{
return s1.size() < s2.size();
}
//按长度由短至长排序words
sort(words.begin(), words.end(), isShorter);
如果words包含的数据与这里的一样，此调用会将words重排，使得所有长度为3的单词排在长度为4的单词之前，然后是长度为5的单词，依此类推。
2.2.排序算法
在我们将words按大小重排的同时，还希望具有相同长度的元素按字典序排列。为了保持相同长度的单词按字典序排列，可以使用stable_sort算法。这种稳定排序算法维持相等元素的原有顺序。
通常情况下，我们不关心有序序列中相等元素的相对顺序，它们毕竟是相等的。但是，在本例中，我们定义的“相等”关系表示“具有相同长度”。而具有相同长度的元素，如果看其内容，其实还是各不相同的。通过调用stable_sort，可以保持等长元素间的字典序：
1
2
3
4
5
6
elimDups(words);//将words按字典序重排，并消除重复单词
//按长度重新排序，长度相同的单词维持字典序
stable_sort(words.begin(), words.end(), isShorter);
for (const auto &s : words)//无须拷贝字符串
cout << s << " ";//打印每个元素，以空格分隔
cout << endl;
假定在此调用前words是按字典序排列的，则调用之后，words会按元素大小排序，而长度相同的单词会保持字典序。如果我们对原来的vector内容运行这段代码，输出为：
1
fox red the over slow jumps quick turtle
3.lambda表达式
根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。
例如我们修改第2.2部分的程序，求大于等于一个给定长度的单词有多少。我们还会修改输出，使程序只打印大于等于给定长度的单词。我们将此函数命名为biggies，其框架如下所示：
1
2
3
4
5
6
7
8
9
void biggies(vector<string> &words, vector<string>::size_type sz)
{
elimDups(words);//将words按字典序排序，删除重复单词
//按长度排序，长度相同的单词维持字典序
stable_sort(words.begin(), words.end(), isShorter);
//获取一个迭代器，指向第一个满足size()>=sz的元素
//计算满足size>=sz的元素的数目
//打印长度大于等于给定值的单词，每个单词后面接一个空格
}
我们的新问题是在vector中寻找第一个大于等于给定长度的元素。一旦找到了这个元素，根据其位置，就可以计算出有多少元素的长度大于等于给定值。
我们可以使用标准库find_if算法来查找第一个具有特定大小的元素。类似find，find_if算法接受一对迭代器，表示一个范围。但与find不同的是，find_if的第三个参数是一个谓词。find_if算法对输入序列中的每个元素调用给定的这个谓词。它返回第一个使谓词返回非0值的元素，如果不存在这样的元素，则返回尾迭代器。
编写一个函数，令其接受一个string和一个长度，并返回一个bool值表示该string的长度是否大于给定长度，是一件很容易的事情。但是，find_if接受一元谓词—我们传递给find_if的任何函数都必须严格接受一个参数，以便能用来自输入序列的一个元素调用它。没有任何办法能传递给它第二个参数来表示长度。为了解决此问题，需要使用另外一些语言特性。
3.1.介绍lambda
我们可以向一个算法传递任何类别的可调用对象（callable object）。对于一个对象或一个表达式，如果可以对其使用调用运算符，则称它为可调用的。即，如果e是一个可调用的表达式，则我们可以编写代码e(args)，其中args是一个逗号分隔的一个或多个参数的列表。
到目前为止，我们使用过的仅有的两种可调用对象是函数和函数指针。还有其他两种可调用对象：重载了函数调用运算符的类（后续博文会有详细介绍），以及lambda表达式（lambda expression）。
一个lambda表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个lambda具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda可能定义在函数内部。一个lambda表达式具有如下形式：
1
[capture list] (parameter list) -> return type { function body }
其中，capture list（捕获列表）是一个lambda所在函数中定义的局部变量的列表（通常为空）；return type、parameter list和function body与任何普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同，lambda必须使用尾置返回来指定返回类型。
我们可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体：
1
auto f = [] { return 42; };
此例中，我们定义了一个可调用对象f，它不接受参数，返回42。lambda的调用方式与普通函数的调用方式相同，都是使用调用运算符：
1
cout << f() << endl;//打印42
在lambda中忽略括号和参数列表等价于指定一个空参数列表。在此例中，当调用f时，参数列表是空的。如果忽略返回类型，lambda根据函数体中的代码推断出返回类型。如果函数体只是一个return语句，则返回类型从返回的表达式的类型推断而来。否则，返回类型为void。
如果lambda的函数体包含任何单一return语句之外的内容，且未指定返回类型，则返回void。
3.2.向lambda传递参数
与一个普通函数调用类似，调用一个lambda时给定的实参被用来初始化lambda的形参。通常，实参和形参的类型必须匹配。但与普通函数不同，lambda不能有默认参数。因此，一个lambda调用的实参数目永远与形参数目相等。一旦形参初始化完毕，就可以执行函数体了。
作为一个带参数的lambda的例子，我们可以编写一个与isShorter函数完成相同功能的lambda：
1
[] (const string &a, const string &b) { return a.size() < b.size(); }
空捕获列表表明此lambda不使用它所在函数中的任何局部变量。如下所示，可以使用此lambda来调用stable_sort：
1
2
3
4
//按长度排序，长度相同的单词维持字典序
stable_sort(words.begin(), words.end(),
[] (const string &a, const string &b)
{ return a.size() < b.size(); });
当stable_sort需要比较两个元素时，它就会调用给定的这个lambda表达式。
3.3.使用捕获列表
我们现在已经准备好解决原来的问题了—编写一个可以传递给find_if的可调用表达式。我们希望这个表达式能将输入序列中每个string的长度与biggies函数中的sz参数的值进行比较。
虽然一个lambda可以出现在一个函数中，使用其局部变量，但它只能使用那些明确指明的变量。一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量。捕获列表指引lambda在其内部包含访问局部变量所需的信息。
在本例中，我们的lambda会捕获sz，并只有单一的string参数。其函数体会将string的大小与捕获的sz的值进行比较：
1
[sz] (const string &a) { return a.size() >= sz; };
lambda以一对[]开始，我们可以在其中提供一个以逗号分隔的名字列表，这些名字都是它所在函数中定义的。
由于此lambda捕获sz，因此lambda的函数体可以使用sz。lambda不捕获words，因此不能访问此变量。如果我们给lambda提供一个空捕获列表，则代码会编译错误：
1
2
//错误：sz未捕获
[] (const string &a) { return a.size() >= sz; };
一个lambda只有在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用该变量。
3.4.调用find_if
使用此lambda，我们就可以查找第一个长度大于等于sz的元素：
1
2
3
4
//获取一个迭代器，指向第一个满足size()>=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的末尾一共有多少个元素：
1
2
3
4
5
6
7
string make_plural(size_t ctr, const string &word, const string &ending)
{
return (ctr > 1) ? word + ending : word;
}
//计算满足size>=sz的元素的数目
auto count = words.end() - wc;
cout << count << " " << make_plural(count, "word", "s") << " of length " << sz << " or longer" << endl;
3.5.for_each算法
问题的最后一部分是打印words中长度大于等于sz的元素。为了达到这一目的，我们可以使用for_each算法。此算法接受一个可调用对象，并对输入序列中每个元素调用此对象：
1
2
3
4
//打印长度大于等于给定值的单词，每个单词后面接一个空格
for_each(wc, words.end(),
[] (const string &s) { cout << s << " "; });
cout << endl;
捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和在它所在函数之外声明的名字。
3.6.完整的biggies
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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, "word", "s") << " of length " << sz << " or longer" << endl;
//打印长度大于等于给定值的单词，每个单词后面接一个空格
for_each(wc, words.end(),
[] (const string &s) { cout << s << " "; });
cout << endl;
}
4.lambda捕获和返回
当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。我们将在后续博文中介绍这种类是如何生成的。目前，可以这样理解，当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象：传递的参数就是此编译器生成的类类型的未命名对象。类似的，当使用auto定义一个用lambda初始化的变量时，定义了一个从lambda生成的类型的对象。
默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员。类似任何普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。
4.1.值捕获
类似参数传递，变量的捕获方式也可以是值或引用。表10.1列出了几种不同的构造捕获列表的方式。到目前为止，我们的lambda采用值捕获的方式。与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝：
1
2
3
4
5
6
7
8
void fcn1()
{
size_t v1 = 42;//局部变量
//将v1拷贝到名为f的可调用对象
auto f = [v1] { return v1; };
v1 = 0;
auto j = f();//j为42；f保存了我们创建它时v1的拷贝
}
由于被捕获变量的值是在lambda创建时拷贝，因此随后对其修改不会影响到lambda内对应的值。
4.2.引用捕获
我们定义lambda时可以采用引用方式捕获变量。例如：
1
2
3
4
5
6
7
8
void fcn2()
{
size_t v1 = 42;//局部变量
//对象f2包含v1的引用
auto f2 = [&v1] { return v1; };
v1 = 0;
auto j = f2();//j为0；f2保存v1的引用，而非拷贝
}
引用捕获与返回引用有着相同的问题和限制。引用捕获有时是必要的。例如，我们可能希望biggies函数接受一个ostream的引用，用来输出数据，并接受一个字符作为分隔符：
1
2
3
4
5
6
7
8
9
void biggies(vector<string> &words,
vector<string>::size_type sz,
ostream &os = cout, char c = ' ')
{
//与之前例子一样的重排words的代码
//打印count的语句改为打印到os
for_each(words.begin(), words.end(),
[&os, c] (const string &s) { os << s << c; });
}
我们不能拷贝ostream对象，因此捕获os的唯一方法就是捕获其引用（或指向os的指针）。
我们也可以从一个函数返回lambda。函数可以直接返回一个可调用对象，或者返回一个类对象，该类含有可调用对象的数据成员。如果函数返回一个lambda，则与函数不能返回一个局部变量的引用类似，此lambda也不能包含引用捕获。
当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的。
4.3.隐式捕获
除了显式列出我们希望使用的来自所在函数的变量之外，还可以让编译器根据lambda体中的代码来推断我们要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个&或=。&告诉编译器采用捕获引用方式，=则表示采用值捕获方式。例如，我们可以重写传递给find_if的lambda：
1
2
3
//sz为隐式捕获，值捕获方式
wc = find_if(words.begin(), words.end(),
[=] (const string &s) { return s.size() >= sz; });
如果我们希望对一部分变量采用值捕获，对其他变量采用引用捕获，可以混合使用隐式捕获和显式捕获：
1
2
3
4
5
6
7
8
9
10
11
12
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; });
}
当我们混合使用隐式捕获和显式捕获时，捕获列表中的第一个元素必须是一个&或=。此符号指定了默认捕获方式为引用或值。⚠️当混合使用隐式捕获和显式捕获时，显式捕获的变量必须使用与隐式捕获不同的方式。
4.4.可变lambda
默认情况下，对于一个值被拷贝的变量，lambda不会改变其值。如果我们希望能改变一个被捕获的变量的值，就必须在参数列表首加上关键字mutable。因此，可变lambda能省略参数列表：
1
2
3
4
5
6
7
8
void fcn3()
{
size_t v1 = 42;//局部变量
//f可以改变它所捕获的变量的值
auto f = [v1] () mutable { return ++v1; };
v1 = 0;
auto j = f();//j为43
}
一个引用捕获的变量是否（如往常一样）可以修改依赖于此引用指向的是一个const类型还是一个非const类型：
1
2
3
4
5
6
7
8
9
void fcn4()
{
size_t v1 = 42;//局部变量
//v1是一个非const变量的引用
//可以通过f2中的引用来改变它
auto f2 = [&v1] { return ++v1; };
v1 = 0;
auto j = f2();//j为1
}
4.5.指定lambda返回类型
到目前为止，我们所编写的lambda都只包含单一的return语句。因此，我们还未遇到必须指定返回类型的情况。默认情况下，如果一个lambda体包含return之外的任何语句，则编译器假定此lambda返回void。与其他返回void的函数类似，被推断返回void的lambda不能返回值。
下面给出了一个简单的例子，我们可以使用标准库transform算法和一个lambda来将一个序列中的每个负数替换为其绝对值：
1
2
transform(vi.begin(), vi.end(), vi.begin(),
[] (int i) { return i < 0 ? -i : i; });
函数transform接受三个迭代器和一个可调用对象。前两个迭代器表示输入序列，第三个迭代器表示目的位置。算法对输入序列中每个元素调用可调用对象，并将结果写到目的位置。如本例所示，目的位置迭代器与表示输入序列开始位置的迭代器可以是相同的。当输入迭代器和目的迭代器相同时，transform将输入序列中每个元素替换为可调用对象操作该元素得到的结果。我们无须指定返回类型，因为可以根据条件运算符的类型推断出来。
transform函数源码见下：
测试几个例子：
但是，如果我们将程序改写为看起来是等价的if语句，就会产生编译错误：
1
2
3
//错误：不能推断lambda的返回类型
transform(vi.begin(), vi.end(), vi.begin(),
[] (int i) { if(i<0) return -i; else return i; });
编译器推断这个版本的lambda返回类型为void，但它返回了一个int值。当我们需要为一个lambda定义返回类型时，必须使用尾置返回类型：
1
2
3
transform(vi.begin(), vi.end(), vi.begin(),
[] (int i) -> int
{ if(i<0) return -i; else return i; });
5.参数绑定
对于那种只在一两个地方使用的简单操作，lambda表达式是最有用的。如果我们需要在很多地方使用相同的操作，通常应该定义一个函数，而不是多次编写相同的lambda表达式。类似的，如果一个操作需要很多语句才能完成，通常使用函数更好。
但是，对于捕获局部变量的lambda，用函数来替换它就不是那么容易了。例如，我们用在find_if调用中的lambda比较一个string和一个给定大小。我们可以很容易地编写一个完成同样工作的函数：
1
2
3
4
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形参传递一个参数的问题。
5.1.标准库bind函数
我们可以解决向check_size传递一个长度参数的问题，方法是使用一个新的名为bind的标准库函数，它定义在头文件functional中。可以将bind函数看作一个通用的函数适配器，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。
调用bind的一般形式为：
1
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为第二个参数，依此类推。
5.2.绑定check_size的sz参数
作为一个简单的例子，我们将使用bind生成一个调用check_size的对象，如下所示，它用一个定值作为其大小参数来调用check_size：
1
2
3
//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。
1
2
string s = "hello";
bool b1 = check6(s);//check6(s)会调用check_size(s, 6)
使用bind，我们可以将原来基于lambda的find_if调用替换为如下使用check_size的版本：
1
2
auto wc = find_if(words.begin(), words.end(),
bind(check_size, _1, sz));
5.3.使用placeholders名字
名字_n都定义在一个名为placeholders的命名空间中，而这个命名空间本身定义在std命名空间中。为了使用这些名字，两个命名空间都要写上。与其他例子类似，对bind的调用代码假定之前已经恰当地使用了using声明。例如，_1对应的using声明为：
1
using std::placeholders::_1;
此声明说明我们要使用的名字_1定义在命名空间placeholders中，而此命名空间又定义在命名空间std中。
对每个占位符名字，我们都必须提供一个单独的using声明。编写这样的声明很烦人，也很容易出错。可以使用另外一种不同形式的using语句（后续博文会有更详细的介绍），而不是分别声明每个占位符，如下所示：
1
using namespace namespace_name;
这种形式说明希望所有来自namespace_name的名字都可以在我们的程序中直接使用。例如：
1
using namespace std::placeholders;
使得由placeholders定义的所有名字都可用。与bind函数一样，placeholders命名空间也定义在functional头文件中。
5.4.bind的参数
如前文所述，我们可以用bind修正参数的值。更一般的，可以用bind绑定给定可调用对象中的参数或重新安排其顺序。例如，假定f是一个可调用对象，它有5个参数，则下面对bind的调用：
1
2
//g是一个有两个参数的可调用对象
auto g = bind(f, a, b, _2, c, _1);
生成一个新的可调用对象，它有两个参数，分别用占位符_2和_1表示。这个新的可调用对象将它自己的参数作为第三个和第五个参数传递给f。f的第一个、第二个和第四个参数分别被绑定到给定的值a、b和c上。
传递给g的参数按位置绑定到占位符。即，第一个参数绑定到_1，第二个参数绑定到_2。因此，当我们调用g时，其第一个参数将被传递给f作为最后一个参数，第二个参数将被传递给f作为第三个参数。实际上，这个bind调用会将
1
g(_1, _2)
映射为
1
f(a, b, _2, c, _1)
即，对g的调用会调用f，用g的参数代替占位符，再加上绑定的参数a、b和c。例如，调用g(X, Y)会调用
1
f(a, b, Y, c, X)
5.5.用bind重排参数顺序
下面是用bind重排参数顺序的一个具体例子，我们可以用bind颠倒isShorter的含义：
1
2
3
4
//按单词长度由短至长排序
sort(words.begin(), words.end(), isShorter);
//按单词长度由长至短排序
sort(words.begin(), words.end(), bind(isShorter, _2, _1));
5.6.绑定引用参数
默认情况下，bind的那些不是占位符的参数被拷贝到bind返回的可调用对象中。但是，与lambda类似，有时对有些绑定的参数我们希望以引用方式传递，或是要绑定参数的类型无法拷贝。
例如，为了替换一个引用方式捕获ostream的lambda：
1
2
3
4
//os是一个局部变量，引用一个输出流
//c是一个局部变量，类型为char
for_each(words.begin(), words.end(),
[&os, c] (const string &s) { os << s << c; });
可以很容易地编写一个函数，完成相同的工作：
1
2
3
4
ostream &print(ostream &os, const string &s, char c)
{
return os << s << c;
}
但是，不能直接用bind来代替对os的捕获：
1
2
//错误：不能拷贝os
for_each(words.begin(), words.end(), bind(print, os, _1, ' '));
原因在于bind拷贝其参数，而我们不能拷贝一个ostream。如果我们希望传递给bind一个对象而又不拷贝它，就必须使用标准库ref函数：
1
2
for_each(words.begin(), words.end(),
bind(print, ref(os), _1, ' '));
函数ref返回一个对象，包含给定的引用，此对象是可以拷贝的。标准库中还有一个cref函数，生成一个保存const引用的类。与bind一样，函数ref和cref也定义在头文件functional中。
向后兼容：参数绑定
旧版本C++提供的绑定函数参数的语言特性限制更多，也更复杂。标准库定义了两个分别名为bind1st和bind2nd的函数。类似bind，这两个函数接受一个函数作为参数，生成一个新的可调用对象，该对象调用给定函数，并将绑定的参数传递给它。但是，这些函数分别只能绑定第一个或第二个参数。由于这些函数局限太强，在C++11中已被弃用（deprecated）。所谓被弃用的特性就是在新版本中不再支持的特性。新的C++程序应该使用bind。
