[C++ 面试基础知识总结] 泛型算法[C++ 面试基础知识总结] 泛型算法

参考书籍：《c++ primer》

<a href="#c-%e9%9d%a2%e8%af%95%e5%9f%ba%e7%a1%80%e7%9f%a5%e8%af%86%e6%80%bb%e7%bb%93-%e6%b3%9b%e5%9e%8b%e7%ae%97%e6%b3%95">c 面试基础知识总结 泛型算法</a>

<a href="#%e7%9b%ae%e5%bd%95">目录</a>

<a href="#%e5%9f%ba%e7%a1%80%e6%b3%9b%e5%9e%8b%e7%ae%97%e6%b3%95">基础泛型算法</a>

<a href="#%e5%8f%aa%e8%af%bb%e7%ae%97%e6%b3%95">只读算法</a>

<a href="#%e5%86%99%e5%ae%b9%e5%99%a8%e7%ae%97%e6%b3%95">写容器算法</a>

<a href="#%e9%87%8d%e6%8e%92%e5%ae%b9%e5%99%a8%e5%85%83%e7%b4%a0%e7%ae%97%e6%b3%95">重排容器元素算法</a>

<a href="#%e5%ae%9a%e5%88%b6%e6%93%8d%e4%bd%9c">定制操作</a>

<a href="#%e5%90%91%e7%ae%97%e6%b3%95%e4%bc%a0%e9%80%92%e5%87%bd%e6%95%b0">向算法传递函数</a>

<a href="#lambda%e8%a1%a8%e8%be%be%e5%bc%8f">lambda表达式</a>

<a href="#%e5%8f%82%e6%95%b0%e7%bb%91%e5%ae%9a">参数绑定</a>

<a href="#%e7%89%b9%e6%ae%8a%e8%bf%ad%e4%bb%a3%e5%99%a8">特殊迭代器</a>

<a href="#%e6%8f%92%e5%85%a5%e8%bf%ad%e4%bb%a3%e5%99%a8">插入迭代器</a>

<a href="#iostream%e8%bf%ad%e4%bb%a3%e5%99%a8">iostream迭代器</a>

<a href="#%e5%8f%8d%e5%90%91%e8%bf%ad%e4%bb%a3%e5%99%a8">反向迭代器</a>

<a href="#5%e7%b1%bb%e8%bf%ad%e4%bb%a3%e5%99%a8">5类迭代器</a>

<a href="#%e9%93%be%e8%a1%a8%e7%9a%84%e7%89%b9%e5%ae%9a%e5%ae%b9%e5%99%a8%e7%ae%97%e6%b3%95">链表的特定容器算法</a>

泛型算法本身运行于迭代器之上，不会执行容器的操作，可以改变容器中保存元素的值，也可以在容器内移动元素，但永远不会直接添加或删除元素。插入迭代器是一种特殊的迭代器，当算法操作插入迭代器时，迭代器可以向容器添加元素，但算法本身永远不会做这样的事。

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

可以使用自定义的条件来给容器中的元素排序。下面以给几个两位数排序为例。

如果希望个位数字大小相同的数字，再按十位数字大小来排序，可以用稳定排序

调用普通函数：

调用lambda表达式可以得到同样结果

lambda表达式还可以省略参数列表和返回类型

用lambda表达式可以简化之前的排序的代码：

在上述vector的基础上，输出所有两位数四舍五入后的值

lambda表达式可以采取值捕获和引用捕获两种方式。

如果lambda函数体包含了除return以外的任何语句，则编译器会假定lambda返回void，如果要返回其他类型，需要显示指定出来。

由于函数有两个参数，而find_if只接受一元谓词，不能写成如下形式：

这个时候就需要用到bind函数

等价于

占位符的顺序是传递参数的顺序，例如之前的

如果改写为

则相当于颠倒了两个参数的顺序，最终得到的序列将会是从大到小的。

在bind函数中，非占位符参数是引用的时候，需要用ref函数或cref函数（常量）保护起来，写成以下形式

插入迭代器是一种迭代器适配器，它接收一个容器，生成一个迭代器，能实现给定容器添加元素。该迭代器调用容器操作来向给定容器的指定位置插入一个元素。插入迭代器有3种类型，只是插入位置存在差异。

需要注意的是，front_inserter会将插入元素序列颠倒过来，类似数据结果中链表的头插法。

通过流迭代器，可以用泛型算法从流对象读取数据以及向其写入数据。

反向迭代器是在容器中从尾元素向首元素反向移动的迭代器，rbegin函数返回的指向容器尾元素的迭代器，rend函数返回指向容器首元素之前位置的迭代器。crbegin和crend为相应的const型反向迭代器。

算法所要求的迭代器操作可以分为5个类别，每个算法都会对它的每个迭代器参数指明须提供哪类迭代器。

输入迭代器：只读不写，单遍扫描，只能递增，find和accumulate要求输入迭代器，istream_iterator是输入迭代器

输出迭代器：只写不读，单遍扫描，只能递增，copy的第三个参数和ostream_iterator就是输出迭代器

前向迭代器：可读写，多遍扫描，只能递增，replace要求前向迭代器，forward_list上的迭代器也是前向迭代器

双向迭代器：可读写，多遍扫描，可递增递减，reverse要求双向迭代器，list上的迭代器也支持双向迭代器

随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算，sort要求随机访问迭代器，array，deque，string，vector的迭代器和内置数组的指针都是随机访问迭代器。

由于链表类型不支持要求随机访问迭代器的通用算法，所以定义了一些类似的算法。

链表还定义了splice算法，以下2种写法等价，都是将l2所有元素移动到l尾部，并从l2中删除

如果只移动一个元素可以写成如下形式

注意：多数链表特有算法与其通用版本很相似，但不完全相同，链表特有版本的一个至关重要的区别是会改变底层的容器。例如merge算法将l2合并到l中后，会将l2的全部元素从l2列表中删除。但这些删除的元素依旧存在，只是存在于l中了。