C++Primer 5th：第十章泛型算法

本文最后更新于：2020年7月12日上午

第十章泛型算法

10.1 概述

头文件：algorithm，numeric
标准库算法find

int val = 42;
vector<int> vec{ 1,2,3,4,5 };
auto result = find(vec.cbegin(), vec.cend(), val);
cout << "The value " << val
    << (result == vec.cend() ? " is not present" : " is present") << endl;

迭代器令算法不依赖于容器，但算法依赖于元素类型的操作
算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素。

10.2 初始泛型算法

10.2.1 只读算法

只会读取其输入范围内的元素，而从不改变元素。
find，count，accumulate

//对 vec 中的元素求和，和的初值是0
int sum = accumulate(vec.cbegin, vec.cend, 0);
//将vector中所有的string元素连接起来
string sum = accumulate(v.cbegin(), v.cend, string(""));

最好使用 cbegin() 和 cend() 。
equal
- 确定两个序列是否保存相同的值
- 相等返回 true ，否则返回 false

1 2	`//roster2中的元素数目应该至少与roster1一样多 equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());`

10.2.2 写容器元素的算法

fill
- 将给定的值赋予输入序列中的每个元素

//将每个元素重置为0
fill(vec.begin(), vec.end(), 0);
//将容器的一个子序列设置为10
fill(vec.begin, vec.begin + vec.size()/2, 10);

算法不检查写操作，以fill_n为例

vector<int> vec;
//将所有元素重置为0
fill_n(vec.begin(), vec.size(), 0);
//错误❌
//fill_n(vec.begin(), 10, 0);

插入迭代器：back_inserter
- 向容器中添加元素
- 头文件：iterator

vector<int> vec;
auto it = back_inserter(vec);
*it = 42;
//添加10个元素到vec
fill_n(back_inserter(vec), 10, 0);

拷贝算法：
- copy
- 必须保证目标目的序列至少要包含与输入序列一样多的元素

int a1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int a2[sizeof(a1)/sizeof(*a1)];
//copy返回其目的位置迭代器（递增后）的值
//ret指向a2的尾元素之后的位置
auto ret = copy(begin(a1), end(a1), a2);

- replace

//将所有值为0的元素改为42
replace(ilst.begin(), ilst.end(), 0 , 42);
//希望保留原序列不变
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

10.2.3 重排容器元素的算法

消除重复的单词：sort，unique

void elimDups(vector<string>& words)
{
    //按字典排序words,以便查找重复单词
	sort(words.begin(), words.end());
    //unique重排输入范围，使得每个单词只出现一次
    //排列在范围的前部，返回指向不重复区域之后一个位置的迭代器
	auto end_unique = unique(words.begin(), words.end());
    //使用向量操作erase删除重复单词
	words.erase(end_unique, words.end());
}

10.3 定制操作

10.3.1 向算法传递函数

谓词（predicate）
- 可调用的表达式，返回结果使一个能用作条件的值
- 一元谓词：只接受单一参数
- 二元谓词：有两个参数

bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}
//按长度由短至长排序words
sort(words.begin(), words.end(), isShorter);

stable_sort：保持等长元素间的字典序

elimDups(words);
stable_sort(words.begin(), words.end(), isShorter);
for(const auto &s : words)
	cout << s << " ";
cout << endl;

10.3.2 lambda表达式

可以向算法传递任何类别的可调用对象（callable object）
lambda表达式的形式
- 一个 lambda 只有在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用该变量
- 捕获列表只用于局部非 static 变量
- lambda可以直接使用局部static变量和在它所在函数之外声明的名字

//1. 介绍 lambda
[capture list](parameter list) -> return type {function body}
//忽略参数列表和返回类型
auto f = [] { return 42; };
//调用
cout << f() << endl;
//2. 向lambda传递参数
stable_sort(words.begin(), words.end(),
           [](const string &a, const string &b)
            {return a.size() < b.size();});
//3. 使用捕获列表
[sz](const string &a)
	{return a.size >= sz;};
//4. 调用find_if
//获取指向第一个满足a.size >= sz 元素的迭代器
auto wc = find_if(words.begin(), words.end(),
                 [sz](const string &a)
                  {return a.size >= sz; });

完整的biggies
- 求大于一个给定长度的单词有多少
- 打印大于等于给定长度的单词

string make_plural(size_t ctr, const string& word, const string& ending)
{
	return (ctr > 1) ? word + ending : word;
}

void biggies(vector<string>& words, vector<string>::size_type sz)
{
	elimDups(words);
	//按长度排序，长度相同的单词维持字典序
	stable_sort(words.begin(), words.end(),
		[](const string& a, const string& b)
		{return a.size() < b.size(); });
	//获取一个迭代器，指向第一个满足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 << " " << make_plural(count, "word", "s")
		<< " of  length " << sz << " or longer" << endl;
	//打印长度大于等于给定值的单词，每个单词后面接一个空格
	for_each(wc, words.end(),
		[](const string& s) {cout << s << " "; });
	cout << endl;
}

10.3.3 lambda捕获和返回

值捕获

void fcn1()
{
    size_t v1 = 42;
    auto f = [v1]{return v1;};
    v1 = 0;
    //j为42；f保存了创建它时v1的拷贝
    auto j = f();
}

引用捕获
- 当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的
- 尽量减少捕获的数据量
- 如果可能，应该避免捕获指针或引用

void fcn2()
{
    size_t v1 = 42;
    auto f2 = [&v1]{return v1;};
    v1 = 0;
    //j为0；f2保存v1的引用，而非拷贝
    auto j = f2();
}

隐式捕获
- 让编译器根据lambda体中的代码推断要使用的变量
- 在捕获列表中写一个&或=
- &：捕获引用方式
- =：值捕获方式
- 混合使用隐式捕获和显示捕获，捕获列表第一个元素必须是&或=

//sz为隐式捕获，值捕获方式
wc = find_if(words.begin(), words.end(),
             [=](const string &s)
             {return s.size() >= sz; });
//混合使用隐式捕获和显示捕获
void biggies(vector<string> &words, 
             vector<string>::size_type sz, ostream &os = cout, chat c = ' ')
{
    //os隐式捕获，引用捕获方式；c显式捕获，值捕获方式
    for_each(words.begin(), words.end(), [&, c](const string &s){os << s << c;});
    //os显式捕获，引用捕获方式；c隐式捕获，值捕获方式
    for_each(words.begin(), words.end(), [=, &os](const string &s){os << s << c;});
}

可变lambda：mutable

void fcn3()
{
    size_t v1 = 42;
    auto f = [v1]() mutable {return ++v1;};
    v1 = 0;
    //j为0；f2保存v1的引用，而非拷贝
    auto j = f();
}

指定 lambda 返回类型

//将输入序列中的每个元素替换为可调用对象操作该元素得到的结果
transform(vi.begin(), vi.end(), vi.begin(),
         [](int i) -> int
          {if(i < 0) return -i; else return i;});

10.3.4 参数绑定

find_if接受一个一元谓词，不能使用check_size

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

标准库 bind 函数
- 头文件：functional

1 2	`//一般形式 auto newCallable = bind(callable, arg_list);`

绑定check_size的 sz 参数

auto check6 = bind(check_size, _1, 6);
string s = "hello";
bool b1 = check6(s);
//基于lambda的find_if调用
auto wc = find_if(words.begin(), words.end(),
                 [sz](const string &a)
                 {return a.size >= sz; });
//替换为如下版本
auto wc = find_if(words.begin(), words.end().
                 bind(check_size, _1, sz));

使用placeholders名字
- 头文件：functional

1	`using namespace std::placeholders;`

bind的参数
- 用 bind 绑定给定可调用对象中的参数或重新安排其顺序

//f是一个可调用对象，有5个参数
//g是一个有两个参数的可调用对象
auto g = bind(f, a, b, _2, c, _1);
//调用g(X,Y)会调用f(a,b,Y,c,X)

用 bind 重排参数顺序

//按单词长度由短至长排序
sort(words.begin(), words.end(), isShorter);
//按单词长度由长至短排序
sort(words.begin(), words.end(), bind(isShorter, _2, _1));

绑定引用对象：ref
- 函数ref：返回一个对象，包含给定的引用
- cref：生成一个保存 const 引用的类
- 头文件：functional

ostream &print(ostream &os, const string &s, char c)
{
    return os << s << c;
}
//错误：不能拷贝os
//for_each(words.begin(), words.end(), bind(print, os, _1, ''));
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ''));

10.4 再探迭代器

10.4.1 插入迭代器（insert iterator）

back_inserter：创建一个使用 push_back 的迭代器
front_inserter：创建一个使用 push_front 的迭代器
inserter：创建一个使用 inserter 的迭代器，函数第二个参数必须是一个指向给定容器的迭代器，元素被插入到给定迭代器所表示的元素之前

list<int> lst = {1, 2, 3, 4};
list<int> lst2, lst3;
//拷贝完成后，lst2包含4 3 2 1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
//lst3包含1 2 3 4
copy(lst.cbegin(), lst.cend(), inserter(lst3));

10.4.2 iostream 迭代器

istream_iterator操作

vector<int> vec;
istream_iterator<int> in_iter(cin);
istream_iterator<int> eof;
while (in_iter != eof)
{
	//后置递增运算读取流，返回迭代器的旧值
	//解引用迭代器，获得从流读取的前一个值
	vec.push_back(*in_iter++);
}

重写上述程序如下：

1 2	`istream_iterator<int> in_iter(cin), eof; vector<int> vec(in_iter, eof);`

用算法操作流迭代器

1 2	`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 << endl;

通过调用 copy 来打印 vec 中的元素

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

使用流迭代器处理类类型
- 重写1.6节（第21页）中的书店程序

istream_iterator<Sales_item> item_iter(cin), eof;
ostream_iterator<Sales_item> out_iter(cout, "\n");
//将第一笔记录保存在sum中，并读取下一条记录
Sales_item sum = *item_iter++;
while (item_iter != eof){
	if (item_iter->isbn() == sum.isbn())
		sum += *item_iter++;
	else {
		out_iter = sum;
		sum = *item_iter++;
	}
}
out_iter = sum;

10.4.3 反向迭代器

递增递减操作的含义颠倒
除 forward_list 外，其他容器都支持反向迭代器

1
2
3

vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for(auto r_iter = vec.crbegin(); r_iter != vec.crend(); ++r_iter)
    cout << *r_iter << endl;

反向迭代器和其他迭代器间的关系
- base 成员函数返回反向迭代器对应的普通迭代器

string line =  "FIRST,MIDDLE,LAST";
//打印第一个单词
auto comma = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), comma) << endl;
//打印最后一个单词
auto rcomma = find(line.crbegin(), line.crend(), ',');
//错误：将逆序输出单词的字符
//cout << string(line.crbegin(), rcomma) << endl;
//正确:
cout << string(rcomma.base(), line.cend()) << endl;

10.5 泛型算法结构

10.5.1 五类迭代器

输入迭代器（input iterator）
- 只用于顺序访问
- 只能用于单遍扫描算法
- 算法find和accumulate要求输入迭代器
- istream_iterator是一种输入迭代器
输出迭代器（output iterator）
- 只能用于单遍扫描算法
- 用作目的位置的迭代器
- copy函数的第三个参数就是输出迭代器
- ostream_iterator 类型是输出迭代器
前向迭代器（forward iterator）
- 只能在序列中沿一个反向移动
- 可多遍扫描
- replace要求前向迭代器
- forward_list上的迭代器是前向迭代器
双向迭代器（bidirectional iterator）
- 算法reverse要求双向迭代器
- 除forward_list外，其他标准都提供符合双向迭代器要求的迭代器
随机访问迭代器（random-access iterator）
- 算法sort要求随机访问迭代器
- array, deque, string, vector 的迭代器都是随机访问迭代器
- 用于访问内置数组元素的指针也是

10.5.2 算法形参模式

alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);

接受单个目标迭代器的算法
- 算法假定：按其需要写入数据，不管写入多少个元素都是安全的
- dest被绑定到一个插入迭代器或是一个ostream_iterator
接受第二个输入序列的算法
- 接受单独 beg2 的算法假定从 beg2 开始的序列与 bed 和 end所表示的范围至少一样大

10.5.3 算法命名规范

一些算法使用重载形式传递一个谓词
_if 版本的算法
- 接受谓词参数的算法都有附加的_if前缀

1 2	`find(beg, end, val); find(beg, end, pred);`

区分拷贝元素的版本和不拷贝版本
- 写到额外目的空间的算法都在名字后面附加一个_copy

1 2	`reverse_(beg, end); reverse_copy(beg, end, dest);`

10.6 特定容器算法

对于list 和forward，优先使用成员函数版本的算法而不是通用算法

lst.merge(lst2)
lst.merge(lst2, comp)
lst.remove(val)
lst.remove_if(pred)
lst.reverse()
lst.sort()
lst.sort(comp)
lst.unique()
lst.unique(pred)

splice成员

1	`lst.splice(args)或flst.splice_after(args)`

链表特有的操作会改变容器
- 链表版本的merge函数会销毁给定的链表
- 元素从指定的链表中删除，被合并到调用merge的链表对象中

编程

学习笔记 c++

本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议。转载请注明出处！

C++Primer 5th：第十一章关联容器上一篇

读书笔记：为什么精英都是时间控下一篇

C++Primer 5th：第十章 泛型算法

第十章 泛型算法

10.1 概述

10.2 初始泛型算法

10.2.1 只读算法

10.2.2 写容器元素的算法

10.2.3 重排容器元素的算法

10.3 定制操作

10.3.1 向算法传递函数

10.3.2 lambda表达式

10.3.3 lambda捕获和返回

10.3.4 参数绑定

10.4 再探迭代器

10.4.1 插入迭代器（insert iterator）

10.4.2 iostream 迭代器

10.4.3 反向迭代器

10.5 泛型算法结构

10.5.1 五类迭代器

10.5.2 算法形参模式

10.6 特定容器算法

C++Primer 5th：第十章泛型算法

第十章泛型算法