Fork me on GitHub

C++ Primer学习笔记：(十)泛型算法

发表于 | 分类于 | 阅读次数:
字数统计: 3,458

标准库并没有给每个容器添加大量功能，而是提供了一组算法，这些算法大多数都独立于任何特定的容器。这些算法是通用的(generic，或称泛型的)：可以用于不同类型的容器或者元素。算法通过在迭代器上进行操作来实现类型无关。

算法不直接改变所操作序列的大小。它们会将一个元素从一个位置拷贝到另一个位置，但不会直接添加或删除元素。
虽然算法不能向序列添加元素，但是插入迭代器可以做到。

概述（10.1，P336）

顺序容器只定义了很少的操作：在多数情况下，我们可以添加和删除元素、访问首尾元素、确定容器是否为空以及获得指向首元素或者尾元素之后位置的迭代器。

标准库定义了大约100个类型无关的对序列进行操作的算法。序列可以是标准库类型中的元素、一个内置数组或者是（例如）通过读写一个流来生成的。

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

初识泛型算法（10.2，P338）

accumulate：定义在头文件numeric中。作用是对范围求和。

euqal：定义在头文件algorithm中。作用是判断给定两个区间是否相等。假定第二个序列至少与第一个序列一样长。

fill：定义在头文件algorithm中。作用是对给定区间全部赋予某值。

fill_n：定义在头文件algorithm中。作用是对给定迭代器后的n个元素赋予某值。

back_inserter：定义在头文件iterator中。得到指向容器尾部的迭代器。

重排容器元素的算法

1
2
3
4
vector<string> words = {"the", "quick", "red", "fox","red", "the","slow"};
sort(words.begin(),words.end());
auto end_unique = unique(words.begin(),words.end());
words.erase(end_unique,words.end());

消除重复单词的程序：使用到了下面这三个算法：

  • sort：定义在头文件algorithm中。对指定区间排序；
  • unique：定义在头文件algorithm中。“消除”重复项，返回指向不重复值范围末尾的迭代器；
  • erase：容器操作，而不是算法。删除指定范围内的元素。

定制操作（10.3）

向算法传递函数（10.3.1）

谓词(predicate)是一个可调用的表达式，其返回结果是一个能用作条件的值。谓词分为：一元谓词和二元谓词。几元谓词接受几元参数。

使用谓词的排序版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<string> words = {"the", "quick", "red", "fox","red", "the","slow"};
cout << "Before: ";
for(auto iter = words.begin();iter != words.end(); ++iter){
	cout << *iter << "  ";	
}
cout << endl;
sort(words.begin(),words.end(), isShorter); //使用谓词进行排序
cout << "After sort: ";		
	for(const auto &s: words){
	cout << s << "  ";	
}
cout << endl;

结果为：

1
2
Before: the  quick  red  fox  red  the  slow  
After sort: the  red  fox  red  the  slow  quick

可以看到三个字母的都在最前面，接着是长度为4,然后是长度为5的。

有时候我们希望长度相同的元素按照字典进行排序，此时可用stable_sort算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool isShorter(const string &s1, const string &s2){
	return s1.size() < s2.size();
}
void elimDups(vector<string> &words){
	//按字典顺序排序
	sort(words.begin(),words.end());
	auto end_unique = unique(words.begin(),words.end());
	words.erase(end_unique,words.end());
}
int main(){
	vector<string> words = {"the", "quick", "red", "fox","red", "the","slow", "seen"};
	elimDups(words);
	stable_sort(words.begin(), words.end(), isShorter);
	cout << "After stable_sort: ";		
 	for(const auto &s: words){
		cout << s << "  ";	
	}
	cout << endl;
	return 0;
}

输出为：

After sort: fox red the seen slow quick

lambda表达式(10.3.2，P345)

可调用对象：对于一个对象或一个表达式，如果可以对其使用调用运算符，则称为可调用的；可调用的对象有：函数、函数指针、重载函数调用运算符的类和lambda表达式。

lambda表达式形式：

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

capture list是一个lambda所在函数中定义的局部变量的列表（通常为空）；
return type、parameter list和function body分别表示返回类型、参数列表和函数体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool isShorter(const string &s1, const string &s2){
	return s1.size() < s2.size();
}
void elimDups(vector<string> &words){
	//按字典顺序排序
	sort(words.begin(),words.end());
	auto end_unique = unique(words.begin(),words.end());
	words.erase(end_unique,words.end());
}
void biggies(vector<string> &words, vector<string>::size_type sz)
{
	// 将words按字典序排序，删除重复单词
	elimDups(words); 
	// 按长度排序，长度相同的单词维持字典序
	stable_sort(words.begin(), words.end(), isShorter); 
	
	// 获取一个迭代器，指向第一个满足size()>=sz的元素
	auto wc = find_if(words.begin(), words.end(), [sz](const string &a){ return a.size() >= sz; });
	// 计算满足size>=sz元素的数目
	auto count = words.end() - wc;
	cout << count << " " << ( (count>1) ? "word" : "words" ) << " of length " << sz << " or longer" << endl;
	
	//打印长度大于等于给定值的单词，每个单词后面接一个空格
	for_each(wc,words.end(),[](const string &a){ cout << a << " "; });
	cout << endl;
}
int main(){
	vector<string> words = {"the", "quick", "red", "fox","red", "the","slow", "seen"};
	biggies(words,4);
	return 0;
}

lambda捕获与返回（10.3.3，P349）

捕获方式分为显式捕获、隐式捕获与混合使用。

显式捕获分为值捕获与引用捕获。
值捕获：与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是在调用时拷贝。

隐式捕获：在捕获列表写一个&（引用捕获）或者=（值捕获）。

混合使用隐式捕获和显式捕获：捕获列表第一个元素必须是一个&或=，并且显式捕获的变量必须采用与隐式捕获不同的方式。

参数绑定（10.3.4，P354）

标准库bind函数：定义在头文件：functional；它接受一个可调用对象，生成一个新的可调用对象来适应原对象的参数列表。

调用bind的形式：

auto newCallable=bind(callable, arg_list);

newCallable本身是一个可调用对象，arg_list是一个逗号分隔的参数列表，对应给定的callable的参数。arg_list中的参数可能包含形如_n的名字，_1是newCallable的第一个参数,_2为第二个参数，依次类推。

_n参数在命名空间placeholders中，需要如下声明：

1
using namespace std::placeholders;

bind拷贝参数而不能拷贝ostream。我们可以使用ref函数。

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

再探迭代器（10.4）

标准库在头文件iterator中定义了几种迭代器：

  • 插入迭代器：这些迭代器被绑定到一个容器上，可用来向容器插入元素。
  • 流迭代器：这些迭代器被绑定到输入或输出流上，可用来遍历所有关联的IO流。
  • 反向迭代器：这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
  • 移动迭代器：这些专用的迭代器不是拷贝其中的元素，而是移动它们。

插入迭代器（10.4.1，P358）

插入器的三种类型
back_inserter 创建一个使用push_back的迭代器
front_inserter 创建一个使用push_front的迭代器
inserter 创建一个使用insert的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将插入到给定迭代器所表示的元素之前。

练习10.28：分别使用上述三种插入迭代器将vector的内容拷贝到容器中。

1
2
3
4
5
6
7
8
9
10
vector<int> v;
for (int i= 1; i<=9; ++i)
{
	v.push_back(i);
}
deque<int> di, dbi, dfi;
copy(v.begin(), v.end(), inserter(di, di.begin())); // 接收两个参数
copy(v.begin(), v.end(), back_inserter(dbi));
copy(v.begin(), v.end(), front_inserter(dfi));

三个插入器的最终结果为：

1
2
3
inserter:1 2 3 4 5 6 7 8 9 
back_inserter:1 2 3 4 5 6 7 8 9 
front_inserter:9 8 7 6 5 4 3 2 1

iostream迭代器

istream_iterator操作

istream_iterator操作 含义
istream_iterator<T> in(is) in从输入流is读取类型为T的值
istream_iterator<T> end; 读取类型为T的值的istream_iterator迭代器，表示尾后位置 （默认初始化）
in1 == in2 in1和in2必须读取相同类型。如果它们都是尾后迭代器，或绑定到相同
in1 != in2 的输入，则两者相等
*in 返回从流中读取的值
in->mem 与(*in).mem的含义相同
++in,in++ 使用元素类型所定义的>>运算符从输入流中读取下一值。与以往一样，前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值

计算从标准输入的值的和：

1
2
istream_iterator<int> in_iter(cin), eof;
cout << "sum is: " << accumulate(in_iter, eof, 0) << endl;

ostream_iterator操作

ostream_iterator操作 含义
ostream_iterator<T> out(os); out将类型为T的值写到输出流os中
ostream_iterator<T> out(os,d); out将类型为T的值写到输出流os中，每个值后面都输出一个d。d指向一个空字符结尾的字符数组
out = val; 用<<运算符将val写入到out所绑定的ostream中。val的类型必须与out可写的类型兼容。
*out,++out,out++; 这些运算符是存在的，但不对out做任何事情。每个运算符都返回out

使用流迭代器输出vector的内容：

1
2
3
vector<int> v{1, 2, 3, 4, 5};
ostream_iterator<int> out_iter(cout, " ");
copy(v.begin(),v.end(),out_iter);

反向迭代器（10.4.3，P363）

sort函数正向与逆序排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> v{3,5,1,7,4,6,2,9,8};
sort(v.begin(),v.end());
cout << "After sort: ";
for(auto i = v.begin(); i != v.end(); ++i)
{
	cout << *i << " " ;
}
cout << endl;
sort(v.rbegin(),v.rend());
cout << "After reverse sort: ";
for(auto i = v.begin(); i != v.end(); ++i)
{
	cout << *i << " " ;
}
cout << endl;

输出结果为：

1
2
After sort: 1 2 3 4 5 6 7 8 9 
After reverse sort: 9 8 7 6 5 4 3 2 1

使用反向迭代器逆序打印一个vector(练习10.34)：

1
2
3
4
5
6
7
vector<int> v{3,5,1,7,4,6,2,9,8};
cout <<"逆序打印：";
for(auto i = v.crbegin(); i != v.crend(); ++i)
{
	cout << *i << " " ;
}
cout << endl;

输出结果为：

逆序打印：8 9 2 6 4 7 1 5 3

使用find在一个int的list中查找最后一个值为0的元素（练习10.36）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
list<int> v{3,5,1,0,7,4,0,6,2,9,8};
auto it = find(v.cbegin(),v.cend(),0);
auto itr = find(v.crbegin(),v.crend(),0);
cout << "迭代器的指向位置： " << *it << *itr <<*(itr.base()) << endl;	
cout << "After find: " ;
for(auto i = it; i != v.cend(); ++i)
{
	cout << *i << " " ;
}
cout << endl;
cout << "After reverse find: " ;
for(auto i = itr.base(); i != v.cend(); ++i)
{
	cout << *i << " " ;
}
cout << endl;

输出为：

1
2
3
迭代器的指向位置： 006
After find: 0 7 4 0 6 2 9 8 
After reverse find: 6 2 9 8

泛型算法结构（10.5）

迭代器类别

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

算法形参模式

4种算法形参模式：

1
2
3
4
alg(beg,end,other args);
alg(beg,end,dest,other args);
alg(beg,end,beg2,other args);
alg(beg,end,beg2,end2,other args);

其中，alg是算法的名字，beg和end是算法所操作的输入范围。dest、beg2和end2，都是迭代器参数。
dest参数表示算法可以写入的目的位置的迭代器，算法假定：不管写入多少个元素都是安全的。

算法命名规范

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

_if版本的算法：接受一个元素值的算法通常有一个接受谓词版本的算法，加上后缀_if

区分拷贝元素的版本和不拷贝元素的版本：重排元素的算法通常直接写回给定的输入序列，也可以将元素写到一个指定的输出目的的位置，此类算法在名字后面加上_copy

特定容器算法（10.6）

list和forward_list成员函数版本的算法

list和forward_list成员函数版本的算法 含义
lst.merga(lst2)
lst.megra(lst2,comp) 将来自lst2的元素合并入lst。lst和lst2都必须是有序的。元素将从lst2中删除。在合并之后，lst2变成空。第一个版本使用<运算符；第二个版本使用给定的比较操作。
lst.remove(val)
lst.remove_if(pred) 调用erase删除掉与给定值相等(==)或令一元谓词为真的每个元素
lst.reverse() 反转lst中元素的顺序
lst.sort()
lst.sort(comp) 使用<或给定比较操作排序元素
lst.unique()
lst.unique(pred) 调用erase删除同一个值的连续拷贝。第一个版本使用==；第二个版本使用给定的二元谓词

list和forward_list的splice成员函数的参数

lst.splice(args)或flst.splice_after(args) 含义
(p,lst2) p是一个指向lst中元素的迭代器，或一个指向flst首前位置的迭代器。函数将lst2的所有元素移动到lst中p之前的位置或是flst中p之后的位置。将元素从lst2中删除。lst2的类型必须与lst或flst相同，且不能是同一个链表。
(p,lst2,p2) p2是一个指向lst2中位置的有效迭代器。将p2指向的元素移动到lst中，或将p2之后的元素移动到flst中。lst2可以是与lst或flst相同的链表。
(p,lst2,b,e) b和e必须表示lst2中的合法范围。将给定范围中的元素从lst2移动到lst或flst。lst2与lst(或flst)可以是相同的链表，但p不能指向给定范围中元素。

术语表

泛型算法：generic algorithm
谓词：predicate
一元谓词：unary predicate
二元谓词：binary predicate

参考资料

  1. C++ Primer 中文第五版
  2. C++primer第五版第十章学习笔记
  3. 《C++primer(第五版)》学习之路-第十章：泛型算法
------ 本文结束感谢您的阅读 ------
坚持原创技术分享，您的支持将鼓励我继续创作！
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多