五、泛型算法（二）

本节主要分8个部分介绍一些常用泛型算法。

下列函数的参数列表中：

1）b、m和e是表示元素范围的迭代器。

2）b2是表示第二个序列开始位置的迭代器。e2表示第二个序列的末尾位置。如果没有e2,则假定b2指向的序列与b和e表示的序列一样大。

3）d是表示目的序列的迭代器。注意，算法需要向目的序列写入多少元素，目的序列必须保证能保存同样多的元素。通常，d可以与b相同，表示直接在原序列上进行修改。

4）val、val1、val2是一些要进行比较的值。

5）{a,b,c,...}是初始值列表，列表内元素不限个数。

6）p1和p2分别表示一元和二元谓词，分别接受一个和两个参数。

§I 只读算法

※ equal函数在结合反向迭代器后可用于判断一个字符串是否是回文字符串，代码如下：

§II 写算法

    注意，写算法无法改变底层容器的大小。

 对于remove（移除）和unique（去重）系列函数，其中的“删除”操作并未真正删除元素（即不改变容器大小，※泛型算法的特点），只是用要保留的元素覆盖了要删除的元素，最终使要保留的元素留在序列前端。

为了删除元素，可以在remove或unique的基础上结合容器的erase方法，实现删除元素（且改变容器大小）的效果。例如：

※ 注：unique函数只会对相邻的重复元素去重，若想对整个序列去重则需要先将序列排序。

§III 排序与划分算法

排序算法（默认升序）

partial_sort和nth_element都是未完成的快排。

划分算法

§IV 有序序列上的泛型算法（使用前要确保序列有序）

二分查找

集合算法

注：定义目的序列时需要先指定其容器大小。例如：

序列合并算法

inplace_merge用于一个序列中包含两段有序序列的情况，但实际情况中是需要预先找到两序列分界处的位置的，例如：

* §V 堆操作算法

§VI 排列算法

§VII 最大最小值算法

§VIII 数值算法

※ list容器特有的算法

注意，因list容器底层的数据结构是双向链表，故使用其成员函数版本的算法比使用通用泛型算法更好（因为泛型算法交换list的元素时代价太高）。下列常用list成员函数版本的算法：

因为此处的remove和unique本身就是list的成员函数，所以删除时会直接从容器中删除并改变容器大小。（注意与泛型算法中的remove和unique区别）