前言

从本节开始，将会持续介绍 STL 中的算法（Algorithm）部分的内容，算法也是很庞大的一个组件，光是《STL 源码剖析》中列出的算法就有接近 80 个，大部分算法还有许多重载，十分繁杂，因此算法部分这里就只挑一部分具有代表性的算法进行分析，如：copy、sort、merge 等。

STL 中的大部分文件都放在这三个文件中：stl_numeric.h、stl_algobase.h、stl_algo.h，分别代表了数值算法、基础算法以及其他的大部分算法，其中关于集合（set）的一些算法如交集（intersection）、并集（union）等也放在了 stl_algo 中，而在 TinySTL 里，这部分内容被单独放进了 set_algo 里。

本节将主要介绍 STL 中的算法分类以及算法的泛化思想，算是一个开胃菜。

质变算法与非质变算法

所有的STL算法都作用在由迭代器 (first, last) 所标示出来的区间上。

所谓“质变算法（mutating algorithms）”，是指运算过程中会更改区间内（迭代器所指）的元素内容。诸如 copy、swap、replace、fill、remove、permutation、partition、random shuffing、sort 等算法，都属此类。因此这类算法接受的迭代器不能为 const_iterator。

所谓“非质变算法（nonmutating algorithms）”，是指运算过程中不会更改区间内（迭代器所指）的元素内容。诸如 find、search、count、for_each、equal、mismatch、max、min 等算法，都属此类。但由于模板参数并不能真正的确定一个迭代器是否为 const_iterator，因此如果传入的迭代器为非 const_iterator，这些算法依旧有可能改变区间内元素的值，如下面这个例子：

1
2
3
4
5
6
7
8
9
template<class T>
struct plus2 {
    void operator()(T& x) const {x += 2;}
};

int ia[] = {1,2,3,4,5};
vector<int> iv(ia, ia + sizeof(ia) / sizeof(int));

for_each(iv.begin(), iv.end(), plus2<int>());

传入了一个能够使得元素的值发生改变的仿函数，那么即使是非质变算法，还是能改变区间内元素的值。当然如果传入的是 const_iterator 这里依然会报错。

算法的泛化过程

正如 STL 一以贯之的特点那样，STL 的 Algorithm 最大的特点也在于其泛型思维，在 STL 的架构中，Container 与 Algorithm 是独立的，这意味着 Algorithm 可以适配 STL 中各种各样的容器而不用考虑它们的内部细节。极大地减少了二者的耦合而提高了算法的复用性。

《STL 源码剖析》中对于泛型思想以及 STL 的结构总结得高屋建瓴，十分到位。想要从宏观的视角理解 STL 的特点，还请阅读侯捷老师的原著，这里引用其中的部分内容，来继续介绍算法的泛化过程。

将一个叙述完整的算法转化为程序代码，是任何训练有素的程序员胜任愉快的工作。这些工作有的极其简单（例如循序查找）,有的稍微复杂（例如快速排序法），有的十分繁复（例如红黑树之建立与元素存取），但基本上都不应该形成任何难以跨越的障碍。

然而，如何将算法独立于其所处理的数据结构之外，不受数据结构的羁绊，思想层面就不是那么简单了。如何设计一个算法，使它适用于任何（或大多数）数据结构呢？换个说法，我们如何在即将处理的未知的数据结构（也许是 array，也许是 vector，也许是 list，也许是 deq…） 上，正确地实现所有操作呢？

关键在于，只要把操作对象的型别加以抽象化，把操作对象的标示法和区间目标的移动行为抽象化，整个算法也就在一个抽象层面上工作了。整个过程称为算法的泛型化（generalized），简称泛化。

让我们看看算法泛化的一个实例。以简单的循环查找为例，假设我们要写一个 find() 函数，在 arry 中寻找特定值。面对整数 array，我们的直觉反应是：

1
2
3
4
5
6
7
8
9
int* find(int* arrayHead, int arraySize, int value)
{
    for (int i = 0; i < arraySize; ++i>)
    {
        if (arrayHead[i] == value)
            break;
    }
    return &(arrayHead[i]);
}

该函数在某个区间内查找 value。返回的是一个指针，指向它所找到的第一个符合条件的元素；如果没有找到，就返回最后一个元素的下一位置（地址）。

“最后元素的下一位置”称为 end。返回 end 以表示“查找无结果”似乎是个可笑的做法。为什么不返回 null？因为，一如稍后即将见到的，end 指针可以对其他种类的容器带来泛型效果，这是 null 所无法达到的。

find() 的这种做法暴露了太多的实现细节（例如 arraySize），也因此太过依附特定容器。为了让 find() 适用于所有类型的容器，其操作应该更加抽象化些。让 find() 接受两个指针作为参数，标示出一个操作区间，就是很好的做法：

1
2
3
4
5
6
int* find(int* begin, int* end, int value)
{
    while (begin != end && *begin != value)
        ++begin;
    return begin;
}

这个函数在“前闭后开”区间 (begin, end) 内（不含 end；end 指向 array 最后元素的下一位置）查找 value，并返回一个指针，指向它所找到的第一个符合条件的元素；如果没有找到，就返回 end。由于 find() 函数之内并无任何操作是针对特定的整数 array 的，所以我们可以将它改成一个 template。

1
2
3
4
5
6
7
8
9
template <class T>
T* find(T* begin, T* end, const T& value)
{
    // 注意，以下用到了 operator!=，operator++，operator*
    while (begin != end && *begin != value)
        ++begin;
    // 注意，以下返回操作会引发 copy 行为
    return begin;
}

将值传递改为引用传递可以减少不必要的拷贝，在对象很大时效率会提升很多。

这样的 find() 很好，几乎适用于任何容器，只要该容器允许指针指入，而指针们又都支持以下四种 find() 函数中出现的操作行为：

  • inequality（判断不相等）操作符
  • dereference（提领，取值）操作符
  • prefix increment（前置式递增）操作符
  • copy（复制）行为（以便产生函数的返回值）

C++ 有一个极大的优点便是，几乎所有东西都可以改写为程序员自定义的形式或行为。是的，上述这些操作符或操作行为都可以被重载（ overloaded），既然如此，何必将 find 限制为只能使用指针呢？何不让支持以上四种行为的、行为很像指针的“某种对象”都可以被 find() 使用呢?如此一来，find() 函数便可以从原生（native）指针的思想框框中跳脱出来。如果我们以一个原生指针指向某个list，则对该指针进行 ++ 操作并不能使它指向下一个串行节点。但如果我们设计一个 class，拥有原生指针的行为，并使其 ++ 操作指向 list 的下一个节点，那么 find() 就可以施行于 list 容器身上了。

这便是迭代器的观念，迭代器是一种行为类似于指针的对象，换句话说，是一种 smart pointers。现在我们将 find() 函数内的指针以迭代器取代，重新写过：

1
2
3
4
5
6
7
template <class Iterator, class T>
Iterator find(Iterator begin, Iterator end, const T& value)
{
    while (begin != end && *begin != value)
        ++begin;
    return begin;
}

这便是一个完全泛型化的 find() 函数。你可以在任何 C++ 标准库的某个头文件里看到它，长相几乎一模一样. SGI STL 把它放在 <stl_algo.h> 之中。

有了这样的观念与准备，再来看 STL 各式各样的泛型算法，就会轻松许多。

STL 算法的一般形式

所有泛型算法的前两个参数都是一对迭代器（iterators） ，通常称为 first 和 last，用以标示算法的操作区间。STL 习惯采用前闭后开区间（或称左涵盖区间）表示法，写成 [first,last)，表示区间涵盖 first 至 last （不含last）之间的所有元素。当时 first==last，上述所表现的便是一个空区间。

这个 [first, last) 区间的必要条件是，必须能够经由 increment 操作运算符的反复运用，从 first 到达 last。

根据不同的特性，迭代器可分为五类，详见 Iterator-2。每一个 STL 算法的声明，都表现出它所需要的最低程度的迭代器类型。例如 find() 需要一个 InputIterator，这是它的最低要求，但它也可以接受更高类型的迭代器，如 Forwardlterator，Bicirectionalterator 或 RandonAccesslterator。如果交给 find() 一个 Outputterator，会导致错误。

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

许多 STL 算法不只支持一个版本，这一类算法的某个版本采用缺省运算行为，另一个版本提供额外参数，接受外界传人一个仿函数，以便采用其他策略。例如 unique() 缺省情况下使用 equality 操作符来比较两个相邻元素，但如果这些元素的型别并未供应 equality 操作符，或如果用户希望定义自己的 equality 操作符，便可以传一个仿函数给另一版本的 unique。有些算法干脆将这样的两个版本分为两个不同名称的实体，附从的那个总是以 _if 作为尾词，例如 find_if()。另一个例子是 replace()，使用内建的 equality 操作符进行比对操作，replace_if() 则以接收到的仿函数进行比对行为。

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