《C++ Primer》读书笔记 第十章 泛型算法

第十章 泛型算法

10.1 概述

  • 定义在<algorithm><numeric>
  • 泛型算法本身不会执行容器的操作,它们只会运行于迭代器上,一般不会改变底层容器的大小。

10.2 初识泛型算法

10.2.1 只读算法

find、count、accumulate、equal。

其中,accumulate 是累加,第三个参数是初始值,需要支持 + 运算。equal 操作两个序列,比较指定范围内的元素是否都相等。

1
string sum = accumulate(v.cbegin(), v.cend(), string(""));  // 不能改成""

10.2.2 写容器元素的算法

注意确保序列原大小至少不小于我们要求写入的元素数目。

操作两个序列时,有些接受三个迭代器,有些接受四个。

fill函数:在指定位置之间填充指定值。
fill_n函数:从指定位置开始填充指定数量的指定值。注意空间够不够。
copy函数:
replace函数:
replace_copy函数:

插入迭代器:向插入迭代器所指元素赋值将插入新值。

1
2
3
4
5
6
vector<int> vec;
fill_n(vec.begin(), 10, 0); // 错误
fill_n(back_inserter(vec), 10, 0); // 正确

replace(ilst.begin(), ilst.end(), 0, 42);
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

10.2.3 重排容器元素的算法

  • sort函数:排列。
  • unique函数:排列使不重复的元素出现在前面,返回第一个出现重复的元素的位置。(标准库算法是对迭代器而不是容器进行操作。)

10.3 定制操作

10.3.1 向算法传递函数

给 sort 等函数多传递一个参数,称作谓词(predicate):它是一个可调用的表达式,其返回结果是一个能用作条件的值。

稳定排序:stable_sort

10.3.2 lambda 表达式

find_if函数:第三个参数是一个谓词,返回第一个使谓词返回 true 的元素,否则返回尾迭代器。

可调用对象包括:

  • 函数
  • 函数指针
  • 重载了函数调用运算符的类
  • lambda 表达式
1
[capture list](parameter list) -> return type { function body }

其中,捕获列表是一个 lambda 所在函数中定义的局部变量的列表(通常为空)。我们可以忽略参数列表和返回类型,但必须永远包含捕获列表和函数体。

如果函数体包含任何单一 return 语句之外的内容,且未指定返回类型,则返回 void。

1
2
auto f = [] { return 42; };
stable_sort(words.begin(), words.end(), [](const string& a, const string& b) { return a.size() < b.size(); } );

如果 lambda 表达式还用到它所在函数中的局部非静态变量,必须将它写在捕获列表中。所以 find_if 可以写成:

1
2
3
auto wc = find_if(words.begin(), words.end(),
[sz] (const string &a)
{ return a.size() >= sz; });

for_each算法:接受一个可调用对象,对输入序列中每个元素调用此对象。

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

10.3.3 lambda 捕获和返回

变量的捕获方式也可以是值或引用。被捕获的变量的值是在 lambda 创建时拷贝,而不是调用时拷贝。

1
2
3
4
size_t v1 = 42;
auto f = [v1] { return v1; };
v1 = 0;
auto j = f(); // j 为 42

以引用方式捕获:

1
2
3
4
size_t v1 = 42;
auto f = [&v1] { return v1; };
v1 = 0;
auto j = f(); // j 为 0

引用捕获和返回引用一样,要确保被引用对象在 lambda 执行的时候是存在的。

当我们向一个函数传递一个 lambda 时,lambda 会立即执行。

我们也可以返回一个 lambda,但注意不能包含引用捕获。

尽量减少捕获的数据量,尽量避免捕获指针或引用。

可以使用&=表示隐式捕获,也可以混用隐式捕获和显式捕获。

1
2
[=]{const string &s) { return s.size() >= sz; });
[=, &os](const string &s) { os << s << c; });

如果希望能改变一个被捕获的变量的值,就必须在参数列表首加上关键字mutable。

1
2
3
4
size_t v1 = 42;
auto f = [v1] () mutable { return ++i; };
v1 = 0;
auto j = f(); // j 为 43

transform算法:将一个序列的元素依次做一个转化,放到另一个指定位置开始的序列中。

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

10.3.4 参数绑定

lambda 表达式适合使用次数少、代码少的应用场景,取代函数。但是不能直接把捕获列表作为谓词的参数放到函数的形参中。

解决方法:使用<functional>中定义的bind函数。

1
2
3
4
5
6
7
using std::placeholders::_1;
bool check_size(const string &s, string::size_type sz)
{
return s.size() >= sz;
}
auto wc = find_if(words.begin(), words.end(),
bind(check_size, _1, sz));

其中,_1是占位符。更一般的:

1
2
3
4
auto g = bind(f, a, b, _2, c, _1);

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

如果需要绑定引用,使用refcref函数:

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

旧版本的 bind1st 和 bind2nd 应被弃用。

10.4 再探迭代器

中还定义了:

  • 插入迭代器。
  • 流迭代器。
  • 反向迭代器。
  • 移动迭代器。

10.4.1 插入迭代器

三种类型:

  • back_inserter:创建一个使用 push_back 的迭代器。
  • front_inserter:创建一个使用 push_front 的迭代器。
  • inserter:创建一个使用 inserter 的迭代器,此函数接受第二个参数表示位置,元素被插入到它之前。
1
2
3
4
5
6
7
8
9
10
*it = val;
//inserter 插入迭代器相当于:
it = c.insert(it, val); // 指向新加入的元素
++it; // 指回原来的元素


list<int> lst = {1,2,3,4};
list<int> lst2, lst3;
copy(lst.cbegin(), lst.cend(), front_inserter(list2)); // 4,3,2,1,始终指向新首元素。
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin())); // 1,2,3,4

10.4.2 iostream 迭代器

  • istream_iterator要读写的类型必须定义了>>
  • ostream_iterator要读写的类型必须定义了<<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 构造1:使用流
istream_iterator<int> int_it(cin);
ifstream in("afile");
istream_iterator<string> str_it(in);

// 构造2:默认初始化
istream_iterator<int> int_eof; // 可得到尾后迭代器,一旦到文件尾或者IO错误,迭代器就与之相等。

// 用法1: 从流中读内容
while (int_it != int_eof)
ivec.push_back(*in_it++);

// 用法2: 两个迭代器结合用来构造容器
istream_iterator<int> in_iter(cin), eof;
vector<int> vec(in_iter, eof);

// 用法3:算法中使用
istream_iterator<int> in(cin), eof;
cout << accumulate(in, eof, 0) << endl;

注意:标准库不保证迭代器立即从流读取数据,允许使用懒惰求值,只保证在第一次解引用前完成从流中读数据的操作。

1
2
3
4
5
6
7
ostream_iterator<int> out_iter(cout, " ");
// 用法1:
for (auto e : vec)
out_iter = e; // 等效于 *out_iter++ = e;,但推荐别简写。

// 用法2:
copy(vec.begin(), vec.end(), out_iter);

10.4.3 反向迭代器

  • rbeginrendcrbegincrend
  • 反响迭代器需要--运算符。
  • 可以调用base()转化成正常迭代器。

10.5 泛型算法结构

10.5.1 5类迭代器

10.5.2 算法形参模式

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

10.5.3 算法命名规范

重载一个谓词:

1
2
unique(beg, end);
unique(beg, end, comp);

_if 版本:

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

区分拷贝不拷贝的版本:

1
2
reverse(beg, end);
reverse_copy(beg, end, dest);

同时包含上面两点:

1
2
remove_if(beg, end, pred);
remove_copy_if(beg, end, dest, pred);

10.6 特定容器算法

list 和 forward_list 还定义了:


通用版本的 sort 要求随机访问迭代器,不能用于它们。list 和 forward_list 应优先使用成员函数版本的算法。

另外还有splice成员:

有些链表版本的算法与通用版本有区别,主要是会改变底层结构。包括removeuniquemergesplice