本文主要介绍STL中的稍微复杂的算法，主要涉及到的源码文件有 stl_algo.h 等。
在文件 stl_algo.h 中有很多常用的算法，包括查找、计数、旋转、删除、排序、合并、集合的交并等运算、求极值、排列组合等等，本文将按源码中各算法的实现顺序来介绍其具体实现细节。由于本文涉及到的算法和相关代码太多，在文中就尽量不贴出代码了，详细的代码及相关注释请参见 stl_algo.h。
1. 求三个数的中值 median
该算法比较简单，几个if-else语句就解决了。该函数只提供内部算法使用，并不对外提供接口，也不是STL标准中的算法，限于篇幅这里就不贴代码了。另外，该算法有两个版本，一个是使用默认的大小比较，另一个是可以指定比较函数。
2. for_each
也很简单，就是对区间 [first, last) 中的每一个元素执行一个给定函数的运算，就一行语句：
1
| |
其中 __f 为用户传入的一个指定的仿函数。该算法的返回值仍为传入的仿函数 __f 。
3. 查找 find
函数 find 查找特定值的元素，函数 find_if 查找经过用户的指定函数 func（STL中的pred函数） 运算后结果为 true 的元素。主要代码也只有一行：
1
| |
另外，关于find，考虑偏特化特性，还有在迭代器为随机存取迭代器时，每次循环进行4次判断和自增，这是所谓的 loop unrolling，在StackOverflow 上也有相关解释 questions-24295972。如果学过体系结构，应该也会提及循环展开的加速方法。
还有一个称为 adjacent_find 的查找算法，它查找序列区间中连续相等的两个元素的位置，返回其中第一个元素的迭代器。这个算法就没有做过多的优化和加速考虑了。
初次之外，在algo文件的最后部分，还有 find_first_of、find_end、`` 的算法，后面会按顺序介绍到。
4. 计数 count
该算法查找序列中值与给定值相等的元素的个数，即进行计数，返回为void，计数结果通过传入的引用参数 _Size& __n 来返回给用户，主要代码如下：
1 2 | |
以上这个是非STL标准的，另外还有一个版本返回值为迭代器的 difference_type 的偏特化版本，这个才是STL标准。
5. 搜索search
该算法实现的功能是在区间 [first1, last1) 中搜索是否存在与区间 [first2, last2) 中元素都对应相等的子序列，存在则返回区间1中与区间2匹配的起始位置，否则返回last1。基本思路也很简单，详见源码中我的注释。还有一个版本，可以指定判断条件，而不一定是对应相等这个条件。
另外，还有一个 search_n 的算法与之相似，只是这个算法搜索区间中是否存在长度为count且值均为val的子序列，存在则返回该子序列的起始位置，否则返回last。同样，它也有一个可以指定判断条件的重载版本。
6. 区间置换 swap_ranges
交换两个长度相等的区间：
1 2 | |
7. 区间变换运算 transform
对区间的每个元素进行opr运算，结果放在result中，仅这一点与 for_each 不同：
1 2 | |
还有一个版本是两个等长序列的运算，结果放在result中：
1 2 | |
注意该算法不需要传入第二个区间的last迭代器。
8. 替换 replace
将序列中所有值为oldval的元素值都改为newval：
1 2 | |
另外还有三个版本的替换： replace_if，判断条件可以自己指定，而不一定是相等；replace_copy，将修改后的结果存到一个新的序列中；replace_copy_if 是前两者的合体。
9.生成 generate
将序列中的元素的值按给定函数赋值：
1
| |
还有一个 generate_n 将序列中的前n个元素的值按给定函数赋值。
10.移除 remove
移除序列中值为val的元素，与 replace 算法类似，有4个版本，其中 remove 和 remove_if 分别通过 remove_copy、remove_copy_if 实现，只需将后者中的result参数设为该序列的起点first。
1 2 3 4 | |
11.unique和unique_copy
将区间的元素的值唯一化，即去掉相邻的重复的项。由于判断时是针对相邻的元素，所以一般需要结合sort使用，如果序列无序需要先对序列排序再进行唯一化。unique 的实现是调用 unique_copy 来实现的，只是将参数中result仍设为输入序列的first。
这个算法实现的过程中，有很多函数的调用，其中还有个问题没有解决（见代码中注释关于func4什么时候调用func3，func8什么时候调用func7的问题）。
12.反转 reverse
将区间中元素进行反转，一下是迭代器为随机存取迭代器时的实现：
1
| |
还有迭代器为双向迭代器的版本和非质变算法版本 reverse_copy。
13.旋转 rotate
该算法将区间 [first, last) 内的数据以 middle 为分界前后对调，即将[first,middle)+[middle,last) 变为 [middle,last)+[first,middle)。具体实施过程分为两步：首先将middle之后的元素全部调到middle之前，然后对middle之后的元素进行调整，使之按在middle之前时的顺序排列。具体步骤见源码注释，可以结合实例进行理解。该算法的时间复杂度为 $O(n)$，总体上只对序列进行了一次遍历。
另外，除了迭代器为前向迭代器的版本之外，还有迭代器为双向迭代器、随机访问迭代器的版本，分别对算法进行了特化和优化，详见源码注释。其中迭代器为随机访问迭代器时，算法稍微复杂些，但可以通过实例来简化理解。关于旋转算法的几种实现及其效率，可以参见这个 【Vector Rotation】，其中三种算法分别对应于STL中的随机迭代器版、前向迭代器版、双向迭代器版。虽然三种算法的复杂度均为线性的，但对于大量数据的旋转，还是会存在一些明显的效率区别的。
14.随机相关算法 random
random_shuffle 算法将序列随机重排，具体实现是对序列中每个位置的元素与序列中一个随机的元素进行对调：
1 2 | |
除了这个版本采用STL的random函数生成随机数的版本外，还有一个版本可以自己指定随机数生成函数。
random_sample_n 和 random_sample 都是从序列中随机选取n个样本，不同的是输入参数的形式、返回序列的有序性等，均非STL标准。
15.分割 partition
该算法的功能是将序列按条件分割成两个子序列（实际还是一个序列，只是按分割点分成了满足条件的部分和不满足条件的部分），返回分割点的位置。有迭代器为前向迭代器、双向迭代器的版本，保证稳定性的版本 stable_partition。
16. 排序 sort
排序算法是STL中最重要也最复杂的算法，总代码量大概是600行（实际上还不止，因为还有调用其他函数，如partition、merge等），占整个文件的1/5。该算法接受两个随机存取迭代器参数，将区间内的元素以渐增的顺序排列，重载版本则允许用户指定一个仿函数作为排序标准。STL的所有关系型容器都拥有自动排序功能（因为底层是RB-tree，属于有序搜索树），不需要用到这个sort算法，而序列式容器中的stack、queue和priority-queue都有特定的出入限制，不允许排序，剩下vector、deque和list、slist，前两者的迭代器都是随机存取迭代器，可以使用sort算法，而list是双向迭代器，slist是前向迭代器，都不适合使用sort算法，如果要对list或slist排序，需要使用list或slist自己实现的sort函数。
insert_sort 插入排序：在序列长度较小时（STL中设置的是长度小于16时），使用线性（而不是二分）插入排序。
sort 排序：在序列较长时，将序列分割为一个个小的区间，使得区间与区间之间整体上有序，然后使用线性插入排序对整体进行排序。（这与我们通常所理解的快速排序还是有很大区别的，最后整体上进行直接插入排序，实际效果与对每个子区间分别进行插入排序的效果是一样的，效率依然是非常高的）
stable_sort 稳定排序：实际上为归并排序，或称为merge sort，时间复杂度仍为 $O(nlogn)$。当子区间长度小于15时，让然是直接用插入排序；当子能够申请到O(n)的buffer时，借助buffer进行merge sort，否则使用inplace merge进行stable sort。而关于两种（with buffer和inplace的）merge的算法的内容，在后文中介绍。
partial_sort 部分排序：使用堆进行排序，功能是将序列 [first, last) 中的较小的 middle-first 个元素排序并放在区间 [first, middle) 中，而其余的 last-middle 个元素仍然是无序的。整个算法分为两个大的步骤，首先是将middle前的元素构建一个max-heap，将middle及之后的元素中比max-heap堆顶小的元素与堆顶对调并调整堆，从而得到middle前的元素都比middle后的元素小；然后使用heap sort对middle之前的元素进行排序。
17. 第n大的数 nth_element
该算法的功能是求一个序列中排行第n大的元素，具体实现时是使用 partition 将搜索范围逐步缩小，直到不足3个元素的区间后，进行insert-sort，最后第n大的元素就位于序列的第n个位置（该算法的迭代器也要求是随机存取的迭代器）。
18. 二分查找 binary_search
该系列算法的前提条件是序列已经有序，迭代器至少是ForwardIterators。
lower_bound ：二分查找 val，存在则返回指向该元素的迭代器，否则返回最小的不小于 val 的元素的迭代器，即在不破坏次序的情况下val可插入的第一个位置。
upper_bound ： 二分查找 val，存在则返回该元素的下一个元素的迭代器，否则返回最小的不小于 val的元素的迭代器，及在不破坏次序的前提下，val可插入的最后一个位置。
equal_range ：二分查找 val，返回值为 val 的区间 [i,j)，其中 i 是 lower_bound，而 j 是 upper_bound。
binary_search ：二分查找，找到返回true，否则返回false。实际上使用的是 lower_bound 来实现的。
19. 合并 merge
merge ：两个有序序列合并为一个有序序列，输入为5个参数，分别为两个序列的首尾迭代器、结果的首迭代器，算法返回结果序列的尾迭代器。基本思路是同时访问两个序列，取较小者放入结果序列并后移，最后必然是一个序列结束而另一个序列还有剩余元素，只需要将剩余部分copy的结果序列的尾部即可。
inplace_merge：原地将一个序列的两个有序子序列合并，实际上并不一定是原地进行，当可以申请到 O(n)的内存时借助buffer来进行merge，否则进行原地合并。原地合并的基本思路如下：先比较两个有序子序列的长度，将其中较长的序列分成两等分，取该序列的中间元素 first_cut 作为基准，然后得到第二个子序列以该基准分割的位置 second_cut，再然后进行原地旋转，将两个cut之间大于基准的数据旋转到两个cut之间小于基准的数据的后面，这样两个序列就被分成了两对有序子序列，最后分别将小于和大于基准的每对有序子序列进行merge。
20. 集合算法 set
由于集合的低层容器是红黑树，因此集合中的元素是有序的，这样在遍历两个集合时，复杂度不是O(mn)，而是O(m+n)。
includes：判断集合1是否包含集合2. 基本思想是，遍历两个集合，依次判断集合2中的元素是否均在集合1中出现了。
set_union：求两个集合的并集，如果两个集合中出现了相同的元素，则只算一次。
set_intersection：求两个集合的交集，即只保留两个集合中都存在的元素。
set_difference：两个集合的差集，即集合1中存在而集合2中不存在的元素。
set_symmetric_difference：两个集合的对称差，即集合1中存在而2中不存在的元素或集合2中存在而集合1中不存在的元素。
21. 求极值 max/min element
遍历整个区间，找到其中最大/小的元素的值，返回的是指向最大/小值的迭代器。
22. 排列的后继和前驱 next/pre permutation
关于该算法在之前的一篇文章中有详细介绍，请参见 全排列及某排列的后继的求解及其STL实现的分析 .
23. 找第一次出现的位置 find first of
在第一个序列中依次查找第二个序列中某个元素第一次出现的位置，使用一个双重循环，外循环遍历第一个序列，内循环遍历第二个序列，只要找到一个就立即返回在序列1中的位置，没有找到则返回序列1的尾迭代器。
24. 查找序列中的子序列 find end
在序列1中查找是否存在序列2这样的子序列，返回最后一次查找结果。还有一个版本是针对双向迭代器的类偏特化版本。
25. 判断序列是否为堆 is heap
判断一个序列是否为堆，即不断地判断父节点是否大于其孩子节点，如果不大于则返回false，否则返回true。
26. 判断序列是否有序 is sorted
判断一个序列是否有序，只需要遍历序列并判断相邻的两个元素的大小关系是否一致即可。
Well Done！终于看完了这些算法了！其中旋转、排序、查找、合并算法是稍微复杂的，且做了一些优化，是需要仔细阅读和体会的。 2014.11.09 更新。