What & How & Why

泛型算法

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 的一个简单流程:

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

我们发现这整个过程都没有任何与容器相关的操作。因此,只要是能使用迭代器访问元素的地方,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_inserterinsert_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() 真正删除上述范围的元素。


写成代码就是:
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(算法调用它对元素进行比较)

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

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



比如 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() 参数列表中即可。



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));
由于 placeholdernewCallable 对象 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);

可以总结出来的是:

  • newCallable 中:placeholder 使用 编号与其参数对应,即 _1 对应 第一个参数,以此类推
  • callable 中:placeholder 与其绑定参数的位置对应。比如上例中 f(a,b,X,c,Y),如果将 XY 调换,那么对应的 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 指定的初始位置:

换句话说,插入的位置由 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

常见的操作如下表:



istream_iterator 的操作

使用 istream_iterator 有两个前提:

  • 创建 istream_iterator 时需要指定其操作对象的类型
  • istream_iterator 使用 » 运算符,因此被操作的对象必须支持该运算符

一些实例:

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"
通过 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,所有的容器都有反向迭代器。反向迭代器写作 rbeginrend,以及其常量版本 crbegin & crendrbegin 指代容器最后一个元素,而 rend 指代容器的 off-the-begin 元素:

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

反向迭代器与一般迭代器的遍历过程正好相反。利用这一点可以方便我们进行做一些对容器末尾的操作。比如我们有一个 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()]$。由于这样的原因,rcommarcomma.base() 表示的实际上是两个相邻的位置




泛型算法的结构

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



这五种类别的迭代器分别具有不同的读 / 写 / 遍历 / 随机访问属性。

迭代器的五个类别

迭代器通过什么进行分类?

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



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

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():

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"
        }
    }
}
可以看出 replace() 的实现中, first 迭代器支持对其指向元素的多次读写(多次读写意味着迭代器可以保存当前元素的状态)。同时,该算法的循环是单向的;因此 replace() 可以使用前向迭代器来完成算法的实现。

其他常见的前向迭代器:forward_list 的成员迭代器。

双向迭代器

双向迭代器(Bidirectional iterators)的等级高于前向迭代器。其支持前向迭代器的所有操作,除此之外,双向迭代器支持对序列的双向遍历,也就是同时支持迭代器的自增和自减操作。使用双向迭代器的常见算法有 reverse()。除了 forward_list 以外的容器,都要求其成员迭代器的等级不低于双向得带器。

随机访问迭代器

随机访问迭代器(Random-access iterators)是迭代器类别中等级最高的迭代器。其不但支持之前所有迭代器支持的操作;并且还额外支持以下的操作:

  • 两个迭代器之前的关系运算操作<, ⇐, >, >=),用于比较两个迭代器的相对位置
  • 单个迭代器的移位操作(+, +=, -,-=
  • 两个迭代器的相减(iter1 - iter2),用于获取迭代器之间的距离
  • 下标操作(iter[n]),等同于移位再取对应元素的操作(*(iter+n)

常见使用随机访问迭代器的例子有:sort() 算法,以及 arrraydequestringvector 的成员迭代器。

算法形参的形式

除开迭代器的分类以外,算法的 parameter 的形式也有助于算法的理解。通常情况下算法有如下四种形式的参数分布:

alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);
一般的来说, beg/end 表示输入源, beg2/end2 代表算法额外的输入源,dest 表示输出部分。

使用 dest 参数的算法

dest parameter 指代的是某个容器,或是插入迭代器,或是输出迭代器:

  • dest容器:代表算法将会把得到的输出写到这个容器中的元素里
  • dest插入迭代器:添加元素到指定容器
  • dest输出迭代器:将得到的内容写到输出的 stream 中

采用 dest 参数的算法假定无论有多少数据,dest 都具有足够的空间容纳这些输入。

使用第二个输入源的算法

有两种不同的形式用于指定第二个输入源:

  • beg2 / end2,指代了第二个输入源的范围为 [beg2, end2)
  • beg2,指代了第二个输入源的起始位置,并假定其范围不小于第一个输入源。

算法的命名规范

除开参数的规范,算法还遵循一系列命名和重载的规范。这些规范用于处理一些问题:

  • 如何替换默认的关系运算符 <, ==
  • 决定算法结果写出的位置是其自身的输入范围,或是指定的 dest 对象。
使用重载版本传递谓词的算法

拥有重载版本的算法有如下的两个特点:

  • 使用额外的谓词参数来代替 < 或者 ==
  • 除此之外并没有额外的参数

比如:

unique(beg, end); // uses the == operator to compare the elements
unique(beg, end, comp); // uses comp to compare the elements

具有 if 版本的算法

只接收单个元素值的算法通常都会有一个 _if 后缀的版本。该版本不属于重载,并且使用一个谓词来取代原版本中的元素值,比如:

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
提供 _if 是为了防止可能由重载带来的歧义

具有拷贝 / 不拷贝两种版本的算法

这种算法多半存在于排序算法中。默认情况下,排序算法会将排序结果重新写入输入的序列中。不过这些算法往往会提供第二个版本,允许算法将结果写入到指定的位置。第二个版本往往以 _copy 的后缀结尾,比如:

reverse(beg, end); // reverse the elements in the input range
reverse_copy(beg, end, dest);// copy elements in reverse order into dest
某些版本还会基于 _if 的版本提供 _copy 的版本,意味着该版本会采取定制的策略,并将结果写到其他指定的位置
// 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; });

容器专属的算法

ListForward_list 拥有专属的成员算法:sortmergeremovereverseunique。特别是 sort,由于 泛型的 sort 算法需要随机访问迭代器, 而 Listforward_list 只能使用双向迭代器与前向迭代器,因此泛型 sort 算法不能应用与这两种容器上。

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

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

splice 成员

ListForward_list 都有其独占成员算法 splice。该算法为链表数据结构而专门设计,因此没有必要提供泛型版本:



需要注意的是,在调用 splice_after() 的时候,如果希望从 flst2 移动全部的元素,需要使用:
flst.splice_after(flst.begin(), flst2);
而不能使用
flst.splice_after(flst.begin(), flst2, flst2.begin(), flst2.end());
第二种方法会丢失 flst2 中的第一位数。原因是 forward_list 中表示范围是从 flst.before_begin() 开始的。

list 的成员算法会改变容器

需要注意的是,即便 list 的成员算法与其泛型版本在功能上没有多大的区别,但一个重要的不同是 list 的成员算法会修改对应的容器。比如 list.remove() 会移除指定的元素,list.unique() 会将重复的元素真正的移除掉,而不是将其放到序列的末尾。

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