C++Primer笔记-第十章：泛型算法

前言

该系列是《C++Primer第五版》的笔记，包含本人认为值得记录和整理的主要的知识点，并不是全部内容，也不是具体的内容。
该系列文章的作用应该是作为复习或预习的参考，有哪些知识点忘记或想学，可以大致浏览下该文章，然后再去书中寻找详细解答。（本系列文章基本是按书本顺序罗列的知识点，便于大家去书中寻找）
所以看该文章前，需要有一定的C++基础，否则阅读起来可能有困难。

本文大致整理了第十章的知识点，涉及到C++关于泛型算法和相关迭代器的知识，属于STL中比较基础的部分，在迭代器部分可能有些难度，需要多阅读几遍。

链接目录

• 第二章：变量与基本类型
• 第三章：字符串、向量和数组
• 第四章：表达式
• 第五章：语句
• 第六章：函数
• 第七章：类
• 第八章：IO库
• 第九章：顺序容器
• 第十章：泛型算法
• 第十一章：关联容器
• 第十二章：动态内存
• 第十三章：拷贝控制
• 第十四章：重载运算与类型转换
• 第十五章：面向对象程序设计
• 第十六章：模板与泛型编程
• 第十七章：标准库特殊设施
• 第十八章：用于大型程序的工具
• 第十九章：特殊工具与技术

概述

大多数算法定义在头文件algorithm中，标准库还在头文件numeric中定义了一组数值泛型算法。
算法不依赖于容器，通过迭代器工作。

另外，算法不会执行容器的操作，它运行在迭代器之上，不会添加或删除容器中的元素。

只读算法

这些算法只会读取输入范围内的元素，从不改变元素。例如，find和count。

//对vec中的元素求和，和的初值为0
int sum = accumulate(vec.cbegin(), vec.cend, 0);

操作两个序列的算法：如equal，比较两个序列的值

//arr2元素至少和arr1一样多
equal(arr1.cbegin(), arr1.cend(), arr2.cbegin())

写容器元素的算法

//将每个元素置为0，给定序列的有效性由程序员确定
fill(vec.begin(), vec.end(), 0);

算法不检查写操作：

vector<int> vec;
//(起始迭代器，计数值，值)，对对应的值进行覆写
fill_n(vec.begin(), vec.size(), 0);
fill_n(vec.begin(), 10, 0);//错误，空向量中没有值，进行写操作未定义

back_inserter：向插入迭代器(insert iterator)赋值时，会向容器中添加元素。

vector<int> vec;
auto it = back_inserter(vec);//获取插入迭代器
*it = 42;//对插入迭代器赋值会调用push_back

fill_n(back_inserter(vec), 10, 0);//通过插入迭代器插入10个0

拷贝算法：

int a1[] = {1, 2, 3};
int a2[sizeof(a1)/sizeof(*a1)];
//ret指向拷贝到a2的尾元素之后的位置
auto ret = copy(begin(a1), end(a1), a2);

//将所有值为0的元素改为42
replace(ilst.begin(), ilst.end, 0, 42);
//保留原序列不变，在ivec中保存一份拷贝
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

重排容器元素的算法

例如sort，利用<运算符来实现排序，因此容器元素只有支持<运算符才能进行排序。如果元素不支持<运算符，也可以指定自己的比较器。

消除重复元素：unique函数删除相邻的重复元素，因此使用unique之前一般需要排序。重复元素会堆积在不重复区域之后。

sort(words.begin， words.end());
//unique返回不重复区域之后一个位置的迭代器
auto end_unique = unique(words.begin(), words.end());
//unique并不删除元素，真正删除需要手动
words.erase(end_unique, words.end(());

向算法传递函数

谓词：可调用的表达式，返回结果是一个能作用于条件的值。

• 一元谓词：只接受单一参数
• 二元谓词：接受两个参数

bool isShorter(const string &s1, const string &s2){
	return s1.size() < s2.size();
}
//isShorter是一个二元谓词，排序基于谓词进行
sort(words.begin(), words.end(), isShorter);

lambda表达式

lambda：可以视为一个未命名的内联函数，可以定义在函数内部，必须使用尾置返回。
形式：[capture list](parameter list) -> return type{function body}

参数：

• capture list：捕获列表
• parameter list：参数列表
• return type：返回类型
• function body：函数体

捕获列表：包含函数体内声明的局部变量，可为空，只有声明之后才能在lambda函数体内使用。捕获列表只用于局部非static变量，可以不声明直接使用局部static变量和在它所在函数之外声明的名字。

//lambda表达式可以忽略参数列表和返回类型
auto f = []{return 42;};
cout << f() << endl;

//传递参数
[](const string &a, const string &b){
	return a.size() < b.size();
}
//等价sort(words.begin(), words.end(), isShorter);
sort(words.begin(), words.end(), 
	 [](const string &a, const string &b)
		 {return a.size() < b.size();});
//使用捕获列表
//sz为lambda表示所在函数的局部变量，未在[]内声明，则函数体内不能使用
[sz](const string &a){
	return a.size() >= sz;
};

find_if：前两个参数是一对迭代器，表示范围，第三个参数是一个谓词。

//获取一个迭代器，指向第一个满足size>=sz的元素
auto wc = find_if(words.begin(), words.end(), 
			  [sz](const string &a)
				  {return a.size() >= sz;});

for_each算法：对每个对象调用一个可调用的对象(函数)。

//每行输出一个元素
for_each(words.begin(), words.end(),
	 [](const string &s)
		 {cout << s << endl;});

lambda捕获和返回

值捕获：

int v1 = 42;
//将v1拷贝到f
auto f = [v1]{return v1;};
v1 = 0;
//f输出42
cout << f() << endl;

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

int v1 = 42;
auto f = [&v1]{return v1;};
v1 = 0;
//输出0，保存的是引用
cout << f() << endl;

隐式捕获：

可变lambda：可以改变所捕获变量的值，相当于在调用时将v1当作参数传入，传入参数包含在[]内，不用在调用时显式声明。

int v1 = 42;
auto f = [v1]()mutable{return ++v1;};
v1 = 0;
//f输出43
cout << f() << endl;

指定lambda返回类型：

//transform将前一对内的元素执行谓词，然后将结果写入第三个迭代器
transform(vec.begin(), vec.end(), vec.begin(),
		  [](int i) -> int{
			if(i < 0) return -i;
			else return i;
		  });

参数绑定

标准库bind函数：定义在头文件functional，可以看作一个通用的函数适配器，它接受一个可调用对象，生成一个新的可调用对象。
一般形式为：auto newCallable = bind(callable, list);
其中newCallable是可调用对象，当我们调用newCallable时，它会调用callable并传入参数list。
list中可能包含如_n的名字，代表第n个参数，如_1代表newCallable中的第一个参数。_n此类的占位符定义在命名空间placeholders命名空间中，需要声明命名空间using namespace std::placeholders才能使用。

绑定check_size的sz参数：

bool check_size(const string &s, string::size_type sz){
	return s.size() >= sz;
}
//check6是一个可调用对象，判断字符串大小是否大于等于6
auto check6 = bind(check_size, _1, 6);
string s = "hello";
cout << check6(s) << endl;//等价调用check_size(s, 6)

bind的参数：可以重新排序。默认情况下，bind不是占位符的参数是被拷贝到bind返回的可调用对象中。有时需要传引用或绑定的类型无法拷贝，可以使用标准库函数ref(定义在functional中)，它返回一个对象给定的引用，也有const版本的cref，传入const的引用。

auto g = bind(f, a, b, _2, c, _1);
g(X, Y);//等价于f(a, b, Y, c, X)
//os不可拷贝
ostream &print(ostream &os, const string &s){
	return os << s;
}
//错误，os不能拷贝
for_each(words.begin(), words.end(), bind(print, os, _1));
//正确
for_each(words.begin(), words.end(), bind(print, ref(os), _1));

再探迭代器

• 插入迭代器：用来向容器插入元素。
• 流迭代器：绑定到输入或输出流上，用来遍历所关联的流。
• 反向迭代器：反向迭代器反向移动。
• 移动迭代器：移动迭代器不拷贝元素，而是移动它们。

插入迭代器

操作：

• it = t：在it指定的当前位置插入t
• *it,it++：没有意义，都返回it

插入器的类型：

• back_inserter：使用push_back的插入迭代器。
• front_inserter：使用push_front的插入迭代器。
• inserter：使用insert的插入迭代器。

*it = val;
//等价于
it = c.insert(it, val);
++it;

iostream迭代器

• istream_iterator：读取输入流。
• ostream_iterator：：向输出流写数据。

istream_iterator操作：必须指定迭代器将要读写的对象类型。

istream_iterator<int> in_iter(cin);//从cin读取int
istream_iterator<int> eof;//istream尾后迭代器
while(in_iter != eof)
	vec.push_back(*in_iter++);

eof：空的istream_iterator，当流的迭代器遇到文件尾或IO错误，迭代器的值就为空，因此可以当作尾后迭代器。

使用算法操作流迭代器：

istream_iterator<int> in(cin), eof;
//计算从标准输入读取的值的和
cout << accumulate(in, eof, 0) << endl;

ostream_iterator操作：必须是一个C风格字符串。

ostream_iterator<int> out_iter(cout, " ");
for(auto e : vec)
	*out_iter++ = e;//将元素写到cout，每个元素加个空格
	//实际上等价于out_iter = e;
cout << endl;

//也可以调用迭代器相关的算法
copy(vec.begin(), vec.end(), out_iter):
cout << endl;

反向迭代器

要考虑迭代器范围是左闭合的，所以正向迭代器和反向迭代器范围并不相同。
正向迭代器的首指针指向第一个元素，尾指针指向尾后。
反向迭代器的首指针指向最后一个元素，尾指针指向首前。

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

//在一个逗号分隔的列表中查找最后一个元素
auto comma = find(line.crbegin(), line.crend(), ",");
//错误，将逆序输出单词，迭代器是反向迭代器
cout << string(line.crbegin(), comma) << endl;
//正确，将反向迭代器转为正向迭代器
cout << string(comma.base(), line.cend()) << endl;

泛型算法结构

迭代器类型：高层迭代器支持低层迭代器的所有操作。

• 输入迭代器：只读，单遍扫描，只能递增。
• 输出迭代器：只写，单遍扫描，只能递增。
• 前向迭代器：可读写，多遍扫描，只能递增。
• 双向迭代器：可读写，多遍扫描，可递增递减。
• 随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算。

5类迭代器

对于一个算法，有要求迭代器的最小类别，如find，至少是输入迭代器，replace至少是前向迭代器。

输入迭代器至少支持：

• 用于比较两个迭代器的相等运算。
• 用于推进迭代器的递增运算。
• 用于读取元素的解引用运算，出现在右侧，用于读取值。
• 箭头运算符。

输出迭代器至少支持：

• 用于推进迭代器的递增运算。
• 解引用运算符，出现在左侧，用于写入值。

前向迭代器：支持前两类迭代器的所有操作。

双向迭代器：支持前向迭代器的所有操作，额外支持递减运算符。

随机访问迭代器：支持双向迭代器的所有操作，额外支持

• 用于比较了两个迭代器相对位置的关系运算符(<、<=、>、>=)。
• 迭代器和一个整数值的加减运算。
• 用于两个迭代器的减法运算，获取迭代器距离。
• 下标运算符。

算法命名规范

一些算法使用重载形式传递一个谓词：一个版本用元素类型的运算符来比较，另一个版本接受一个额外谓词参数来代替<或==。

unique(beg, end);//使用==运算符比较
unique(beg, end, f);//使用谓词f比较

_if版本的算法：一个版本接受值，另一个版本通过谓词代替元素值。

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

区分拷贝元素的版本和不拷贝的版本：默认情况下，重排元素的算法将重排后的元素写回原序列，另一个版本提供将结果写入其他序列。

reverse(beg, end);//反转序列
reverse_copy(beg, end, dest);//将元素逆序拷贝到dest，原序列不变

remove_if(v1.begin(), v1.end(), f);//删除序列中奇数
remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), f);//结果为删除奇数后的序列拷贝到v2，实际工作将偶数元素拷贝到v2

特定容器算法

list和forward_list的迭代器分别为为双向迭代器和前向迭代器，对于通用类型的算法，例如sort要求随机访问迭代器，可以使用但是代价太高，所以有链表版本特有的算法。
如：lst.sort()

splice成员：链表数据结构所特有的算法。

• lst.splice(p, lst2)：p是一个指向lst中元素的迭代器，将lst2的所有元素移动到lst的p之前的位置。将元素从lst2中删除。(lst和lst2不能是相同的链表)
• lst.splice(p, lst2, p2)：p2是指向lst2中元素的迭代器，将p2指向的元素移动到lst中。(lst和lst2可以是相同的链表)
• lst.splice(p, lst2, b, e)：b和e表示lst2中的合法范围，将给定范围的元素从lst2移动到lst。(lst和lst2可以是相同的链表，但p不能指向给定范围中的元素)

---