标准模板库介绍

作者:Wilbur Lang

标准模板库,也叫 STL,是一个 C++ 容器类库,算法和迭代器。他提供许多 基本算法,数据结构。STL 是一个通用库,即可以充份定制:几乎所有的 STL 组件都是模板。在你使用 STL 前,你必须了解模板的工作情况。

容器和算法

和许多类库一样,STL 包含容器类 - 可以包含其他对象的类。STL 包含向量 类,链表类,双向队列类,集合类,图类,等等。他们中的每个类都是模板,能包含 各种类型的对象。例如,你可以用 vector<int> ,就象常规的 C 语 言中的数组,除了 vector 不要你象数组那样考虑到动态内存分配的问题。

      vector<int> v(3);            // 定义一个有三个元素的向量类
      v[0] = 7;
      v[1] = v[0] + 3;
      v[2] = v[0] + v[1];          // v[0] == 7, v[1] == 10, v[2] == 17  

STL 还包含了大量的算法。他们巧妙地处理储存在容器中的数据。你能够颠倒 vector 中的元素,只是简单使用 reverse 算法。

      reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7

在调用 reverse 的时候有两点要注意。首先,他是个全局函数,而不是成员 函数。其次,他有两个参数,而不是一个:他操作一定范围的元素而不是操作容器。 在这个例子中他正好是对整个容器 V 操作。

以上两点的原因是相同的:reverse 和其他 STL 算法一样,他们是通用的,也就 是说, reverse 不仅可以用来颠倒向量的元素,也可以颠倒链表中元素的顺序。 甚至可以对数组操作。下面的程序是合法的。

      double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };
      reverse(A, A + 6);
      for (int i = 0; i < 6; ++i)
        cout << "A[" << i << "] = " << A[i];

这个例子也用到了范围,和我们上面的向量的例子一样:第一个参数是指向要操作的 范围的头的指针,第二个参数是指向尾的指针。在这里,范围是 [A, A + 6)。可能 你注意到范围的不对称。

迭代器

在上面的 C 数组的例子中,reverse 的参数类型是 double*。那么在 向量链表中参数又是什么呢?也就是说,究竟 reverse 是 如何定义参数的,并且 v.begin()v.end() 返回什么?

问题的答案是 reverse 的参数是 迭代器 (iterators)。他是指针的概括。 指针自己也是迭代器。这也是为什么可以颠倒数组中元素的顺序的原因。同样地,向量 定义了嵌套的类型 iteratorconst_iterator。在上面的例子中, v.begin()v.end() 返回的类型是 vector<int>::iterator。 还有一些迭代器,如 istream_iteratorostream_iterator。他们根本不能和容器关联。

迭代器的出现让算法和容器的分离成为可能。算法是模板,其类型依赖于迭代器,因此不会局 限于单一的容器。例如,我们写个算法实现在一定范围的线性查找。下面就是 STL 的 find 算法。

      template <class InputIterator, class T>
      InputIterator find(InputIterator first, InputIterator last, const T& value) {
          while (first != last && *first != value) ++first;
          return first;
      }

Find 有三个参数:两个迭代器定义范围,第三个是要查找的值。他遍历范围 [first, last),从头到尾的处理,在找到后停止或到范围的最后停止。

Firstlast 定义为 InputIterator 类型, 而 InputIterator 是个模板参数。也就是说,实际上没有一个真实的类型 InputIterator:当你调用 find 时,编译器用实际的类型 去匹配 InputIteratorT。如果 find 的两个参数 中第一个实现是 int*,第三个实现是 int,那么你可以认为是在执行 下面的函数。

      int* find(int* first, int* last, const int& value) {
          while (first != last && *first != value) ++first;
          return first;
      }

约束和类属实参

对于函数模板 (不仅仅是 STL 算法) 来说,一个非常重要的问题是:用什么样的参数 类型去匹配模板参数才正确?为详细说明这个问题,我们举例:显然,int*double* 能够代替 find 的模板参数 InputIterator。而 intdouble 则不行。因此,有个显然的答案是:find 隐含地定义了对于类型的要求。无论用什么类型来实现 InputIterator,都必须 提供一定的操作:他必须能够比较两个对象的大小,他必须能够进行增加操作。

Find 不是仅有的一个有如此要求的 STL 算法。for_eachcount 以及其他算法,都要满足上面的要求。这些要求很重要,所以我们给他取个名字:我们将这一 类类型条件叫约束 (concept)。我们称上面的约束为 Input Iterator。如果 一个类型满足所有的要求,那么我们说这个类型符合该约束,或者说他是该约束的类属实参 (Model)。我们说 int*Input Iterator 的类属实参,因为 int* 能提供 Input Iterator 所要求的所有操作。

约束可不是 C++ 语言的一部份,在一个程序中你没有办法去定义一个约束,或者 定义某类型是约束的类属实参。然而,约束是 STL 中的很重要的一部份。使用约束类属机制 让我们在程序中从程序实现中分离接口成为可能。find 的作者只要考虑 接口只针对于 Input Iterator 而不是去实现符合该约束的所有可能数据类型。 同样,如果你要用 find,那么你只要确定你传递的参数是 Input Iterator 的类属实参就可以了。这就是为什么 findreverse 能够在 list, vector, C 数组合其他类型中使用。用约束(的思想)去编程, 而不是固定于某一特定类型,让程序重用组件和将组件组合使用。

Refinement

Input Iterator 实际上是相当弱的约束。也就是说,他只有少数几个 要求。一个 Input Iterator 必须支持指针运算的子集(他必须能够通过操作符 operator++ 来增加 Input Iterator ),但是不需要其支持所有的 指针算法。这对于 find 来说足够了,但是其他的一些算法就不是这样的,他们 需要满足另外的条件。例如 Reverse 还要能够支持操作符 --。 用术语来说,就是 reverse 的参数要是 Bidirectional Iterator 而非 Input Iterator

Bidirectional Iterator 的约束和 Input Iterator 的约束很相近:他 只是简单地增加了一点另外的条件。Bidirectional Iterator 的类属实参是 Input terator 类属实参的子集:每个是 Bidirectional Iterator 类属实参的数据类型都是 Input Iterator 的类属实参。例如 Int* 即是 Bidirectional Iterator 的类属实参, 也是 Input Iterator 的类属实参。但是 istream_iterator就不同了,他只是 Input Iterator 的类属实参:他不能“适应”更严格的 Bidirectional Iterator 的要求。

我们这样来描述 Input IteratorBidirectional Iterator 的关系: Bidirectional IteratorInput Iteratorrefinement。 约束的 refinement 非常象 C++ 类的继承。我们用不同的词的主要原因是 refinement 用于约束而不是实际的类型。

除了我们上面提到的两个迭代器约束外,还有三个迭代器约束。这五个迭代器 约束是: Output Iterator, Input Iterator, Forward Iterator, Bidirectional IteratorRandom Access IteratorForward IteratorInput Iterator 的 refinement,Bidirectional Iterator 又是 Forward Iterator 的 refinement, Random Access IteratorBidirectional Iterator 的 refinement。(Output Iterator 和其他四个约束有关系,但是不是 refinement 层次上的关系:他不是 其他四个的 refinement,其他四个也不是他的 refinement。)

容器类和迭代器一样,也有约束的层次关系。所有的容器是 Container 的 类属实参。例如 Sequence 和 Associative Container,都是具体的容器。

STL 的其他部份

如果你理解了算法,迭代器,容器,那么你几乎就了解了 STL。但是 STL 还包含其他几个部 份的内容。

首先,STL 包含几个 “工具”:非常基本的在类库中不同地方出现的函数和 concept。 例如,Assignable 约束, 就描述了那些可以赋值 和类的拷贝操作的类型。几乎所有的 STL 类都是 Assignable 的类属实参。几乎所有的算法都要求其参数是 Assignable 的类属实参。

其次,STL 包括了底层的内存的分配和释放。Allocators 非常少见,你几乎可以忽略 他们。

最后,STL 包含了大量的 对象函数,也称为 functors。就象迭代器是指针的 一般形式一样,对象函数是函数的一般形式。对象函数有几种不同的约束,包括 Unary Function (一种只有一个参数的对象函数,如 f(x)) 和 Binary Function (一种有两个参数的对象函数,如 f(x, y))。对象函数对于编程来说很重要,因为 他如同对象类型的抽象一样作用于操作。