【笔记】《C++Primer》—— 第10章：泛型算法

这一章介绍了标准库中的常用几个算法和相关的一些重要介绍如10.3的Lambda表达式和10.4的迭代器介绍。这章也是非常重要的部分，这篇的篇幅比较长但值得好好看。

10.1 概述

• 泛型算法，也称“算法”，实现了一些经典算法的公共接口，而且可用于不同类型的元素与容器中
• 大多数的标准库算法都定义在头文件algorithm中，有些数值类的在numeric
• 通常来说算法本身并不依赖容器，也就不修改容器，对容器的访问与修改是通过算法调用所需的迭代器操作实现的，这保证了灵活性
• 算法虽然运行在迭代器上单需要依赖于元素类型所支持的操作

10.2 初识泛型算法

• 有些效果上不会改变范围内元素的算法称为只读算法
• find在范围内查找第一个与输入值相等的元素并返回指定这个元素的迭代器，否则返回end迭代器。需要支持==
• accumulate对范围内的元素求和，可以输入初始值，返回求和的值。需要支持+
• equal判断范围内的元素与目标序列是否相同，返回bool，需要支持==
• 所有只接受一个迭代器表示序列头的算法都假设目标序列至少和原序列一样长，如equal
• 一些算法向容器中已有的元素写入值，称为写容器算法
• fill将范围中的元素赋予某个值
• fill_n对从输入迭代器开始计数n个元素赋值
• copy将某范围的元素拷贝给另一个容器
• replace算法将范围中的与输入值相等的元素替换为另一个值
• replace_copy是一个copy版本的函数，需要额外输入一个迭代器，会将替换后的序列复制到那个迭代器而不改变原来的容器
• 写容器算法需要确保被写入的容器长度至少和需要写入的量一样长，为了规避这个风险可以用插入迭代器back_inserter解决，这点在后面详细说
• 一些算法会重排容器的元素，但不修改元素，称为重排容器元素算法
• sort通过混合排序算法进行排序，默认使得序列从小到大排序，需要实现<
• stable_sort内部采用稳定的排序算法，得到的序列内相同key的元素相对顺序不会改变
• unique将重复的元素移动到容器尾，除了list外不会删除那些被移走的元素，返回的迭代器指向新的容器尾(最后一个不重复的元素的位置)，可以用erase来删除剩余元素

10.3 定制操作

• 很多算法需要比较容器中的元素，如sort。比较默认是使用<或==实现的，有时候默认的运算符实现并不适合我们，可以通过在参数输入新的可调用对象(如函数)来自定义默认行为，这个参数称为“谓词”
• 谓词是一个可调用的表达式，标准库中的谓词分接受一个参数的一元谓词和接受两个参数的二元谓词。例如sort的谓词是二元谓词，可以用下述谓词修改sort的排序顺序 bool predicateTest(const int& a, const int& b) { // 默认的sort是内部调用了(a<b), 因此这个修改后排序顺序会相反 return a > b; } int main() { vector<int> a; // 第三个参数是一个二元谓词 sort(a.begin(), a.end(), predicateTest); return 0; }
• 有时候我们想要传入多于两个参数的谓词，例如我们需要更加复杂的find_if(条件查找)参数，其中一种解决方法是使用lambda表达式代替函数形式的谓词
• lambda有时被叫做匿名函数，是C++四种可调用对象之一(函数，函数指针，lambda，重载了调用运算符的类)，它可以理解为一个未命名的内联函数，特点是可以高效地运算并调用函数体外的一些局部变量
• lambda的格式如下，其中参数列表和返回类型是可以忽略的：
• [ 捕获列表 ] ( 参数列表 ) -> 返回类型 { 函数体 }
• 最基本的lambda可以如下，可以看到尽管函数的声明比较特别但是函数是调用和其他函数并无不同，可以猜想传递参数的方法也和普通函数并无不同，写进参数列表即可 auto lam = [] {return "lambda output!"; }; cout << lam();
• lambda特别的成分是捕获列表，在捕获列表中可以写入一些lambda所在函数的局部变量，然后用逗号分隔。被捕获的变量可以在lambda中使用如下 int main() { int a = 0; // 注意这里捕获了main函数的a，这个变量原本不属于lam auto lam = [a] {return a; }; cout << lam(); return 0; }
• 要注意捕获列表只作用域局部的非static变量，就如同一个单独的函数一样
• 关于捕获变量，lambda有值捕获，引用捕获，隐式捕获三种类型。其中值捕获和引用捕获区别就是写入捕获列表的名称是否加上引用符而已，效果也与引用变量相同
• 隐式捕获比较特别，通过在捕获列表中无名地写个=或&，可以告诉编译器推断函数所需要的捕获，其中=是值捕获推断，&是引用捕获推断
• 两种隐式捕获不能简单混用，如果声明了一种隐式捕获，那么剩余的只能用显式的传统的捕获，且显式捕获的类型还要和隐式捕获的不同，而且隐式捕获必须排列在显式捕获的前面 int main() { int a = 0, b = 1; // 隐式值捕获a auto lam1 = [=] {return a; }; // 隐式引用捕获a, 即此时a会是引用形式 auto lam2 = [&] {return a; }; // 混合捕获a(隐式的值捕获)，b(显式的引用捕获) auto lam3 = [=, &b] {return a + b; }; // 混合捕获a(显式的值捕获)，b(隐式的引用捕获) auto lam3 = [&, a] {return a + b; }; return 0; }
• 当我们希望lambda可以强制改变捕获的原值(即使是const)时，可以在参数列表后加mutable // 可变lambda auto lam1 = [a]() mutable {return a; };
• 当lambda函数体中存在不止一句return时，编译器将假定返回类型为void，此时要通过第六章讲到的尾置返回来指定所需的返回类型 // 尾置返回指定 auto lam1 = [a]()->int {int b = 1; return a+b; };
• lambda的能力十分大可玩性很高，但是要谨记lambda本质上意味着匿名的内联函数，不建议让lambda承担过于复杂的工作和捕获过多的内容，且尽可能避免lambda捕获指针或引用，因为lambda在创建时通过拷贝得到捕获的变量，如果保留了这个lambda到变量销毁时再调用可能会产生内存问题
• 有时候我们还是希望能用普通函数来代替lambda捕获变量的特性，可以用标准库头文件functional中的bind函数来处理
• bind函数接收一个可调用对象然后生成一个适配的新的可调用对象，利用它我们可以用适配器减少函数的所需的参数从而适配谓词
• bind函数的第一个参数是需要适配的可调用对象，后续参数是需要传递给这个调用对象的参数，返回值是适配后的可调用对象。其中传递给调用对象的参数中，可以用placeholder空间(此空间包括在std中)的_1,_2…占位符来标记，参数填入了_1代表生成的对象的第一个参数会被映射到这个位置，_2同理
• 利用bind可以实现参数的顺序交换，也可以实现一些动态的默认参数设置如下： #include<functional> using namespace std; // 指定命名空间placeholders using namespace std::placeholders; int test(int a, int b, int c) { return 0; } int main() { // 相当于调用test(1,2,3); auto f1 = bind(test, 1, _1, _2); f1(2, 3); // 相当于调用test(1,3,2); auto f2 = bind(test, 1, _2, _1); f2(2, 3); return 0; }
• 如果想要给bind传递引用，需要用ref函数或其常量版本cref将所需引用的对象再包装一下，这对于iostream很有用。这个函数同样处于functional中

10.4 再探迭代器

• 标准库头文件iterator中定义了四种基础迭代器，对他们的赋值操作将有不同的效果，分别是：

• 插入迭代器有三种类型，back_inserter,front_inserter,inserter，如其名分别是在容器后面插入，在前面插入和在参数位置插入在指向的元素之前
• 通过给算法传递不同的迭代器可以改变算法的效果 // 相当于push_front copy(vec1.begin(), vec1.end(), front_inserter(vec1)); // 相当于push_back copy(vec1.begin(), vec1.end(), back_inserter(vec2)); // 相当于push_back copy(vec1.begin(), vec1.end(), inserter(vec3, vec3.begin()));
• 注意对插入迭代器进行++,--是无意义的，只是为了统一通用而存在
• 流迭代器有两种类型，istream_iterator和ostream_iterator，它们使用输入输出运算符来处理流，输入流迭代器取值时从流得到一个值，输出流迭代器赋值时写入值到流中，输入流迭代器的空构造形式是流尽头的意思，可以用来判断边界 istream_iterator<int> in(cin); istream_iterator<int> eof; // 求和流里的int内容 int sum=accumulate(in, eof, 0); vector<int> vec; ostream_iterator<int> out(cout); // 用copy把向量内容复制(输出)到输出流 copy(vec.begin(), vec.end(), out);
• 对输入流迭代器的递增操作可以移动迭代器
• 反向迭代器前面说过各种操作与普通迭代器是相反的，通过传入反向迭代器到sort里可以实现逆序排列
• 反向迭代器可以通过bask成员函数转换为普通迭代器，从而适应一些更灵活的情况

• 移动迭代器在之后的章节再有介绍

10.5 泛型算法结构

• 泛型算法是利用迭代器对容器进行操作的，因此泛型算法们自然就对输入的迭代器有一定的要求
• 迭代器在标准库中大致分为五个抽象类别(并不对应某个具体的类，而是对类进行了分类)

• 除了输入输出迭代器是同级外，从上往下的迭代器级别逐步变高，功能逐步增强，排在下面的迭代器支持上层的所有操作
  • 输入迭代器用于读取序列中的元素，此类迭代器的状态不一定能保存下来，属于此类的迭代器必须支持：比较，递增移动，解引用(处于右侧)
  • 输出迭代器用于对元素进行改变，相当于输入迭代器的补集，注意我们只能对一个输出迭代器赋值一次，需要支持：递增移动，解引用(处于左侧)
  • 前向迭代器可以顺序读写元素，我们可以对此迭代器进行保存和多次使用
  • 双向迭代器可从正反两方向读写元素，也就是支持了递减移动运算符
  • 随机访问迭代器提供在常量时间内访问序列中任意元素的能力，同时支持了：比较迭代器之间位置的运算，迭代器与一个整数的位置加减运算，下标运算
• 知道了迭代器的分类后就可想而知算法大概会需要什么迭代器才能运行(迭代器错误时会报错并产生相应的错误提示)，除了forwardl_list外的容器都提供双向迭代器甚至更高级的迭代器
• 大多数算法不需要很高级的迭代器，需要注意的是sort需要随机访问迭代器，也即是需要从array,deque,vector等产生的迭代器
• 标准库算法都有一组参数规范，大多数算法都是以下四种形式之一：

• 其中算法目的位置的迭代器是单个的情况下，算法都假设可以安全地对元素进行写入而不会出现写入范围外的情况
• 标准库中能传递比较谓词的算法通常都是重载的同名函数，谓词是最后一个参数
• 接受一个参数参与内部运算的算法通常有一个xxx_if版本的函数，其接受的参数变为谓词
• 有拷贝版本的函数通常会增加指定目标拷贝的位置的新的参数并改名为xxx_copy

10.6 特定容器算法

• 链表类型list和forward_list由于实现方式的特别而拥有一些专有成员函数代替标准库算法，这些函数通常来说性能比标准库的通用函数更好，应尽可能使用

• 链表类型还额外定义了splice(捻接)算法，将两个链表连接在一起
• 由于链表自身的特性上述的算法才能有很高的性能优化，也因此它们的成员函数版本的算法会对容器进行改变(拼接)，最明显的效果就是链表版本的函数会改变低层的容器，例如unique在之前说到会将重复的元素放到容器尾，在链表版本中unique会将重复元素直接删除，也类似的merge在通用版本中仅仅是合并序列到目的迭代器中，在链表版本中合并后原始的链表将会消失