[C++]C++Primer Chapter 10

泛型算法

10.1 概述

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

一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围（参见9.2.1节，第296页）来进行操作。

迭代器令算法不依赖于容器，但算法依赖于元素类型的操作

关键概念：算法永远不会执行容器的操作

算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素。

10.2 初识泛型算法

10.2.1 只读算法

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

find就是这样一种算法，我们在10.1节练习（第337页）中使用的count函数也是如此。另一个只读算法是accumulate，它定义在头文件numeric中。accumulate函数接受三个参数，前两个指出了需要求和的元素的范围，第三个参数是和的初值。accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型。

算法和元素类型

对于只读取而不改变元素的算法，通常最好使用cbegin（）和cend（）（参见9.2.3节，第298页）。但是，如果你计划使用算法返回的迭代器来改变元素的值，就需要使用begin（）和end（）的结果作为参数。

操作两个序列的算法

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

那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。

10.2.2 写容器元素的算法

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

算法不检查写操作

函数fill_n接受一个单迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定个元素。我们可以用fill_n将一个新值赋予vector中的元素。函数fill_n假定写入指定个元素是安全的。

介绍back_inserter

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

我们现在将使用back_inserter，它是定义在头文件iterator中的一个函数。

back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中

拷贝算法

拷贝（copy）算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。

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

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

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

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

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

10.2.3 重排容器元素的算法

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

消除重复单词

为了消除重复单词，首先将vector排序，使得重复的单词都相邻出现。一旦vector排序完毕，我们就可以使用另一个称为unique的标准库算法来重排vector，使得不重复的元素出现在vector的开始部分。由于算法不能执行容器的操作，我们将使用vector的erase成员来完成真正的删除操作

使用unique

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

unique返回的迭代器指向最后一个不重复元素之后的位置。此位置之后的元素仍然存在，但我们不知道它们的值是什么。

使用容器操作删除元素

10.3 定制操作

10.3.1 向算法传递函数

为了按长度重排vector，我们将使用sort的第二个版本，此版本是重载过的，它接受第三个参数，此参数是一个谓词（predicate）。

谓词

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

接受一个二元谓词参数的sort版本用这个谓词代替<来比较元素。我们提供给sort的谓词必须满足将在11.2.2节（第378页）中所介绍的条件。

排序算法

为了保持相同长度的单词按字典序排列，可以使用stable_sort算法。这种稳定排序算法维持相等元素的原有顺序。

标准库定义了名为partition的算法，它接受一个谓词，对容器内容进行划分，使得谓词为true的值会排在容器的前半部分，而使谓词为false的值会排在后半部分。算法返回一个迭代器，指向最后一个使谓词为true的元素之后的位置。

10.3.2 lambda表达式

我们可以使用标准库find_if算法来查找第一个具有特定大小的元素。类似find（参见10.1节，第336页），find_if算法接受一对迭代器，表示一个范围。但与find不同的是，find_if的第三个参数是一个谓词。find_if算法对输入序列中的每个元素调用给定的这个谓词。它返回第一个使谓词返回非0值的元素，如果不存在这样的元素，则返回尾迭代器。

find_if接受一元谓词——我们传递给find_if的任何函数都必须严格接受一个参数，以便能用来自输入序列的一个元素调用它。没有任何办法能传递给它第二个参数来表示长度。为了解决此问题，需要使用另外一些语言特性。

介绍lambda

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

我们使用过的仅有的两种可调用对象是函数和函数指针（参见6.7节，第221页）。还有其他两种可调用对象：重载了函数调用运算符的类，我们将在14.8节（第506页）介绍，以及lambda表达式（lambda expression）。

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

capture list（捕获列表）是一个lambda所在函数中定义的局部变量的列表（通常为空）；return type、parameter list和function body与任何普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同，lambda必须使用尾置返回（参见6.3.3节，第206页）来指定返回类型。我们可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体

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

向lambda传递参数

lambda不能有默认参数（参见6.5.1节，第211页）。

使用捕获列表

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

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

for_each算法

此算法接受一个可调用对象，并对输入序列中每个元素调用此对象

一个lambda可以直接使用定义在当前函数之外的名字。

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

10.3.3 lambda捕获和返回

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

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

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

值捕获

与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝

由于被捕获变量的值是在lambda创建时拷贝，因此随后对其修改不会影响到lambda内对应的值。

引用捕获

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

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

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

一般来说，我们应该尽量减少捕获的数据量，来避免潜在的捕获导致的问题。而且，如果可能的话，应该避免捕获指针或引用。

隐式捕获

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

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

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

当混合使用隐式捕获和显式捕获时，显式捕获的变量必须使用与隐式捕获不同的方式。

可变lambda

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

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

指定lambda返回类型

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

当我们需要为一个lambda定义返回类型时，必须使用尾置返回类型（参见6.3.3节，第206页）

10.3.4 参数绑定

如果lambda的捕获列表为空，通常可以用函数来代替它。

但是，对于捕获局部变量的lambda，用函数来替换它就不是那么容易了。

标准库bind函数

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

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

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

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

使用placeholders名字

名字_n都定义在一个名为placeholders的命名空间中，而这个命名空间本身定义在std命名空间（参见3.1节，第74页）中。为了使用这些名字，两个命名空间都要写上。

bind的参数

我们可以用bind修正参数的值。更一般的，可以用bind绑定给定可调用对象中的参数或重新安排其顺序。

例如，假定f是一个可调用对象，它有5个参数，则下面对bind的调用

生成一个新的可调用对象，它有两个参数，分别用占位符_2和_1表示。这个新的可调用对象将它自己的参数作为第三个和第五个参数传递给f。f的第一个、第二个和第四个参数分别被绑定到给定的值a、b和c上。传递给g的参数按位置绑定到占位符。即，第一个参数绑定到_1，第二个参数绑定到_2。因此，当我们调用g时，其第一个参数将被传递给f作为最后一个参数，第二个参数将被传递给f作为第三个参数。

用bind重排参数顺序

绑定引用参数

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

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

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

10.4 再探迭代器

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

• 插入迭代器（insert iterator）：这些迭代器被绑定到一个容器上，可用来向容器插入元素。
• 流迭代器（stream iterator）：这些迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流。
• 反向迭代器（reverse iterator）：这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
• 移动迭代器（move iterator）：这些专用的迭代器不是拷贝其中的元素，而是移动它们。我们将在13.6.2节（第480页）介绍移动迭代器。

10.4.1 插入迭代器

插入器是一种迭代器适配器（参见9.6节，第329页），它接受一个容器，生成一个迭代器，能实现向给定容器添加元素。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素。

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

• back_inserter（参见10.2.2节，第341页）创建一个使用push_back的迭代器
• front_inserter创建一个使用push_front的迭代器。
• inserter创建一个使用insert的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

只有在容器支持push_front的情况下，我们才可以使用front_inserter。类似的，只有在容器支持push_back的情况下，我们才能使用back_inserter。

当调用inserter（c，iter）时，我们得到一个迭代器，接下来使用它时，会将元素插入到iter原来所指向的元素之前的位置。即，如果it是由inserter生成的迭代器，则下面这样的赋值语句

其效果与下面代码一样

front_inserter生成的迭代器的行为与inserter生成的迭代器完全不一样。当我们使用front_inserter时，元素总是插入到容器第一个元素之前。

10.4.2 iostream迭代器

istream_iterator（参见表10.3）读取输入流，ostream_iterator（参见表10.4节，第361页）向一个输出流写数据。这些迭代器将它们对应的流当作一个特定类型的元素序列来处理。通过使用流迭代器，我们可以用泛型算法从流对象读取数据以及向其写入数据。

istream_iterator操作

当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。

一个istream_iterator使用>>来读取流。因此，istream_iterator要读取的类型必须定义了输入运算符。当创建一个istream_iterator时，我们可以将它绑定到一个流。当然，我们还可以默认初始化迭代器，这样就创建了一个可以当作尾后值使用的迭代器。

下面是一个用istream_iterator从标准输入读取数据，存入一个vector的例子：

此循环从cin读取int值，保存在vec中。在每个循环步中，循环体代码检查in_iter是否等于eof。eof被定义为空的istream_iterator，从而可以当作尾后迭代器来使用。对于一个绑定到流的迭代器，一旦其关联的流遇到文件尾或遇到IO错误，迭代器的值就与尾后迭代器相等。

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

这个构造函数从cin中读取数据，直至遇到文件尾或者遇到一个不是int的数据为止。

使用算法操作流迭代器

由于算法使用迭代器操作来处理数据，而流迭代器又至少支持某些迭代器操作，因此我们至少可以用某些算法来操作流迭代器。我们在10.5.1节（第365页）会看到如何分辨哪些算法可以用于流迭代器。

istream_iterator允许使用懒惰求值

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

ostream_iterator操作

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

out_iter++实际不对迭代器做任何操作，但还是推荐第一种形式。在这种写法中，流迭代器的使用与其他迭代器的使用保持一致。如果想将此循环改为操作其他迭代器类型，修改起来非常容易。而且，对于读者来说，此循环的行为也更为清晰。

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

使用流迭代器处理类类型

10.4.3 反向迭代器

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

除了forward_list之外，其他容器都支持反向迭代器。

我们可以通过调用rbegin、rend、crbegin和crend成员函数来获得反向迭代器。

虽然颠倒递增和递减运算符的含义可能看起来令人混淆，但这样做使我们可以用算法透明地向前或向后处理容器。例如，可以通过向sort传递一对反向迭代器来将vector整理为递减序：

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

流迭代器不支持递减运算，因为不可能在一个流中反向移动。因此，不可能从一个forward_list或一个流迭代器创建反向迭代器。

反向迭代器和其他迭代器间的关系

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

10.5 泛型算法结构

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

第二种算法分类的方式（如我们在本章开始所做的）是按照是否读、写或是重排序列中的元素来分类。附录A按这种分类方法列出了所有算法。

10.5.1 5类迭代器

迭代器类别

1.输入迭代器（input iterator）：可以读取序列中的元素。

一个输入迭代器必须支持:

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

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

2.输出迭代器（output iterator）：可以看作输入迭代器功能上的补集——只写而不读元素。

输出迭代器必须支持

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

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

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

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

5.随机访问迭代器（random-access iterator）：提供在常量时间内访问序列中任意元素的能力。此类迭代器支持双向迭代器的所有功能，此外还支持表3.7（第99页）中的操作：

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

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

10.5.2 算法形参模式

大多数算法具有如下4种形式之一：

接受单个目标迭代器的算法

dest参数是一个表示算法可以写入的目的位置的迭代器。算法假定（assume）：按其需要写入数据，不管写入多少个元素都是安全的。

接受第二个输入序列的算法

接受单独的beg2或是接受beg2和end2的算法用这些迭代器表示第二个输入范围。这些算法通常使用第二个范围中的元素与第一个输入范围结合来进行一些运算。

10.5.3 算法命名规范

算法还遵循一套命名和重载规范。这些规范处理诸如：如何提供一个操作代替默认的<或==运算符以及算法是将输出数据写入输入序列还是一个分离的目的位置等问题。

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

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

_if版本的算法

接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词（参见10.3.1节，第344页）代替元素值。接受谓词参数的算法都有附加的_if前缀：

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

默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。如我们所见，写到额外目的空间的算法都在名字后面附加一个_copy（参见10.2.2节，第341页）：

一些算法同时提供_copy和_if版本。这些版本接受一个目的位置迭代器和一个谓词：

10.6 特定容器算法

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

splice成员

此算法是链表数据结构所特有的，因此不需要通用版本。

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

链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器。例如，remove的链表版本会删除指定的元素。unique的链表版本会删除第二个和后继的重复元素。

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