Question

STL 提供了一组表示容器、迭代器、函数对象和算法的模板。容器是一个与数组类似的单元，可以存储若干个值。STL 容器是同质的，即存储的值的类型相同；算法是完成特定任务（如对数组进行排序或在链表中查找特定值）的处方；迭代器能够用来遍历容器的对象，与能够遍历数组的指针类似，是广义指针；函数对象是类似于函数的对象，可以是类对象或函数指针（包括函数名，因为函数名被用作指针）。STL 使得能够构造各种容器（包括数组、队列和链表）和执行各种操作（包括搜索、排序和随机排列）。

Alex Stepanov 和 Meng Lee 在 Hewlett-Packard 实验室开发了 STL，并于 1994 年发布其实现。ISO/ANSI C++委员会投票同意将其作为 C++标准的组成部分。STL 不是面向对象的编程，而是一种不同的编程模式——泛型编程（generic programming）。这使得 STL 在功能和方法方面都很有趣。关于 STL 的信息很多，无法用一章的篇幅全部介绍，所以这里将介绍一些有代表性的例子，并领会泛型编程方法的精神。先来看几个具体的例子，让您对容器、迭代器和算法有一些感性的认识，然后再介绍底层的设计理念，并简要地介绍 STL。附录 G 对各种 STL 方法和函数进行了总结。

16.3.1 模板类 vector

第 4 章简要地介绍了 vector 类，下面更详细地介绍它。在计算中，矢量（vector）对应数组，而不是第 11 章介绍的数学矢量（在数学中，可以使用 N 个分量来表示 N 维数学矢量，因此从这方面讲，数学矢量类似一个 N 维数组。然而，数学矢量还有一些计算机矢量不具备的其他特征，如内乘积和外乘积）。计算矢量存储了一组可随机访问的值，即可以使用索引来直接访问矢量的第 10 个元素，而不必首先访问前面第 9 个元素。所以 vector 类提供了与第 14 章介绍的 valarray 和 ArrayTP 以及第 4 章介绍的 array 类似的操作，即可以创建 vector 对象，将一个 vector 对象赋给另一个对象，使用[ ]运算符来访问 vector 元素。要使类成为通用的，应将它设计为模板类，STL 正是这样做的——在头文件 vector（以前为 vector.h）中定义了一个 vector 模板。

要创建 vector 模板对象，可使用通常的<type>表示法来指出要使用的类型。另外，vector 模板使用动态内存分配，因此可以用初始化参数来指出需要多少矢量：

由于运算符[ ]被重载，因此创建 vector 对象后，可以使用通常的数组表示法来访问各个元素：

分配器

与 string 类相似，各种 STL 容器模板都接受一个可选的模板参数，该参数指定使用哪个分配器对象来管理内存。例如，vector 模板的开头与下面类似：

如果省略该模板参数的值，则容器模板将默认使用 allocator<T>类。这个类使用 new 和 delete。

程序清单 16.7 是一个要求不高的应用程序，它使用了这个类。该程序创建了两个 vector 对象——一个是 int 规范，另一个是 string 规范，它们都包含 5 个元素。

程序清单 16.7 vect1.cpp

程序清单 16.7 中程序的运行情况如下：

该程序使用 vector 模板只是为方便创建动态分配的数组。下一节将介绍一个使用更多类方法的例子。

16.3.2 可对矢量执行的操作

除分配存储空间外，vector 模板还可以完成哪些任务呢？所有的 STL 容器都提供了一些基本方法，其中包括 size( )——返回容器中元素数目、swap( )——交换两个容器的内容、begin( )——返回一个指向容器中第一个元素的迭代器、end( )——返回一个表示超过容器尾的迭代器。

什么是迭代器？它是一个广义指针。事实上，它可以是指针，也可以是一个可对其执行类似指针的操作——如解除引用（如 operator*( )）和递增（如 operator++( )）——的对象。稍后将知道，通过将指针广义化为迭代器，让 STL 能够为各种不同的容器类（包括那些简单指针无法处理的类）提供统一的接口。每个容器类都定义了一个合适的迭代器，该迭代器的类型是一个名为 iterator 的 typedef，其作用域为整个类。例如，要为 vector 的 double 类型规范声明一个迭代器，可以这样做：

假设 scores 是一个 vector<double>对象：

则可以使用迭代器 pd 执行这样的操作：

正如您看到的，迭代器的行为就像指针。顺便说一句，还有一个 C++11 自动类型推断很有用的地方。例如，可以不这样做：

而这样做：

回到前面的示例。什么是超过结尾（past-the-end）呢？它是一种迭代器，指向容器最后一个元素后面的那个元素。这与 C-风格字符串最后一个字符后面的空字符类似，只是空字符是一个值，而“超过结尾”是一个指向元素的指针（迭代器）。end( ) 成员函数标识超过结尾的位置。如果将迭代器设置为容器的第一个元素，并不断地递增，则最终它将到达容器结尾，从而遍历整个容器的内容。因此，如果 scores 和 pd 的定义与前面的示例中相同，则可以用下面的代码来显示容器的内容：

所有容器都包含刚才讨论的那些方法。vector 模板类也包含一些只有某些 STL 容器才有的方法。push_back( ) 是一个方便的方法，它将元素添加到矢量末尾。这样做时，它将负责内存管理，增加矢量的长度，使之能够容纳新的成员。这意味着可以编写这样的代码：

每次循环都给 scores 对象增加一个元素。在编写或运行程序时，无需了解元素的数目。只要能够取得足够的内存，程序就可以根据需要增加 scores 的长度。

erase( ) 方法删除矢量中给定区间的元素。它接受两个迭代器参数，这些参数定义了要删除的区间。了解 STL 如何使用两个迭代器来定义区间至关重要。第一个迭代器指向区间的起始处，第二个迭代器位于区间终止处的后一个位置。例如，下述代码删除第一个和第二个元素，即删除 begin( ) 和 begin( )+1 指向的元素（由于 vector 提供了随机访问功能，因此 vector 类迭代器定义了诸如 begin( )+2 等操作）：

如果 it1 和 it2 是迭代器，则 STL 文档使用[p1, p2) 来表示从 p1 到 p2（不包括 p2）的区间。因此，区间[begin( ), end( )]将包括集合的所有内容（参见图 16.3），而区间[p1, p1) 为空。[ ) 表示法并不是 C++的组成部分，因此不能在代码中使用，而只能出现在文档中。

注意：

区间[it1, it2) 由迭代器 it1 和 it2 指定，其范围为 it1 到 it2（不包括 it2）。

insert( ) 方法的功能与 erase( ) 相反。它接受 3 个迭代器参数，第一个参数指定了新元素的插入位置，第二个和第三个迭代器参数定义了被插入区间，该区间通常是另一个容器对象的一部分。例如，下面的代码将矢量 new_v 中除第一个元素外的所有元素插入到 old_v 矢量的第一个元素前面：

图 16.3 STL 的区间概念

顺便说一句，对于这种情况，拥有超尾元素是非常方便的，因为这使得在矢量尾部附加元素非常简单。下面的代码将新元素插入到 old.end( ) 前面，即矢量最后一个元素的后面。

程序清单 16.8 演示了 size( )、begin( )、end( )、push_back( )、erase( ) 和 insert( ) 的用法。为简化数据处理，将程序清单 16.7 中的 rating 和 title 组合成了一个 Review 结构，并使用 FillReview( ) 和 ShowReview( ) 函数来输入和输出 Review 对象。

程序清单 16.8 vect2.cpp

程序清单 16.8 中程序的运行情况如下：

16.3.3 对矢量可执行的其他操作

程序员通常要对数组执行很多操作，如搜索、排序、随机排序等。矢量模板类包含了执行这些常见的操作的方法吗？没有！STL 从更广泛的角度定义了非成员（non-member）函数来执行这些操作，即不是为每个容器类定义 find( ) 成员函数，而是定义了一个适用于所有容器类的非成员函数 find( )。这种设计理念省去了大量重复的工作。例如，假设有 8 个容器类，需要支持 10 种操作。如果每个类都有自己的成员函数，则需要定义 80（8*10）个成员函数。但采用 STL 方式时，只需要定义 10 个非成员函数即可。在定义新的容器类时，只要遵循正确的指导思想，则它也可以使用已有的 10 个非成员函数来执行查找、排序等操作。

另一方面，即使有执行相同任务的非成员函数，STL 有时也会定义一个成员函数。这是因为对有些操作来说，类特定算法的效率比通用算法高，因此，vector 的成员函数 swap( ) 的效率比非成员函数 swap( ) 高，但非成员函数让您能够交换两个类型不同的容器的内容。

下面来看 3 个具有代表性的 STL 函数：for_each( )、random_shuffle( ) 和 sort( )。for_each( ) 函数可用于很多容器类，它接受 3 个参数。前两个是定义容器中区间的迭代器，最后一个是指向函数的指针（更普遍地说，最后一个参数是一个函数对象，函数对象将稍后介绍）。for_each( ) 函数将被指向的函数应用于容器区间中的各个元素。被指向的函数不能修改容器元素的值。可以用 for_each( ) 函数来代替 for 循环。例如，可以将代码：

替换为：

这样可避免显式地使用迭代器变量。

Random_shuffle( ) 函数接受两个指定区间的迭代器参数，并随机排列该区间中的元素。例如，下面的语句随机排列 books 矢量中所有元素：

与可用于任何容器类的 for_each 不同，该函数要求容器类允许随机访问，vector 类可以做到这一点。

sort( ) 函数也要求容器支持随机访问。该函数有两个版本，第一个版本接受两个定义区间的迭代器参数，并使用为存储在容器中的类型元素定义的<运算符，对区间中的元素进行操作。例如，下面的语句按升序对 coolstuff 的内容进行排序，排序时使用内置的<运算符对值进行比较：

如果容器元素是用户定义的对象，则要使用 sort( )，必须定义能够处理该类型对象的 operator<( ) 函数。例如，如果为 Review 提供了成员或非成员函数 operator<( )，则可以对包含 Review 对象的矢量进行排序。由于 Review 是一个结构，因此其成员是公有的，这样的非成员函数将为：

有了这样的函数后，就可以对包含 Review 对象（如 books）的矢量进行排序了：

上述版本的 operator<( ) 函数按 title 成员的字母顺序排序。如果 title 成员相同，则按照 rating 排序。然而，如果想按降序或是按 rating（而不是 title）排序，该如何办呢？可以使用另一种格式的 sort( )。它接受 3 个参数，前两个参数也是指定区间的迭代器，最后一个参数是指向要使用的函数的指针（函数对象），而不是用于比较的 operator<( )。返回值可转换为 bool，false 表示两个参数的顺序不正确。下面是一个例子：

有了这个函数后，就可以使用下面的语句将包含 Review 对象的 books 矢量按 rating 升序排列：

注意，与 operator<( ) 相比，WorseThan( ) 函数执行的对 Review 对象进行排序的工作不那么完整。如果两个对象的 title 成员相同，operator<( ) 函数将按 rating 进行排序，而 WorseThan( ) 将它们视为相同。第一种排序称为全排序（total ordering），第二种排序称为完整弱排序（strict weak ordering）。在全排序中，如果 a<b 和 b<a 都不成立，则 a 和 b 必定相同。在完整弱排序中，情况就不是这样了。它们可能相同，也可能只是在某方面相同，如 WorseThan( ) 示例中的 rating 成员。所以在完整弱排序中，只能说它们等价，而不是相同。

程序清单 16.9 演示了这些 STL 函数的用法。

程序清单 16.9 vect3.cpp

程序清单 16.9 中程序的运行情况如下：

16.3.4 基于范围的 for 循环（C++11）

第 5 章说过，基于范围的 for 循环是为用于 STL 而设计的。为复习该循环，下面是第 5 章的第一个示例：

在这种 for 循环中，括号内的代码声明一个类型与容器存储的内容相同的变量，然后指出了容器的名称。接下来，循环体使用指定的变量依次访问容器的每个元素。例如，对于下述摘自程序清单 16.9 的语句：

可将其替换为下述基于范围的 for 循环：

根据 book 的类型（vector<Review>），编译器将推断出 x 的类型为 Review，而循环将依次将 books 中的每个 Review 对象传递给 ShowReview( )。

不同于 for_each( )，基于范围的 for 循环可修改容器的内容，诀窍是指定一个引用参数。例如，假设有如下函数：

可使用如下循环对 books 的每个元素执行该函数：