标准模板库介绍

1、    标准模板库，也叫 STL，是一个 C+ 容器类库，算法和迭代器。他提供许多基本算法，数据结构。STL 是一个通用库，即可以充份定制：几乎所有的 STL 组件都是模板。在你使用 STL 前，你必须了解模板的工作情况。容器和算法和许多类库一样，STL 包含容器类 - 可以包含其他对象的类。STL 包含向量类，链表类，双向队列类，集合类，图类，等等。他们中的每个类都是模板，能包含各种类型的对象。例如，你可以用 vector ，就象常规的 C 语言中的数组，除了 vector 不要你象数组那样考虑到动态内存分配的问题。   

2、 vector v(3);    / 定义一个有三个元素的向量类    v0 = 7;    v1 = v0 + 3;    v2 = v0 + v1;    / v0 = 7, v1 = 10, v2 = 17 STL 还包含了大量的算法。他们巧妙地处理储存在容器中的数据。你能够颠倒 vector 中的元素，只是简单使用 reverse 算法。   

3、60;reverse(v.begin(), v.end(); / v0 = 17, v1 = 10, v2 = 7在调用 reverse 的时候有两点要注意。首先，他是个全局函数，而不是成员函数。其次，他有两个参数，而不是一个：他操作一定范围的元素而不是操作容器。 在这个例子中他正好是对整个容器 V 操作。以上两点的原因是相同的：reverse 和其他 STL 算法一样，他们是通用的，也就是说， reverse 不仅可以用来颠倒向量的元素，也可以颠倒链表中元素的顺序。甚至可以对数组操作。下面的程序是合法的。    double A6 = 1.2, 1.3

4、, 1.4, 1.5, 1.6, 1.7 ;    reverse(A, A + 6);    for (int i = 0; i < 6; +i)    cout << "A" << i << " = " << Ai;这个例子也用到了范围，和我们上面的向量的例子一样：第一个参数是指向要操作的范围的头的指针，第二个参数是指向尾的指针。在这里，范围是 A, A + 6)。可能你注意到范

5、围的不对称。迭代器在上面的 C 数组的例子中，reverse 的参数类型是 double*。那么在 向量 或链表中参数又是什么呢？也就是说，究竟 reverse 是如何定义参数的，并且 v.begin() 和 v.end() 返回什么？问题的答案是 reverse 的参数是 迭代器 (iterators)。他是指针的概括。指针自己也是迭代器。这也是为什么可以颠倒数组中元素的顺序的原因。同样地，向量 定义了嵌套的类型 iterator 和 const_iterator。在上面的例子中， v.begin() 和 v.end() 返回的类型是 vector:iterator。还有一些迭代器，如 is

6、tream_iterator 和 ostream_iterator。他们根本不能和容器关联。迭代器的出现让算法和容器的分离成为可能。算法是模板，其类型依赖于迭代器，因此不会局限于单一的容器。例如，我们写个算法实现在一定范围的线性查找。下面就是 STL 的 find 算法。    template     InputIterator find(InputIterator first, InputIterator last, const T& value)     whi

7、le (first != last && *first != value) +first;    return first;    Find 有三个参数：两个迭代器定义范围，第三个是要查找的值。他遍历范围 first, last)，从头到尾的处理，在找到后停止或到范围的最后停止。First 和 last 定义为 InputIterator 类型，而 InputIterator 是个模板参数。也就是说，实际上没有一个真实的类型 InputIterator：当你调用 find 时，编译器用实际的类型去匹

8、配 InputIterator 和 T。如果 find 的两个参数中第一个实现是 int*，第三个实现是 int，那么你可以认为是在执行下面的函数。    int* find(int* first, int* last, const int& value)     while (first != last && *first != value) +first;    return first;    约束和类属实

9、参对于函数模板 (不仅仅是 STL 算法) 来说，一个非常重要的问题是：用什么样的参数类型去匹配模板参数才正确？为详细说明这个问题，我们举例：显然，int* 或 double* 能够代替 find 的模板参数 InputIterator。而 int 或 double 则不行。因此，有个显然的答案是：find 隐含地定义了对于类型的要求。无论用什么类型来实现 InputIterator，都必须提供一定的操作：他必须能够比较两个对象的大小，他必须能够进行增加操作。Find 不是仅有的一个有如此要求的 STL 算法。for_each 和 count 以及其他算法，都要满足上面的要求。这些要求很重要，

10、所以我们给他取个名字：我们将这一类类型条件叫约束 (concept)。我们称上面的约束为 Input Iterator。如果一个类型满足所有的要求，那么我们说这个类型符合该约束，或者说他是该约束的类属实参 (Model)。我们说 int* 是 Input Iterator 的类属实参，因为 int* 能提供 Input Iterator 所要求的所有操作。约束可不是 C+ 语言的一部份，在一个程序中你没有办法去定义一个约束，或者定义某类型是约束的类属实参。然而，约束是 STL 中的很重要的一部份。使用约束类属机制让我们在程序中从程序实现中分离接口成为可能。find 的作者只要考虑接口只针对于

11、Input Iterator 而不是去实现符合该约束的所有可能数据类型。同样，如果你要用 find，那么你只要确定你传递的参数是 Input Iterator 的类属实参就可以了。这就是为什么 find 和 reverse 能够在 list, vector, C 数组合其他类型中使用。用约束(的思想)去编程，而不是固定于某一特定类型，让程序重用组件和将组件组合使用。RefinementInput Iterator 实际上是相当弱的约束。也就是说，他只有少数几个要求。一个 Input Iterator 必须支持指针运算的子集(他必须能够通过操作符 operator+ 来增加 Input Iterator )，但是不需要其支持所有的指针算法。这对于 find 来说足够了，但是其他的一些算法就不是这样的，他们需要满足另外的条件。例如 Reverse 还要能够支持操作符 -。用术语来说，就是 reverse 的参数要是 Bidirectional Iterator 而非 Input Iterator。Bidirectional Iterator 的约束和 Input Iterator 的约束很相近：他只是简单地增加了一点另外的条件。Bidirectional Iterator 的类属实参是 Input terator 类属实参的子集：每个是 Bidirectional Itera