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

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

1 向算法传递函数

作为一个例子，假定希望在调用elimDups后打印vector的内容。此外还假定希望单词按其长度排序，大小相同的再按字典序排列。为了按长度排序vector，我们将使用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算法。这种稳定排序算法维持相等元素的原有顺序。

通常情况下，我们不关心有序序列中相等元素的相对顺序，它们毕竟是相等的。通过调用stable_sort，可以保持等长元素间的字典序：

elimDups(words);//将words按字典序重排，并消除重复单词

//按长度重新排序，长度相同的单词维持字典序

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

for(const auto &s:words)

　　cout<<s<<" ";

cout<<endl;

2 lambda表达式

根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。例如，我们求大于等于一个给定长度的单词有多少。并且只打印打印等于给定长度的单词。

我们将此函数命名为biggies，其框架如下所示：

void biggies(vector<string> &words,vector<string>::size_type sz)

{

    elimDups(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的任何函数都必须接受一个参数，以便能用来自输入序列的一个元素调用它。没有任何办法能传递给它第二个参数来表示长度。为了解决此问题，需要使用另外一些语言的特性。

介绍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。

向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表达式。

使用捕获列表

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

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

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

[sz] (const string &s)

　　{return s.size()>=sz;};

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

由于此lambda捕获sz，因此lambda的函数体可以使用sz。lambda不捕获words，因此不能访问此变量。如果我们给lambda提供了一个空捕获列表，则代码会编译错误：

//错误：sz未捕获

[] (const string &s);

　　{ return s.size()>=sz;};

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

调用find_if

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

//获取一个迭代器，指向第一个满足size()>=sz的元素

auto wc=find_if(words.begin(),words.end(),

　　　　　　　[sz] (const string &s)

　　　　　　　　{return s.size()>=sz;});

这里对find_if的调用返回一个迭代器，指向第一个长度不小于给定参数sz的元素。如果这样的元素不存在，则返回words.end()的一个拷贝。

我们可以使用find_if返回的迭代器来计算从它开始到words的末尾一共有多少个元素：

//计算满足size>=sz的元素的数目

auto count=words.end() -wc;

for_each算法

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

//打印长度大于等于给定值的单词，每个单词后面接一个空格

for_each(wc,words.end(),

　　[](const string &s) {cout<<s<<" ";});

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

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

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

3 lambda捕获和返回

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

默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员类似任何普通类的数据成员，lambda的数据成员也在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创建时拷贝，因此随后对其修改不会影响到lambda内对应的值。

引用捕获

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

void fcn2()

{

　　size_t v1=42;

　　//对象f2包含v1的引用

　　auto f2=[&v1] { return v1;};

　　v1=0;

　　auto j=f2();  //j为0；f2保存v1的引用，而非拷贝

}

v1之前的&指出v1应该以引用方式捕获。一个以引用方式捕获的变量与其他任何类型的引用的行为类似。当我们在lambda函数体内使用此变量时，实际上使用的是引用所绑定的对象。在本例中，当lambda返回v1时，它返回的是v1指向的对象的值。

引用捕获与返回引用有着相同的问题和限制。如果我们采用引用方式捕获一个变量，就必须确保被引用的对象在lambda执行的时候是存在的。lambda捕获的都是局部变量，这些变量在函数结束后就不复存在了。如果lambda可能在函数结束后执行，捕获的引用指向的局部变量已经消失。

引用捕获有时是必要的。例如，我们可能希望biggies函数接受一个ostream的引用，用来输出数据，并接受一个字符作为分隔符：

void biggies(vector<string> &words,vector<string>::size_type sz,ostream &os=cout,char c=' ')

{

　　//下面打印count的语句改为打印到os

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

}

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

当我们向一个函数传递一个lambda时，就像本例中调用for_each那样，lambda会立即执行。在此情况下，以引用方式捕获os没有问题，因为当for_each执行时，biggies中的变量是存在的。

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

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

隐式捕获

除了显式列出我们希望使用的来自所在函数的变量外，还可以让编译器根据lambda体中的代码来推断我们要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个&或=。&告诉编译器采用捕获引用方式。例如，我们可以重写传递给find_if的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;});

}

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

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

可变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

}

指定lambda返回类型

到目前为止，我们所编写的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语句，返回一个条件表达式的结果。我们无须指定返回类型，因为可以根据条件运算符的类型推断出来。

但是，如果我们将程序改写为看起来是等价的if语句，就会产生编译错误：

//错误：不能推断lambda的返回类型

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

在此例中，传递给transform的第四个参数是一个lambda，它的捕获列表是空的，接受单一int参数，返回一个int值。它的函数体是一个返回其参数的绝对值的if语句。