STL——算法简介

一、算法概观

以有限的步骤，解决逻辑或数学上的问题，这一专门科目我们称为算法。特定的算法往往搭配特定的数据结构，例如binary search tree（二叉搜索树）和 RB-tree 便是为了解决查找问题而发展出来的特殊数据结构。几乎可以说，特定的数据结构是为了实现某种特定的算法。本章所讨论的，是可施行于“无太多特殊条件限制”之空间中的某一段元素区间的算法。

1. 算法分析与复杂度表示O()

参见算法与数据结构相关书籍，如《算法设计与分析》《数据结构》等。

2. STL 算法总览

3. 质变算法mutating algorithms——会改变操作对象之值

所有的STL算法都作用在由迭代器[first, last) 所标示出来的区间上。所谓“质变算法”，是指运算过程中会更改区间内（迭代器所指）的元素内容。诸如拷贝（copy）、互换（swap）、替换（replace）、填写（fill）、删除（remove）、排列组合（permutation）、分割（partition）、随机重排（random shuffling）、排序（sort）等算法，都属此类。

4. 非质变算法nonmutating algorithms——不改变操作对象之值

所有的STL算法都作用在　　由迭代器[first, last) 所标示出来的区间上。所谓“非质变算法”，是指运算过程中不会更改区间内（迭代器所指）的元素内容。诸如查找（find）、匹配（search）、计数（count）、巡访（for_each）、比较（equal，mismatch）、寻找极值（max，min）等算法，都属此类。

5. STL算法的一般形式

所有泛型算法的前两个参数都是一对迭代器，通常由first和last形成一个“前闭后开”区间[first, last)。根据行进特性，迭代器可分为5类，每一个STL算法的声明，都表现出它所需要的最低程度的迭代器类型。例如find() 需要一个InputIterator，这是它的最低要求，但它也可以接受更高类型的迭代器，如ForwardIterator，BidirectionalIterator或RandomAccessIterator，在 STL——迭代器与traits编程技法 文章中阐述的，不论ForwardIterator或BidirectionalIterator或RandomAccessIterator也都是一种InputIterator。但如果你交给find() 一个OutputIterator，会导致错误。

将无效的迭代器传给某个算法，虽然是一种错误，却不保证能够在编译时期就被捕捉出来，因为所谓“迭代器类型”并不是真实的型别，它们只是function template的一种型别参数（type parameters）。

许多STL算法不只支持一个版本。这一类算法的某个版本采用缺省运算行为，另一个版本提供额外参数，接受外界传入一个仿函数(functor)，以便采用其他策略。

质变算法通常提供两个版本：一个是in-place（就地进行）版，就地改变其操作对象；另一个是copy（另地进行）版，将操作对象的内容复制一份副本，然后在副本上进行修改并返回该副本。copy版本总是以_copy作为函数名称后缀，如replace()和replace_copy()。并不是所有质变算法都有copy版，例如sort()就没有。如果我们希望以这类“无copy版本”之质变算法施行于某一段区间元素的副本身上，我们必须自行制作并传递那一份副本。

所有的数值（numeric）算法都实现于SGI<stl_numeric.h>之中，这是个内部文件，STL 规定用户必须包含的是上层<numeric>。其他STL算法都实现于SGI 的<stl_algo.h> 和 <stl_algobase.h>文件中，也都是内部文件；欲使用这些算法，必须先包含上层相关头文件<algorithm>。

二、算法的泛化过程 : "操作对象的型别+操作对象的标示法+区间目标的移动行为"三者的抽象化

如何将算法独立于其所处理的数据结构之外，关键在于，只要把操作对象的型别(使用模板template)加以抽象化，把操作对象的标示法(使用容器对应的迭代器来标示操作对象)和区间目标的移动行为(例如，一套STL容器的设计标准就规定要设计一个符合STL抽象算法操作行为的容器需要满足的条件，只有定义好了容器的设计标准，才有可能对“各种容器的不同操作行为”进行统一(也即抽象出)形成一个抽象行为，使得这个抽象行为在不同容器之上都能正常工作。而迭代器在这里便充当了容器和算法之间的胶着剂——通过迭代器(迭代器算法)取得容器中的对象，交予算法进行处理。)抽象化，整个算法也就在一个抽象层面上工作了。整个过程称为算法的泛型化，简称泛化。

三、算法实例

在《STL源码剖析》6.3节中，有针对各种算法，包括数值算法，基本算法，set相关算法，heap算法，以及其他多种常用算法的运用实例，详见书籍。

这里重点提一下下面几类算法：

（1）copy算法——强化效率无所不用其极

不论是对客户程序或是STL内部而言，copy()都是一个常常被调用的函数。由于copy进行的是复制操作，而复制操作不外乎运用assignment operator或copy constructor（copy算法用的是前者），但是某些元素型别拥有的是trivial(无价值的,微不足道的) assignment operator，因此，如果能够使用内存直接复制行为（例如C标准函数memove或memcpy），便能够节省大量时间。为此，SGI STL的copy算法用尽各种办法，包括函数重载、型别特性、偏特化等编程技巧，无所不用其极地加强效率。

注意,copy算法,需要特别注意区间重叠的情况:

如图6-3所示:

如果输入区间和输出区间完全没有重叠,当然毫无问题,否则便需特别注意.为什么图6-3第二种情况(可能)会产生错误?从源代码可得知,copy算法是一一进行元素的赋值操作,如果输出区间的起点位于输入区间内,copy算法便(可能)会在输入区间的(某些)元素尚未被复制之前,就覆盖其值,导致错误哦结果.在这里我一再使用"可能"这个字眼,是因为,如果copy算法根据其所接收的迭代器的特性决定调用memmove()来执行任务,就不会造成上述错误,因为memmove()会先将整个输入区间的内容复制下来,没有被覆盖的危险.

（2）sort算法

STL所提供的各式各样算法中，sort()是最复杂最庞大的一个。这个算法接受两个RandomAccessIterators（随机存取迭代器），然后将区间内的所有元素以渐增方式由小到大重新排列。第二个版本则允许用户指定一个仿函数，作为排序标准。STL的所有关系型容器都拥有自动排序功能（底层结构采用RB-tree），所以不需要用到这个sort算法。至于序列式容器中的stack、queue和priority-queue都有特别的出入口，不允许用户对元素排序。剩下vector、deque和list，前两者的迭代器属于RandomAccessIterator，适合使用sort算法，list的迭代器则属于BidirectionalIterators，不在STL标准之列的slist，其迭代器更属于RorwardIterator，都不适合使用sort算法。

STL 的sort算法，数据量大时采用Quick Sort，分段递归排序。一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来过大的额外负荷，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort。 关于Quick Sort和Insertion Sort算法，以及排序相关的其他算法，参考相关算法书籍。