标准库容器的定义操作集合很小，但是标准库提供了一组独立于特定容器的算法，他们是泛型的，可用于不同类型的容器和不同类型的元素

概述

大多数标准库算法都定义在头文件algorithm中

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

• 虽然迭代器的使用令算法不依赖于容器类型，但大多数算法都使用了一个（或多个）元素类型上的操作。

  例如，在步骤2中， find 用元素类型的 == 运算符完成每个元素与给定值的比较。而其他算法可能要求元素类型支持 < 运算符。不过，在后面将会看到，大多数算法提供了一种方法，允许程序员使用自定义的操作来代替默认的运算符。

定制操作及lambda

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

向算法传递函数

作为一个例子，假定希望在调用elimDups（参见10.2.3）后打印 vector 的内容。此外还假定希望单词按其长度排序，大小相同的再按字典序排列。为了按长度重排 vector ，将使用 sort 的第二个版本，此版本是重载过的，它接受第三个参数，此参数是一个 谓词（predicate）。

• 谓词

  谓词是一个返回bool值的函数或者仿函数，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：

  1. 一元谓词 （unary predicate，意味着它们只接受单一参数）
  2. 二元谓词 （binary predicate，意味着它们有两个参数）

接受一个二元谓词参数的 sort 版本用这个谓词代替 < 来比较元素，当前只需知道，此操作必须在输入序列中所有可能的元素值上定义一个一致的序：

1
2
3
4
5
6

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

lambda

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

举例：

1
2
3
4
5

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

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

重点： 一个 lambda 表达式的捕获从 lambda 被定义（即，定义 lambda 的代码执行时）到 lambda 自身执行（可能有多次执行）这段时间内保存的相关信息。确保 lambda 每次执行的时候捕获的这些信息都有预期的意义，是程序员的责任。
① 捕获一个普通变量，如 int 、 string 或其他非指针类型，通常可以采用简单的值捕获方式。 ——在此情况下，只需关注变量在捕获时是否有所需的值就可以了。
② 如果程序员捕获一个指针或迭代器，或采用引用捕获方式 ，就必须确保在 lambda 执行时，绑定到迭代器、指针或引用的对象仍然存在。而且，还需要保证对象具有预期的值。——如果捕获了指针或迭代器，或是采用引用捕获方式，则在 lambda 从创建到它执行的这段时间内，可能有代码改变绑定的对象的值。也就是说，在指针（或引用）被捕获的时刻，绑定的对象的值是所期望的，但在 lambda 执行时，该对象的值可能已经完全不同了。
一般来说，程序员应该尽量减少捕获的数据量，来避免潜在的捕获导致的问题。而且，如果可能的话，应该避免捕获指针、迭代器或引用。

隐式捕获

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

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

1
2
3
4
5
6
7
8
9
10

void biggies(vector<string> &words, vector<string>::size_type sz, ostream &os = cout, char c = ' ')
{
    // 其它代码如前面的biggies一样
    // c为显式的值捕获，其他的所有变量（os）为隐式的引用捕获
    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 不会改变其值。如果程序员希望能改变一个值捕获的变量的值，就必须在参数列表和函数体中间添加 关键字 mutable 。因此，可变（ 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
}

其他

_if 版本的标准库算法

接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词代替元素值。一般情况，如果算法本身和另一个接受谓词参数的版本都接受相同数目的参数，则接受谓词参数的算法会有附加的 _if 后缀：

1
2

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