第6章　通用算法

算法是计算的核心。能够编写出在任何一种类型序列下工作的算法，就可以使程序更加简单和安全。算法在运行时的自定义的能力革新了软件开发方式。

众所周知，标准模板库（Standard Template Library, STL）作为标准C++库的子集，最初是用来设计通用算法（generic algorithm）的—以类型安全的方式生成处理任何一种类型值序列的代码。以前每当需要处理一个数据集合的时候，就得重复地手工编写代码。设计STL的目标就是对于几乎每个任务都使用预定义的算法，来代替这种手工编码的工作。然而，这种方法在提供方便的同时，也为初学者的学习带来了一些困难。在学习完本章后，读者就能自己做出判定，是特别喜欢采用这些算法来进行编程还是越学越困惑。大多数人起初抵制算法的使用，但随着时间的推移，越来越多的人逐渐喜欢使用它们了。

6.1　概述

除了一些别的东西，标准库中的通用算法还提供一个词汇表来描述各种解法。随着对算法的熟悉，读者就会获得一个新的词汇集合用来讨论现在正在做什么，这些词汇往往比以前所用的词汇具有更高层次的抽象。例如，没有必要说“这个循环在运行过程中从这赋值到那，……，噢，我知道了，是复制！”，而是只需简单扼要地用copy（）就可以了。这就是初学者在早期的计算机编程中所做的—创建高层次的抽象来解释正在做什么以及用更少的时间来说明怎样去做。一旦解决了怎样做的问题，并且将其转换成代码隐藏于算法代码中，就可以在需要时重复使用这些算法。

这里有一个怎样使用copy算法的程序例子：

copy（）算法的前两个参数表示输入序列的范围—此处是数组a。范围用一对指针表示。第1个指针指向该序列的第1个元素，第2个指针指向数组的超越末尾的（past the end）位置（即数组的最后一个元素的后面）。刚开始看起来可能觉得比较陌生，但这是传统的C语言的习惯用法，可以带来很大的便利。例如，这两个指针的差值就是序列中元素的个数。更重要的是，在实现copy时，第2个指针可以作为在序列中停止迭代的标记符。第3个参数代表输出序列的开始位置，在本例中输出序列是数组b。这里假设b表示的数组有足够的空间来接收要复制的元素。

如果copy（）算法仅限于处理整数，那就没什么新奇的地方了。它还可以用于任何一种类型的序列。下面的例子用来复制string对象：

这个例子引入了另一个算法equal（），仅当第1个序列的每一个元素与第2个序列的对应元素相等时（使用operator==（））返回true。这个例子对每个序列遍历了两次，一次用来复制，一次用来比较，而不是采用单一的一次循环！

通用算法能够达到如此灵活性是由于采用了函数模板。如果读者能将copy（）的实现想象成下面形式，这样差不多就对了：

说“差不多”是因为copy（）能够处理这样一类的序列，该序列由类似指针的任意类型来限制，例如迭代器。以此方式，copy（）可以用来复制vector：

第1个vector对象v1由数组a中的整数序列来初始化。第2个vector对象v2的定义，使用一个不同的能够为SIZE个元素分配空间的vector构造函数，并且将其初始化为0（整型的默认值）。

如同前面的数组例子，v2要有足够的空间来接收v1内容的复制。为了方便起见，使用一个特殊的库函数back_inserter（），该函数返回一个特殊类型的迭代器。利用这个迭代器就可以用插入元素的方式来代替重写这些元素，因此内存的大小就可以根据容器的需要自动扩大。

下面的例子使用了back_inserter（），因此无需像前面例子那样，在建立输出vector的对象v2时必须确定其大小。

back_inserter（）函数在头文件＜iterator＞中定义。我们将在下一章详细解释插入迭代器是如何工作的。

迭代器在本质上与指针相同，所以可以在标准库中以一种能够接受迭代器和指针两种参数的方式来实现算法。因此，copy（）的实现如下所示：

调用时无论采用哪种类型的参数，copy（）都假定它正确地实现了间接引用和自增运算符。如果没有，就会得到一个编译时错误。

6.1.1　判定函数

有时只想复制定义好的某个序列中的一个子集到另一个序列中，这个子集由只满足某个特殊条件的那些元素组成。为了达到这种灵活性，很多算法的调用序列允许提供一个判定函数（predicate），即一个基于某种标准返回布尔型值的函数。例如，只想提取整数序列中那些小于或等于15的数。copy（）的一种称为remove_copy_if（）的版本能够完成这一工作，如下所示：

remove_copy_if（）函数模板需要一些通常用来限定范围的指针，还增加了一个用户自选的判定函数。判定函数必须是指向一个函数^[1]的指针，这个指针有一个与序列中元素同类型的参数，并且必须返回一个布尔型的值。在这里，当参数大于15时，函数gt15返回true。remove_copy_if（）算法对输入序列的每个元素都应用gt15（），并且在向输出序列写入时忽略掉那些使判定函数产生真值的元素。

下面的程序展示了copy算法的另外一个变种：

与刚才忽略不满足判定函数的元素不同，此例中的replace_copy_if（）在输出一个序列时用一个固定的值来替代这些元素。输出结果是：

因为“read”是几个输入字符串中惟一一个含有字母e的字符串，所以用字符串“kiss”来取代该字符串，“kiss”是replace_copy_if（）调用中指定的最后一个参数。

replace_if（）算法改变原始序列相应位置中的内容，而不是向单独的输出序列中写数据，程序如下所示：

6.1.2　流迭代器

像任何好的软件库一样，标准C++库试图提供便捷的方法以自动完成常见的任务。在本章开始部分曾经提到过，可以使用通用算法来取代循环结构的设想。但是到目前为止，在提出的例子中仍然直接使用循环来打印输出结果。因为打印输出结果是最常见的任务之一，也可以期望有一种方法能够自动实现它。

这里引入流迭代器（stream iterator）的概念。一个流迭代器使用流作为输入或输出序列。例如，为了去除程序CopyInts2.cpp中的输出循环，可以像下面这样做：

在本例中，remove_copy_if（）的第3个参数位置上的输出序列b用一个输出流迭代器来代替，这个迭代器是在头文件＜iterator＞中声明的ostream_iterator类模板的一个实例。输出流迭代器重载其拷贝-赋值操作符，该重载操作符向相应的流写数据。ostream_iterator的这个特殊实例应用于输出流cout。每次remove_copy_if（）通过迭代器对cout赋一个来自输入序列a的整数。即迭代器向cout写入这个整数，并且随后还自动写入一个单独的字符串的一个实例，该字符串位于它的第2个参数位置上，在本例中是一个换行符。

用一个输出文件流来代替cout，就使得写文件同样很容易实现：

一个输入流迭代器允许算法从输入流中获得它的输入序列。这是靠构造函数和operator++（）从基础的流中读入下一个元素，以及重载operator*（）产生先前读入的值来完成的。因为算法需要两个指针来限定输入序列，所以可以用两种方式来构造istream_iterator，请看下面的程序：

程序中replace_copy_if（）的第1个参数，把一个istream_iterator的对象应用于含有整数的输入文件流。第2个参数使用istream_iterator类的默认构造函数。这个调用构造了istream_iterator的一个特殊值，用以指示文件的结束。这样，当第1个迭代器最终遇到物理文件的结尾时，它与istream_iterator＜int＞（）的值进行是否相等的比较，以便算法正确结束。注意，本例中完全避免了直接使用数组。

6.1.3　算法复杂性

使用某个软件库是对它的一种信任。用户相信（软件库的）实现者不仅能提供正确的功能，并且希望这些功能能够尽可能有效地执行。与其使用性能低下的算法，还不如自己来编写循环代码。

为了保证库实现的质量，C++标准不仅说明了算法应该做什么，而且说明了包括做得有多快，有时还包括应该使用多少存储空间。不能满足性能需求的算法也就是不符合标准的算法。算法的执行效率的度量称为复杂性（complexity）。

如果可能的话，C++标准会指定一个算法应该耗费的操作的精确次数。例如，count_if（）算法返回一个序列中满足给定判定函数的元素的个数。下面对count_if（）的调用，如果应用于类似本章前面的例子中的整数序列，会产生大于15的整数元素的个数：

因为count_if（）必须对每个元素仔细检查一次，也就是比较的次数与序列中元素的个数肯定相等。copy（）算法有相同的规格说明。

对于其他算法可以指定其最多执行的操作次数。find（）算法要搜索一个序列，直到遇到一个等于它的第3个参数的元素：

只要找到这样的元素就停止查找，并且返回一个指针，这个指针指向该元素第1次出现的位置。如果一个也没有找到，也返回一个指针，该指针指向超越序列末尾的（本例中是a+SIZE）位置。所以，find（）比较的次数最多等于序列中元素的个数。

有时候不能精确衡量一个算法将耗费运算的次数。在这种情况下，C++标准给出算法的渐近复杂性（asymptotic complexity），这是对算法在大的序列输入下执行性能与已知公式相比较的度量。一个好的例子是sort（）算法，C++标准称其花费“在平均情况下约nlogn次比较”（n是序列中元素的个数）^[2]。这样的复杂性度量似乎给人们一种关于一个算法的开销的“感觉”，不管怎么样，这至少是一种用来比较算法性能的有意义的基本依据。在下一章中读者将会看到，对于容器set的成员函数find（）来说，它具有对数级的复杂性，这意味着在大的集合中查找所花费的时间与元素个数的对数成正比。这比元素个数n要小的多，因此查找一个set最好使用它自己的成员函数find（）而不用一般的find（）算法。

[1]或者是和函数一样可被调用的东西，我们将很快能遇到。

[2]这是O（n log n）的英文简单表述，其表示对于大的n比较的次数与函数f（n）=n log n成正比。除非使用全局变量来烦琐地实现。