在 STL 中，已经实现了了很多的算法，而且这些算法有些还是很有意思的。下面将我看到的一些列在下面：

1）Set 相关的操作，在 STL 里面，只对于 Set 有相应的 Union，Difference 的操作，这是因为 Set 的底层用的是 RBTree，已经是一个排好序的情况，而对于 HashSet 来说，由于底层是 HashTable ，并不是一个有序的序列，并没有提供类似的操作。在计算与集合有关的操作的时候，用类似于归并的方法，逐步的进行比较，并且按照情况移动 array1 或者是 array2 的 iterator 来进行操作。

2)  Quick Sort 操作。说起这个function，其实已经有很多的方法来实现了，只不过在 SGI 提供的版本里面，使用的是 IntroSort 来实现的。具体说来，首先，如果 QuickSort 递归调用的次数大于 16 次，那么意味着很有可能碰到了那种递归的怀情况，这样的情况下使用 Heap 排序（但是 Heap 排序) 。然后，如果剩下的元素少于 10 个的话，说明已经基本有序，这样的情况下采用 Insert 排序。这样使用 IntroSrot 之后，能够使总的时间降到 O(nlgn)。

3)  Permutation 操作。这个基本操作，主要就是 next permutation 和 previous permutation。在求的时候，主要使用了全排列里面较快的一种方法。对于 next_permutation来说，从后往前找，找到一对邻接的数，i和ii，使得 *i<*ii ，然后从后往前找到第一个 j，使得 *i < *j。然后 *i 与 *j 互换，然后把 ii 之后的数逆转一次。对于 previous_permutation来说，从后往前找，找到一对邻接的数，i和ii，使得 *i>*ii ，然后从后往前找到第一个 j，使得 *i > *j。然后 *i 与 *j 互换，然后把 ii 之后的数逆转一次。

不过，使用 STL 的好处要远远的大过仅仅实现的这些算法，更重要的是，能够提供给我们使用一个通用的算法，如果能够合理的使用已经提供的算法的话，那么在开发的时候梗住要得工作就是在设计处理问题的时候所需要的数据结构和算法了。实现，只是搭积木而已。

来自：http://alwaysgg.spaces.live.com/Blog/cns!6B5C7CAA27DF1612!1144.entry

分类： 算法艺术 设计模式