泛型算法

C++ Primer 笔记第十章

泛型算法（Generic Algorithms）是标准库提供的一系列的算法。与之前学到的针对于特定容器的操作相比，泛型算法有几个特点：

不限定类型：可以应用到不同容器甚至 build-in 类型上
主要使用迭代器操作
实现的主要是算法的内容，比如排序、寻找等等

概述

泛型算法主要定义在两个头文件中：

<algorithm> 定义了绝大部分算法。
<numeric> 定义了一系列数值计算的算法。

泛型算法并不直接操作目标，而是主要通过维护两个迭代器（一首一尾）来进行对目标的遍历。比如使用 find 搜寻某个 vector 中的指定元素：

int val = 42; // value we'll look for
// result will denote the element we want if it's in vec, or vec.cend() if not
auto result = find(vec.cbegin(), vec.cend(), val);

find 通过两个迭代器确定搜寻的范围，再通过 val 来确定要匹配的值，然后返回一个结果。由于操作的对象是迭代器，find 也可以用到别的容器上，比如 list：

string val = "a value"; // value we'll look for
// this call to find looks through string elements in a list
auto result = find(lst.cbegin(), lst.cend(), val);

由于在 build-in array 中也可以通过 begin() 和 end() 函数实现类似于迭代器的功能，因此 find 也可以应用于 build-in array：

int ia[] = {27, 210, 12, 47, 109, 83};
int val = 83;
int* result = find(begin(ia), end(ia), val);

泛型算法如何工作

泛型算法通过迭代器进行操作。比如之前的 find 的一个简单流程：

访问第一个元素
与目标值比较，如果匹配返回值说明找到，否则接着进行寻找
如最终未能找到，返回指定值说明没有找到

我们发现这整个过程都没有任何与容器相关的操作。因此，只要是能使用迭代器访问元素的地方，find 就不需要依赖容器类型。

算法、容器和迭代器的关系

尽管泛型算法不依赖于容器，但是依赖于容器元素类型的操作。比如刚才 find 中比较元素的步骤，就必须根据元素指定的比较法则来进行。

这意味着绝大多数的算法并没有对容器的直接操作；换句话说，泛型算法可能会改变容器元素的值，或者交换元素的位置，但不会更改容器本身的大小（不会直接做添删类操作）。

初识泛型算法

C++ 标准库中至少包含了 100 多种泛型算法。从体系上来看，绝大多数算法都是对一个“范围” 内的元素进行操作，而该范围一定是使用迭代器来表示。而真正体现算法差异性的是算法的内容。根据内容的不同，泛型算法可以分为三类：

只读算法
读/写算法
元素重排序算法

只读算法

只读算法（Read-Only Algorithms）指读取但不会改变元素的算法。

只读算法：accumulate

accumulate 是一种常见的只读算法。该算法计算并返回指定范围的元素之和。该算法总共获取三个参数：

accumulate(vec.cbegin(), vec.cend(), 0);

迭代器表示范围，第三个参数表示累加的起始值。需要注意的是，由于第三个参数参与了累加，因此隐含了两个条件：

返回内的元素需要与第三个参数的类型必须相同，或是可以转化
用于累积的元素定义了加法（可以相加）

基于这样的条件来判断，带有 string 的容器也能使用 accumulate：

string sum = accumulate(v.cbegin(), v.cend(), string(""));

算法严格遵循这样的一致性。一个反例就是上例不能使用 literial 空字符串作为起始值，因为 const char* 类型并没有定义加法：

string sum = accumulate(v.cbegin(), v.cend(), "");

除了需要使用算法返回的迭代器改变元素值的情况，只读算法都应该使用 cbegin() 与 cend() 表示范围。

只读算法：equal

equal 是一种应用于两个序列的算法，用与比较连个序列是否相等。equal 获取的 parameter 为三个迭代器：前两个迭代器表示第一个序列的范围，第三个迭代器表示第二个序列的起始点：

// roster2 should have at least as many elements as roster1
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

equal 通过对两个序列每个位置的对应元素进行比较来得出结果。其返回值为 bool，序列相等则返回 true ，反之则为 false。根据算法的特性，只要是可以进行 == 运算的元素序列，都可以使用 equal 进行比较。更详细的来说：

equal 可以比较不同类型的元素序列
equal 可以比较不同长度的元素序列

需要注意的是，由于 equal 算法从设计上来说需要查看第一个序列的所有元素，因此 equal 假定第二个序列的长度不小于第一个序列的长度。

写算法

写算法是 STL 中提供的，用于修改元素内容的算法。该类算法有个非常重要的使用前提：确保被修改的容器足够大到装下算法需要修改的元素个数。

具体的来说，写算法大概分为三种：

修改自身容器，即只接受一对迭代器。这种操作是安全的，因为可写的元素总是在范围内。
使用一个序列修改另外一个序列：这种情况又可以细分为两种：
- 接收三个迭代器的情况。头两个表示第一个序列的范围，第三个表示第二个序列的开头位置。这种情况下，算法会假定第二个序列的长度大于等于第一个序列；也就是我们必须确定第二序列足够的容量供修改。
- 接收四个迭代器的情况：两个表示第一序列的范围，两个表示第二序列的范围。

写算法：fill & fill_n

fill 是一种常见的写算法，其所用是将范围类的元素全替换为指定值。它接收三个参数，前两个确定元素的范围，第三个数为指定值：

fill(vec.begin(), vec.end(), 0); // reset each element to 0

fill 属于之前提到的修改当前序列本身的算法，因此操作是确认安全的。不过即便如此，我们也应该谨记算法不会检查写操作这个事实。 fiil 算法的另外一个变种 fill_n，使用迭代器 + 容器大小的形式表示输入范围；在这种情况下是需要用户来保证输入范围的合法性的：

fill_n(vec.begin(), vec.size(), 0);

vec.size() 在这里就是一个安全的值。但如果像下面这样的写就有问题了：

vector<int> vec; // empty vector
// disaster: attempts to write to ten (nonexistent) elements in vec
fill_n(vec.begin(), 10, 0);

总之需要谨记的是，算法不会检查容器本身，它只会假定容器具有写入的资格（足够大，并且可以容纳指定类型的元素）

确保被写容器拥有足够空间的手段：back_inserter

我们可以用 inserter 类型的迭代器来来确保容器拥有足够的空间。与一般的迭代器不同，inserter 是一种用来添加元素到容器的迭代器。该类迭代器都定义在 <iterator> 头文件里面，以如下的方式向容器中添加元素：

将迭代器绑定至容器中需要添加元素的位置
向该迭代器指向的位置进行赋值

back_inserter 是 insert_iterator 的一种。它的作用是：

获取容器的引用
返回一个绑定到该容器的迭代器
调用 push_back() 为该容器添加新元素

vector<int> vec;
auto it = back_inserter(vec);
*it = 42;

该种类型的迭代器可以与写算法一起连用，达到循环新建容器元素并写入的效果：

vector<int> vec;
fill_n(back_inserter(vec), 10, 0); //append 10 '0' to the end of vec

写算法：copy & replace

copy 是另一种常见的写算法，其功能是将源序列的内容复制到目标序列中。其接收三个迭代器（源序列范围 + 目标序列起始点），因此需要确保目标序列的容量足够大：

int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)]; // a2 has the same size as a1
// ret points just past the last element copied into a2
auto ret = copy(begin(a1), end(a1), a2); // copy a1 into a2

copy 会返回一个迭代器，该迭代器指向复制结果的 off-the-end 位置，比如上例 ret 的值就是 a2 中最后一个元素的下一个位置。

除此之外，其他某些算法也提供类似 copy 的功能，比如 replace，其功能是将指定范围内中的某个值替换为指定值：

// replace any element with the value 0 with 42
replace(ilst.begin(), ilst.end(), 0, 42);

如果不想修改源序列的值，可以使用另外一个版本 replace_copy()。该算法会将替换的结果复制到一个新的容器中：

// use back_inserter to grow destination as needed
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

这里使用了 back_inserter() 将复制的内容添加到 ivec 中。

排序算法

排序算法指改变容器内元素顺序的算法。

排序算法：sort() & unique()

常用的对容器元素排序的算法有：sort(), unique()。

sort() 实现了什么功能？如何使用？

sort() 接收两个表示范围的迭代器，对范围内的元素按照 < 操作来排序（越小的越靠前）：

sort(words.begin(), words.end());

unique() 实现了什么功能？如何使用？

unique() 接收两个表示范围的迭代器，返回一个迭代器：

unique(words.begin(), words.end());

其机制稍微有些复杂：

首先，其目的是移除重复的元素，创造一个不重复元素的序列
其次，由于泛型算法的限制，unique() 使用了移动元素的方式来达到移除重复元素的效果。具体的实现办法就是将重复的元素都往序列最后的位置放；当确定了不重复序列时，返回一个指向该序列末位元素下一位的， “off-the-end” 迭代器。需要注意的是，重复的元素并没有被删除，只是从逻辑上来说他们已经不属于当前队列了。
再次，unique() 移除重复元素的前提必须是范围内相邻的重复元素（every consecutive group of equivalent elements）。

可以看出 unique() 本身具有一定的局限性。比如想实现消除一个无序字符串序列里的重复元素，必须配合 sort() 和容器本身的 erase() 成员使用：

首先通过排序，重复的元素会变得相邻。
其次通过 unique 将重复的元素全移到末尾，并使用返回的 “off-the-end” 迭代器作为分界线，指定需要物理上删除的重复元素范围。
最后通过 earse() 真正删除上述范围的元素。

<html>

</html>
写成代码就是：

vector<string> words; 
sort(words.begin(), words.end(); //sorting
end_unique = unique(words,begin(), words.end()); //move the dupilicated words to the end of the container, return a "boundary" sign 
words.erase(end_unique, words.end()); //use the sign to establish the range of the dupilicated elements, remove all of them in the range.

这种情况下，即使序列中一开始就没有重复元素（即 unique() 直接返回 word.end() 迭代器），earse 操作也是安全的，因为删除空范围是被允许的，不会造成任何影响。

为算法定制比较策略

某些比较算法采用默认的策略对元素进行比较，比如 == 或 < 这样的运算符。但某些情况下，由于元素不支持此类运算符（比如类元素），我们需要自行定制比较的策略。C++ 通过提供对应算法的特殊版本来解决这个问题。

方式1：传递函数给算法

这种特殊的版本以传递函数的方式 将定制的比较策略应用到算法中，其中函数即为我们制定的策略。以 sort() 为例。通常情况下, sort() 只拥有两个迭代器参数。而 sort() 的特殊版本则提供了第三个参数，我们称之为谓词（predicates）。谓词如下的特性使其在这里实际上作为了定制策略的载体：

它是一个表达式（可以是函数）
它可以被算法调用
它接收元素作为 argument（算法调用它对元素进行比较）

因此整个流程可以描述为：

谓词装载定制的函数
该函数接收元素作为 argument
算法通过调用该函数完成定制策略下元素的比较：

<html>

</html>

比如 sort()，如果我们想通过比较 string 元素长度的方式来比较大小，那么规则函数可以定义为：

bool isShorter(const string &s1, const string &s2) {
    return s1.size() < s2.size();
}

接着直接通过带谓词的算法版本调用则可使用该规则完成排序：

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

这里有两点需要注意：

谓词可以接收的 parameter 是 1-2 个，parameter 的数量被称为元，即接收单个 parameter 的谓词被称为一元谓词（unary predicate），接收两个 parameter 的谓词被称为二元谓词（binary predicate）。
由于谓词接收元素作为 argument，因此元素的类型与谓词中函数 parameter 的类型需要匹配。

实例：谓词配合 stable_sort() 排序

上例中，通过比较 string 长度得出来的结果很可能看起来不那么直观，因为规则只比较 string 的长度，因此长度相同的 string 会被无序的放在一起。如果希望结果看起来更直观，可以使用 stable_sort() 进行排序。对于长度相等的 string 元素, stable_sort() 根据其开头字母，以字母表（alphabet）的顺序来进行排列。其用法与 sort() 相同：

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

方式2：Lambda 表达式

根据书中的实例：需要实现一个 biggies() 函数：该函数需要对所有长度大于 sz 的元素进行排序并输出：

void biggies(vector<string> &words,
             vector<string>::size_type sz)
{
    elimDups(words); // put words in alphabetical order and remove duplicates
    // resort by length, maintaining alphabetical order among words of the same length
    stable_sort(words.begin(), words.end(), isShorter);
    // get an iterator to the first element whose size() is >= sz
    // compute the number of elements with size >= sz
    // print words of the given size or longer, each one followed by a space
}

例子中的另外一个要求是希望该函数可以作为自定义的策略提供给 find_if() 算法使用，用于定位所有满足条件 string 序列的头元素位置。

find_if 简介

find_if() 是一种排序算法。其功能是按指定条件对所有元素进行判断，并返回指向第一个满足条件元素的迭代器。通常情况下，该算法接收三个参数：一对表示范围的迭代器与一个一元谓词：

find_if (InputIterator first, InputIterator last, UnaryPredicate pred)

Lambda 的基本概念

Lambda 表达式以及相关背景

由于 find_if() 的谓词只能接收一个参数，因此拥有两个参数的 biggies() 不能直接作为自定义规则传递给该算法。C++ 提供了一个解决方案：Lambda 表达式，允许我们将拥有更多定制参数的规则传递给算法。有几个概念需要在了解 Lambda 之前熟悉一下：

算法可以接收的传递对象有什么特点？

总的来说，如果一个对象被称作可调用对象（callable object），那么它就是可以传递给算法的。

什么是可调用对象？

可调用对象是指可以对其使用调用运算符 () 的对象。该对象可以是对象，也可以是一个表达式。假设 e 是一个可调用的表达式，那么一个可调用的对象就可以表示为如下的形式：

e(argment_list);

加上本节的 Lambda 表达式，已知的可调用对象有四种：

函数
函数指针
Lambda 表达式
重载了 () 运算符的类对象

Lambda 表达式的组成与定义

和函数相似，Lambda 表达式也是由一系列代码组成的代码单元。我们可以将其理解为一个 inline 的、没有名字的函数。Lambda 表达式与函数有很多共同点：

有 parameter list 与返回值
有函数体

但与函数稍微不同的是， Lambda 可以（通常）定义于函数的内部。其定义写法也采用了尾置的形式：

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

其中：

Capture list 表示需要使用的函数局部变量（多用于规则函数的实参传递，与 Lambda处于同一个作用域）
Parameter list 与普通函数相同。当被算法调用的时候，该 List 接收指定范围内的元素作为 parameter 。() 可以省略，代表不接收任何 argument
Return type 与普通函数相同，但必须用 trailing return 的形式表示，可以省略
Function body 表示 Lamaba 表达式的内容。

需要注意的是，Capture list 与函数体在定义中是不能省略的。当位置的返回类型为空的时候，编译器通过函数体中的 return 语句来判断当前表达式的返回类型：

auto f = [] { return 42; } //f returns an int

但如果这种情况下函数体中语句不止一句，则表达式的返回类型为 void。

除此之外，调用 lambda 表达式的方式与普通函数相同：

cout << f() << endl; //print 42

向 Lambda 传递参数

lambda 表达式与普通函数接收 argument 的方式相同。唯一的区别是 lambda 表达式不能设置 default argument。因此 lambda 表达式接收的 argument 与自身的 parameter 永远相等。

之前见过的 is_shorter() ，与其功能完全一致的 lambda 如下所示：

[](const string& s1, const string& s2) { return s1.size() < s2.size(); }

而之前使用 string 长度排序的 stable_sort() 就可以写成：

stable_sort(word.begin(), word.end(), 
			[] (const string& s1, const string& s2) 
			{ return s1.size() < s2.size(); })

使用 Capture list

回到书中的例子。我们的目标是同时将上级函数 biggie() 的两个 parameter：一个 vector<string>& 类型的 word、与长度 sz 传递给算法 find_if() 使用。在这里，我们使用 lambda 的 Capture list 对其所在函数中的变量进行捕获。

捕获的意思是，当 lambda 想使用上级函数（enclosing function, or surrounding function）中的局部变量时，只需要将其添加到 [] 捕获列表中就可以：比如这里我们如果希望使用 sz，则对应的规则 lambda 可以写成：

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

Capture list 允许我们捕获多个局部变量用于使用，只需要用 comma 隔开即可。需要注意的是，Capture list 遵循捕获后才能使用的原则；如果其为空，则意味着 lambda 无法使用任何上级函数的局部变量。

lambda 与 find_if() 的连用

此时我们的 lambda 只有一个参数 s，因此满足 find_if() 需要一元谓词的条件。find_if() 会返回指向第一个满足条件元素的迭代器。该结果可以用与计算结果序列的长度，因此使用 wc 变量将其存储起来：

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

因为 word 是有序序列，使用 word.end() - wc 可以得到满足条件的序列有多长。使用之前定义的 make_plural() 函数可以对打印信息进行单双数的优化：

cout << count << " " << make_plural(count, "word", "s") 
	 << "of length" << sz << " or longer" << endl;

for_each() 简介

for_each() 算法接收一个可调用对象，并使用序列中的每个元素都调用该对象。我们可以将该对象设置为打印功能的 lambda，来输出指定序列中所有的内容：

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

需要注意的是：

只有上级函数中的局部变量，才需要捕获后使用。除此之外，lambda 可以随意使用外部名字，比如这里的 cout。
只有 non-static 的局部变量需要经过 Capture list 捕获才能使用。local static varible，及其在函数外部的名字均可以直接被 lambda使用。

整个的 biggies 函数

void biggies(vector<string> &words, vector<string>::size_type sz) {
	
	//duplicates removed, the sequence in alphabetical order
	
	elim_dups(words); 
	
	//sort words by size, maintain the alphabetical order for words of the same length
	
	stable_sort(words.begin(), words.end(), 
			   [](const string& s1, const string& s2)
			   { return s1.size() < s2.size(); });

	//get the sequence range of the elements that has length >= sz

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

	//print the additional info

	cout << count << " " << make_plural(count, "word", "s")
		 << " of length " << sz << " or longer " << endl;

	//print each element in the range

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

}

Lambda 的捕获与返回

在 lambda 被传递给算法的整个过程中，编译器主要做了两件事：

当 lambda 被定义的时候，编译器生成了一个新的（没有名字）的 class type，这个 class type 对应被定义的 lambda。
当传递 lambda 给算法时候，编译器创建了该 class type 的一个对象，并将该对象作为 argument 传递给算法。

捕获列表中的局部变量也是这个对象的一部分。根据参数的传递方式的不同，捕获列表中的变量也可以分为两种捕获方式：值捕获（Capture by value）与引用捕获（Calture by reference）。

值捕获

值捕获与值传递的方式一样，通过拷贝的方式传递参数；因此可以使用值捕获的变量必须能被拷贝。与函数不同的是，值捕获的变量在 lambda 被创建的时候就已经复制初始化完毕了，因此之后对原有变量的修改不会对 lambda 的捕获变量造成任何影响：

/* caputure by value: change v1 doesn't not affect the capture list. */
void fcn1()
{
	size_t v1 = 42; // local variable
	// copies v1 into the callable object named f
	auto f = [v1] { return v1; };
	v1 = 0;
	auto j = f(); // j is 42; f stored a copy of v1 when we created it
}

引用捕获

另外一种方式是引用捕获，捕获列表中的元素是上级函数中局部变量的引用。由于捕获的是引用，因此通过该引用改变绑定的局部变量也会影响到 lambda：

/* lambda captured a reference that refers to v1, changes v1 also changes the lambda.*/
void fcn2()
{
	size_t v1 = 42; // local variable
	// the object f2 contains a reference to v1
	auto f2 = [&v1] { return v1; };
	v1 = 0;
	auto j = f2(); // j is 0; f2 refers to v1; it doesn't store it
}

这种捕获方式也受传统引用传递方式规则的约束：

该引用遵循任何一般变量引用的规则
通过引用方式捕获的变量，在 lambda 执行的时候必须存在（特别需要注意上级函数的周期，因为引用的是局部变量）。

哪些情况下一定会用到引用捕获？

在传递某些不能被拷贝的参数的情况下。比如我们想使用 biggies() 函数传递一个 ostream 对象给算法，就必须要用到引用捕获：

void biggies(vector<string> &words, vector<string>::size_type size_type,
			 ostream& os = cout; char c = ' '){
	...
	//using fucntion parameter ostream and lambda to print
	for_each(words.begin(), words.end(), 
			[&os, c](const string& s) { os << s << c; };
	os << endl;
}

哪些情况下不能使用引用捕获？

在函数返回自身 lambda 的情况下。通常，lambda 会作为一个对象返回。而此时，捕获列表中的局部变量会作为对象成员一起返回。由于局部变量的生命周期只到函数结束前，如果通过引用捕获获取变量，那返回的就是指向不存在变量的引用，这显然是不能被允许的。

使用捕获列表的建议？

一个总的原则是，尽可能的保证一个简单的捕获列表。只有在捕获间接访问对象（引用，指针）的时候，我们才需要确保其存在性（引用与存在的值绑定）和正确性（引用不修改绑定的值）。因此如果可能，尽可能避免捕获间接访问对象。

隐藏捕获以及混用

lambda 可以在不将变量写入捕获列表的情况下，通过符号 = 或者 & 来指定对所有局部变量的捕获方式：

= 代表使用值捕获
& 代表使用引用捕获

如果需要特殊指定某些变量的捕获方式，可以将需要指定的变量与上述符号混用，中间用逗号隔开：

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

    // os implicitly captured by reference; c explicitly captured by value
    for_each(words.begin(), words.end(),
	    	    [&, c](const string &s) { os << s << c; });
    // os explicitly captured by reference; c implicitly captured by value
    for_each(words.begin(), words.end(),
		    [=, &os](const string &s) { os << s << c; });
}

混用时需要注意几点：

必须以符号 = 或 & 开头
列表中显式捕获的变量（逗号后的）必须形式上与隐式捕获的符号不同。比如以 = 开头，后面的变量必须标注引用符号；反之则不能标注。

Mutable Lambda

Mutable Lambda 只针对于值捕获，即捕获列表中的变量都是拷贝的情况。

在值捕获的情况下，lambda 默认不能修改捕获列表中的变量拷贝。如果希望修改，可以使用关键字 mutable 定义 lambda：

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

需要注意这种情况下是不能省略参数列表的（本例中的 ()）。

如果是引用捕获，那么是否能修改捕获的变量只与引用的变量类型有关系。如果引用的是 non-const 变量，那么就可以修改：

void fcn4() {
	size_t v1 = 42; // local variable
	// v1 is a reference to a non const variable
	// we can change that variable through the reference inside f2
	auto f2 = [&v1] { return ++v1; };
	v1 = 0;
	auto j = f2(); // j is 1
}

指定 Lambda 的返回类型

lambda 在没有显式指定返回类型，且函数体中不单有 return 语句的情况下，默认返回形式为 void。如果希望 lambda 返回期望的值，则必须显式指定返回类型：比如使用 transfrom() 对 vector 进行批量的修改。

先介绍一下 transform()。 transform() 是一种写算法。其作用是以可调用对象的结果替换目标序列中所有的元素。它接收 3 个迭代器与 1 个可调用对象：

头两个对象指代输入序列的范围
第三个迭代器指代源序列的起始点
可调用对象代表要实施的操作

下列例子中，我们希望使用 lambda 对 vi 中的元素求绝对值。由于 lambda 的函数体不止一个语句，因此必须显式的指定返回类型：

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

方法3：参数绑定

lambda 适合简单的规则；当需要大量重复使用规则，或是规则实现复杂时，函数是才是更好的选择。但当 lambda 使用捕获列表时，可传递的 parameter 并不受算法和谓词的限制；而函数本身无法替代该功能。

为了解决这个问题，C++ 提供了 bind() 函数。该函数定义于 <functional> 头文件中，其作用是适配函数的 parameter 数量（function apapter）。bind() 会接收一个可调用对象，以及其对应的 parameter，然后返回一个新的可调用对象供算法调用。这个新的对象通过适配后，其 parameter 就能满足算法的要求。

bind 与 placeholder

以 find_if() 为例。该算法只能接收一元谓词，如果传递函数作为规则，则函数只能有一个 parameter。假设我们有一个 check_size() 的函数如下：

bool check_size(const string &s, string::size_type sz) {
    return s.size() >= sz;
}

使用下面的写法可以得到一个新的函数 check()，该函数与 check_size() 功能相同，并且只有一个参数：

auto check6 = bind(check_size, _1, 6); //check(s) call check_size(s, 6);

bind() 是如何达到函数适配的效果的？

实际上，bind() 通过接收一个可调用对象和一个 argument list 来产生新的可调用对象：

auto newCallable = bind(callable, arg_list);

当调用 newCallable 的时候，我们实际上通过其调用了 callable，并将绑定的参数同时传递给了 callable。

同时，之前的例子中存在 _1 这样的参数。该参数被称为 Placeholder，用于将源函数的某个 parameter 与新函数对应的 parameter 绑定起来：比如我们希望在 check6() 中使用 check_size() 的 const string& s 参数，只需将 _1 添加到 bind() 参数列表中即可。

<html>

</html>

callable 中没有被绑定的参数 与 placeholder 绑定的参数共同组成 callable 的参数列表（arg_list），该部分将通过 bind() 一起传递给 newCallable 对象。比如上例中的 check6() 函数接受了两个参数，但自身的参数也只有被绑定的参数，也就是 s，作为了自身的 parameter：

string s = "hello";
bool b1 = check6(s);  // check6(s) calls check_size(s, 6)

比较一下这种写法与 lambda 的区别：

auto wc = find_if(words.begin(), words.end(),
            [sz](const string &a);
            
auto wc = find_if(words.begin(), words.end(),
             bind(check_size, _1, sz));

很明显，没有被绑定的参数可以被视作接受上级函数参数的载体，比如：

void biggies(vector<string> &words, vector<string>::size_type sz) {
    auto wc = find_if(words.begin(), words.end(),
             bind(check_size, _1, sz));
}

参数绑定与 arguments

需要注意的是，一旦确定 placeholder 的位置后，其与被适配对象和新产生对象中的 parameter 都会一一对应起来。利用 bind() 的这种功能，可以通过对 newCallable 中参数 (被绑定参数) 的重排序，来达到调整 callable 对象中被绑定参数位置的效果。比如 callable 对象为：

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

由于 placeholder 与 newCallable 对象 g() 中的对应关系是按编号来排列的，如果调用一个 g(X,Y) 的函数，实际上调用了：

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

如果我们希望通过 g(X,Y) 调用的 f() 如下：

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

那么需要替换 placeholder 在整个 argument list 中的位置即可：

// g is a callable object that takes two arguments
auto g = bind(f, a, b, _1, c, _2)；

<html>

</html>
可以总结出来的是：

newCallable 中：placeholder 使用编号与其参数对应，即 _1 对应第一个参数，以此类推
callable 中：placeholder 与其绑定参数的位置对应。比如上例中 f(a,b,X,c,Y)，如果将 X 与 Y 调换，那么对应的 placeholder 也需要调换位置。

使用 bind 对参数重新排序

在某些应用下，使用 bind() 重新安排参数顺序能达到改变函数本身功能的效果，比如：

// sort on word length, shortest to longest
sort(words.begin(), words.end(), isShorter);
// sort on word length, longest to shortest
sort(words.begin(), words.end(), bind(isShorter, _2, _1));

原本函数的功能是返回 A < B 的结果。经过 bind() 的参数交换后，函数定义的规则则变为了 B < A，也就是我们实际调用的是 isShorter(B, A)。

使用 placeholder 的前提

placeholder 定义于命名空间 placeholders 中。该命名空间定义于命名空间 std 中。因此，为了使用 placeholder，我们需要作出以下的声明：

using std::placeholders::_1;

如果有多个 placeholder 存在，可以直接声明其所在命名空间来简化书写：

using namespace std::placeholders;

这种写法可以允许我们使用 placeholders 空间中定义的所有名字。

绑定引用 parameters

lambda 通过捕获列表获取局部变量。bind() 中，对标捕获列表的变量是 argument list 中没有被绑定的变量；默认情况下，这些变量是通过拷贝的形式绑定到新函数中的。

而某些对象是一定要通过引用传递的，比如之前提到的 ostream 对象。lambda 通过引用捕获传递该对象：

//os is a local variable referring to an output stream
for_each(words.begin(), words.end(), [&os, c](const string &s) { os << s << c; });

如果我们希望在 bind 中以引用的形式传递该对象，那么需要使用库函数 ref():

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

该函数还有传递 reference to const 的版本 cref()。这两个函数都被定义在 <functional> 头文件中。

更早版本的 C++ 提供了 bind1st() 与 bind2rd() 两个函数实现绑定功能。由于其功能的局限性性（只能绑定第一个或者第二个参数），在 C++11 中已经被放弃了。现代 C++ 应该使用 bind() 替代。

再探迭代器

除了一般应用于容器的迭代器以外，STL 还额外定义了几种通用的迭代器：

插入迭代器（Inserter iterators）：绑定容器并实现对该容器的元素插入操作。
流迭代器（Stream iterators）：绑定 Stream 对象，并实现对该对象的遍历。
反向迭代器（Reverse iterators）：从右往左移动的迭代器，除了 forward_list 都有该类迭代器。
移动迭代器（Move iterrators）: 用移动元素取代拷贝元素的迭代器。

插入迭代器

插入迭代器拥有自身对应的函数适配器（Inserter adoptor）。这些适配器会接收一个容器对象，并返回对应的插入迭代器。元素的插入通过向插入迭代器进行赋值来进行，比如：

it = 222; //it denotes the insert point

根据插入迭代器的不同，其插入的位置与调用的函数都有不同：

front_inserter 会创建调用 c.push_front(val) 的迭代器，在容器首部插入元素 val
back_inseter 会创建调用 c.push_back(val) 的迭代器，在容器尾部插入元素 val
inserter 会创建调用 c.insert(val, pos) 的迭代器，在迭代器 pos 指代的位置插入元素 val

使用插入迭代器的容器必须支持该迭代器对应的调用。

插入迭代器支持 *，++, – 等运算，但这些运算对其没有任何影响，统统会返回迭代器本身。

inserter

成功 inserter(c, iter) 这种形式会得到一个迭代器。假设该迭代器为 it，也就是：

it = inserter(c, iter);

那么当我们在使用该迭代器进行插入操作的时候：

it = 222;

实际上等同于：

it = c.insert(it, 222);
++it;

这是因为 inserter 的插入操作，始终要保证插入的位置处于初始插入点的前一位。本例中，iter 用于设定第一次的插入点，而 it 用于后期维护本轮的插入点。由于 c.insert() 会让 it 指向新插入的元素，为了更新插入点，每次插入结束后，it 都会往后（右）移动一位，将当前位置重新指向初始的插入点，也就是由 iter 指定的初始位置：

<html>

</html> 换句话说，插入的位置由 iter 决定。

back_inserter

back_inserter 的操作类似，只是因为 back_inserter 会调用 push_back()，因此初始插入点已经被指定到了容器的尾部：

it = back_inserter(c);
it = 222;
it = 333;
//output
........, 222, 333

front_inserter

front_inserter 的使用方法与 back_inserter 一致。但由于 push_front() 的机制问题，导致最后插入的元素永远在最开头：

it = back_inserter(c);
it = 222;
it = 333;
//output
333,222,.......

也就是插入的元素会以倒序的形式呈现。

插入迭代器 也拥有 ++it, it++, *it 等操作。但与一般迭代器不同，这些操作对其均不构成任何影响，统统会返回 it。

书中的一些例子：

list<int> 1st = {1,2,3,4};
list<int> lst2, lst3;     // empty lists
// after copy  completes, 1st2 contains 4 3 2 1
copy(1st.cbegin(), lst.cend(), front_inserter(lst2));
// after copy completes, 1st3 contains 1 2 3 4
copy(1st.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

iostream 迭代器

iostream 迭代器绑定一个 stream 对象，并将该 stream 视作一系列指定类型的元素进行读或写的操作。其中：

istream_iterator：读入 Input stream
ostream_iterator: 写 output stream

常见的操作如下表：
<html>

<img src=“/_media/programming/cpp/cpp_primerstream_iterator_op.svg” width=“650”> </div> </html>

==istream_iterator 的操作== 使用 istream_iterator 有两个前提： * 创建 istream_iterator 时需要指定其操作对象的类型 * istream_iterator 使用 » 运算符，因此被操作的对象必须支持该运算符一些实例： <code cpp> istream_iterator<int> int_it(cin); reads int from cin istream_iterator<int> int_eof; default init, end iterator value; ifstrem in(“file”); istream_iterator<string> str_it(in); read string from “file” </code> 通过 istream_iterator 可以将输入的内容存到 vector 中. 这里 vector 的创建可以直接使用 istream_iterator 表示范围：

vector<int> vec(ini_it, int_eof);
//read inputs into a vector
while(int_it != int_eof)
	vec.push_back(*int_it++);

istream_iterator 与算法的配合使用

某些算法可以使用一对 istream_iterator 作为参数来获取输入范围，比如 accumulate:

istream_iterator<int> in(cin), eof;
cout << accumulate(in, eof, 0) << endl;

该段代码实现了所有从输入端输入的值的累加。

istream_iterator 与 lazy evaluation

istream_iterator 读取数据采用的是 lazy evaluation 的机制；也就是说，我们不能保证 istream_iterator 对 stream 的读取是即时的。该读取过程会发生在对 istream_iterator 的解应用之前。通常情况该机制下没有什么影响，除了以下两种情况：

istream_iterator 创建后没被使用就被销毁了
同时从两个 istream_iterator 读取同一段 stream

这两种情况下需要考虑该机制带来的影响。

ostream_iterator 的操作

ostream_iterator 可以绑定任意支持 « 运算符的 stream 对象。 ostream_iterator 同时支持第二个 parameter。该 parameter 接收类型为 c-style string（或者字符）, 功能是为每个输出的元素后面都加上一段字符。这个参数在打印元素之间的空格时很方便：

ostream_iterator<int> out_iter(cout, " ");
for (auto e : vec)
	*out_iter++ = e;
cout << endl;

当每次对 ostream_iterator 赋值时，写操作就会发生一次，同时还会附带上额外的空格字符。需要注意的是，由于解引用与自增对 ostream_iterator 无效，上述循环可以写成：

for (auto e : vec)
	out_iter = e;
cout << endl;

但为了保证对迭代器使用的一致性，加上解引用与自增可以使代码的表意更加清楚。

我们也可以使用 copy 算法来取代上述操作：

copy(vec.begin(), vec.end(), out_iter);
cout << endl;

stream 迭代器与 class type（实例）

通过使用 stream 迭代器进行输入、输出与循环，之前 Sales_data 的合并打印书籍的程序可以改写成如下代码：

istream_iterator<Sales_item> item_iter(cin), eof;
ostream_iterator<Sales_item> out_iter(cout, "\n");

//init the first book
Sales_item total = *item_iter;
//to the next input
++item_iter;

while(item_iter != eof) {
	//current book has the same isbn
	if(item_iter->isbn() == total.isbn())
		//accumulate
		total += *item_iter;
		//to the next input
		++item_iter;
	else {
		//print total for the current book
		out_iter = total;
		//start with the new book
		total = *item_iter;
		//to the next input
		++item_iter;
	}
}
//print the last book
out_iter = total;

几个要点：

通过对 item_iter 的自增实现对整个 stream 内容的遍历
通过对 item_iter 的解引用读入当前输入内容
流迭代器也可以调用成员
out_iter 可以输出定义了 « 操作的对象

反向迭代器

反向迭代器（Reverse Iterators）从右往左遍历整个容器。反向意味着自增自减操作与一般迭代器相反，比如反向迭代器的 ++ 意味着一般迭代器的 –。

除了 forward_list，所有的容器都有反向迭代器。反向迭代器写作 rbegin，rend，以及其常量版本 crbegin & crend。rbegin 指代容器最后一个元素，而 rend 指代容器的 off-the-begin 元素：

<html>

</html>

反向迭代器与其他迭代器的关系

反向迭代器与一般迭代器的遍历过程正好相反。利用这一点可以方便我们进行做一些对容器末尾的操作。比如我们有一个 string line，包含了几个 word, 中间以逗号隔开，找第一个被逗号隔开的 word 可以写成：

// find the first element in a comma-separated list
auto comma = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), comma) << endl;

如果想直接找最后一个被逗号隔开的 word, 则可以利用反向迭代器：

auto rcomma = find(line.rcbegin(), line.rcend(), ",");

不过如果对其输出，返现这个 word 是反着输出的，比如

//input
FIRST, MIDDLE, LAST
//output
TSAL

这是因为使用反向迭代器遍历容器时，是从右往左的。因此打印也是从右往左打印。不仅如此，由于 rcomma 也是反向迭代器，因此不能直接用于输出。正确的方式是以 rcomma 为起点，从左往右输出。这样做需要使用反向迭代器的成员 base 将其转化为一般迭代器：

cout <<string(rcomma.base(), line.cend()) << endl;

同时需要注意的是，如果使用反向迭代器代表范围，那么该范围是一个左闭右开的区间，比如 $[crbegin(), rcomma)$ 在容器中表现的区间是 $(rcomma.base(), cend()]$。由于这样的原因，rcomma 与 rcomma.base() 表示的实际上是两个相邻的位置：

<html>

</html>

泛型算法的结构

根据算法要求的不同，迭代器可以分为如下五大类：

<html>

<img src=“/_mediaprogramming/cpp/cpp_primer/iter_cate.svg” width=“400”> </div> </html>

这五种类别的迭代器分别具有不同的读 / 写 / 遍历 / 随机访问属性。 ===迭代器的五个类别=== 迭代器通过什么进行分类？

迭代器按照其自身允许的操作来分类的。高等级的迭代器支持低等级迭代器的所有操作。

<html>

<img src=“/_media/programming/cpp/cpp_primer/iter_hierarchy.svg” width=“600”>

</html>

算法是如何选择迭代器的？

C++ 标准中指明了了每个算法对迭代器等级的最低要求。如果迭代器不满足该要求，则无法使用。比如 find() 算法对序列进行扫描和读取，因此至少要 input iterator 才能满足需求。

但需要注意的是，很多编译器并不会对不满足要求的迭代器参数提出警告，因此使用之前一定要检查该参数是否满足要求。 ==输入迭代器== 输入迭代器（Input iterator）:用于读取序列中的元素。其支持以下操作： * 比较两个迭代器相等性的操作（==, !=） * 向前移动迭代器的操作（++, prefix or postfix） * 迭代器解应用操作（*it），用于读取迭代器元素。该解引用操作只能在赋值操作的右边，也就是只能作为值赋值给别的对象。 * 迭代器访问成员的操作（it→mem）输入迭代器只能用于顺序访问。同时，输入迭代器只能保证当前位置是有效，因此当输入迭代器自增以后，其他指向同位置输入迭代器的有效性也不会再被保证，也就是 a = b 并不能确保 a++ = b++。因此，输入迭代器只能用于 single-pass 的算法，比如 find()，accumulate() 等等。istream_iterator 也是输入迭代器。

stream 是个很好的例子。对读取下一部分的 stream 内容会使之前部分的内容失效。如果我们通过某个迭代器控制读取，那么当该迭代器移位，其他所有的指向之前内容的迭代器都会失效。

==输出迭代器== 输出迭代器（Output Iteratrors）用于向元素写入内容。它与输入迭代器的等级相同，唯一的区别是输出迭代器只能写，不能读。常见的使用的输出迭代器的算法有: copy()。ostream_iterator 也是输出迭代器。 ==前向迭代器== 前向迭代器（Forward iterators）比输入 / 输出迭代器等级高。该迭代器同时支持对元素的读和写操作，并拥有所有输出 / 输出迭代器可进行的操作。

除此之外，前向迭代器支持 multi-pass 的读写操作，也就是可以对同一元素进行反复读写。比如 replace(): <code cpp> template<class ForwardIt, class T> void replace(ForwardIt first, ForwardIt last, const T& old_value, const T& new_value) { for (; first != last; ++first) { if (*first == old_value) { read ,1st r/w to iter “first”

first = new_value; write, 2rd r/w to iter “first” } } } </code> 可以看出 replace() 的实现中， first 迭代器支持对其指向元素的多次读写（多次读写意味着迭代器可以保存当前元素的状态）。同时，该算法的循环是单向的；因此 replace() 可以使用前向迭代器来完成算法的实现。

其他常见的前向迭代器：forward_list 的成员迭代器。 ==双向迭代器== 双向迭代器（Bidirectional iterators）的等级高于前向迭代器。其支持前向迭代器的所有操作，除此之外，双向迭代器支持对序列的双向遍历，也就是同时支持迭代器的自增和自减操作。使用双向迭代器的常见算法有 reverse()。除了 forward_list 以外的容器，都要求其成员迭代器的等级不低于双向得带器。 ==随机访问迭代器== 随机访问迭代器（Random-access iterators）是迭代器类别中等级最高的迭代器。其不但支持之前所有迭代器支持的操作；并且还额外支持以下的操作： * 两个迭代器之前的关系运算操作（<, ⇐, >, >=），用于比较两个迭代器的相对位置 * 单个迭代器的移位操作（+, +=, -,-=） * 两个迭代器的相减（iter1 - iter2），用于获取迭代器之间的距离 * 下标操作（iter[n]），等同于移位再取对应元素的操作（*(iter+n)）常见使用随机访问迭代器的例子有：sort() 算法，以及 arrray、deque、string 和 vector 的成员迭代器。 ===算法形参的形式=== 除开迭代器的分类以外，算法的 parameter 的形式也有助于算法的理解。通常情况下算法有如下四种形式的参数分布： <code cpp> alg(beg, end, other args); alg(beg, end, dest, other args); alg(beg, end, beg2, other args); alg(beg, end, beg2, end2, other args); </code> 一般的来说， beg/end 表示输入源， beg2/end2 代表算法额外的输入源，dest 表示输出部分。 ==使用 dest 参数的算法== dest parameter 指代的是某个容器，或是插入迭代器，或是输出迭代器： * dest 是容器：代表算法将会把得到的输出写到这个容器中的元素里 * dest 是插入迭代器：添加元素到指定容器 * dest 是输出迭代器：将得到的内容写到输出的 stream 中采用 dest 参数的算法假定无论有多少数据，dest 都具有足够的空间容纳这些输入。 ==使用第二个输入源的算法== 有两种不同的形式用于指定第二个输入源： * beg2 / end2，指代了第二个输入源的范围为 [beg2, end2) * beg2，指代了第二个输入源的起始位置，并假定其范围不小于第一个输入源。 ===算法的命名规范=== 除开参数的规范，算法还遵循一系列命名和重载的规范。这些规范用于处理一些问题： * 如何替换默认的关系运算符 <, == * 决定算法结果写出的位置是其自身的输入范围，或是指定的 dest 对象。 ==使用重载版本传递谓词的算法== 拥有重载版本的算法有如下的两个特点： * 使用额外的谓词参数来代替 < 或者 == * 除此之外并没有额外的参数比如： <code cpp> unique(beg, end); uses the == operator to compare the elements

unique(beg, end, comp); uses comp to compare the elements </code> ==具有 if 版本的算法== 只接收单个元素值的算法通常都会有一个 _if 后缀的版本。该版本不属于重载，并且使用一个谓词来取代原版本中的元素值，比如： <code cpp> find(beg, end, val); find the first instance of val in the input range find_if(beg, end, pred); find the first instance for which pred is true </code> 提供 _if 是为了防止可能由重载带来的歧义。 ==具有拷贝 / 不拷贝两种版本的算法== 这种算法多半存在于排序算法中。默认情况下，排序算法会将排序结果重新写入输入的序列中。不过这些算法往往会提供第二个版本，允许算法将结果写入到指定的位置。第二个版本往往以 _copy 的后缀结尾，比如： <code cpp> reverse(beg, end); reverse the elements in the input range reverse_copy(beg, end, dest); copy elements in reverse order into dest </code> 某些版本还会基于 _if 的版本提供 _copy 的版本，意味着该版本会采取定制的策略，并将结果写到其他指定的位置： <code cpp> removes the odd elements from v1 remove_if(v1.begin(), v1.end(),

	 [](int i) { return i % 2; });

copies only the even elements from v1 into v2; v1 is unchanged remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), [](int i) { return i % 2; }); </code> ====容器专属的算法==== List 与 Forward_list 拥有专属的成员算法：sort、merge、remove、reverse 和 unique。特别是 sort，由于泛型的 sort 算法需要随机访问迭代器, 而 List 和 forward_list 只能使用双向迭代器与前向迭代器，因此泛型 sort 算法不能应用与这两种容器上。

除此之外，上述成员算法的泛型版本可以用于 List 类型，但代价太大。这是由于交换元素的方式不同：泛型版本需要通过输入序列来交换元素，而 List 只需要交换元素之间的链接即可完成元素的交换。因此，上述算法的专属版本效率要高出很多。

List 专属的成员算法如下表所示。对于没有在列表中出现的算法，只要其需求的迭代器与 List 提供的迭代器能正确匹配，那么就不会存在效率上的差异。

<html>

<img src=“/_media/programming/cpp/cpp_primer/list_algo_1.svg” width=“650”>

</html> ==splice 成员== List 与 Forward_list 都有其独占成员算法 splice。该算法为链表数据结构而专门设计，因此没有必要提供泛型版本：

<html>

<img src=“/_media/programming/cpp/cpp_primer/splice.svg” width=“650”>

</html>

需要注意的是，在调用 splice_after() 的时候，如果希望从 flst2 移动全部的元素，需要使用： <code cpp> flst.splice_after(flst.begin(), flst2); </code> 而不能使用 <code cpp> flst.splice_after(flst.begin(), flst2, flst2.begin(), flst2.end()); </code> 第二种方法会丢失 flst2 中的第一位数。原因是 forward_list 中表示范围是从 flst.before_begin() 开始的。 ==list 的成员算法会改变容器== 需要注意的是，即便 list 的成员算法与其泛型版本在功能上没有多大的区别，但一个重要的不同是 list 的成员算法会修改对应的容器。比如 list.remove() 会移除指定的元素，list.unique() 会将重复的元素真正的移除掉，而不是将其放到序列的末尾。

同样，merge 与 splice 也会删除其 argument。泛型版本的 merge 会将要合并的两个序列组合到一个新的目标序列中，而并不会改变两个源序列；而 List 版本的 merge 则会直接将新序列写入调用 merge 的 list 中。

What & How & Why

[ About ]

[ My Links ]

[ Notice ]

页面工具

站点工具

用户工具

目录

泛型算法

概述

泛型算法如何工作

算法、容器和迭代器的关系

初识泛型算法

只读算法

只读算法：accumulate

只读算法：equal

写算法

写算法：fill & fill_n

确保被写容器拥有足够空间的手段：back_inserter

写算法：copy & replace

排序算法

排序算法：sort() & unique()

为算法定制比较策略

方式1：传递函数给算法

实例：谓词配合 stable_sort() 排序

方式2：Lambda 表达式

find_if 简介

Lambda 的基本概念

Lambda 表达式以及相关背景

Lambda 表达式的组成与定义

向 Lambda 传递参数

使用 Capture list

lambda 与 find_if() 的连用

for_each() 简介

整个的 biggies 函数

Lambda 的捕获与返回

值捕获

引用捕获

隐藏捕获以及混用

Mutable Lambda

指定 Lambda 的返回类型

方法3：参数绑定

bind 与 placeholder

参数绑定与 arguments

使用 bind 对参数重新排序

使用 placeholder 的前提

绑定引用 parameters

再探迭代器

插入迭代器

inserter

back_inserter

front_inserter

iostream 迭代器

istream_iterator 与算法的配合使用

istream_iterator 与 lazy evaluation

ostream_iterator 的操作

stream 迭代器与 class type（实例）

反向迭代器

反向迭代器与其他迭代器的关系

泛型算法的结构