Question

STL 包含很多处理容器的非成员函数，前面已经介绍过其中的一些：sort( )、copy( )、find( )、random_shuffle( )、set_union( )、set_intersection( )、set_difference( ) 和 transform( )。可能已经注意到，它们的总体设计是相同的，都使用迭代器来标识要处理的数据区间和结果的放置位置。有些函数还接受一个函数对象参数，并使用它来处理数据。

对于算法函数设计，有两个主要的通用部分。首先，它们都使用模板来提供泛型；其次，它们都使用迭代器来提供访问容器中数据的通用表示。因此，copy( ) 函数可用于将 double 值存储在数组中的容器、将 string 值存储在链表中的容器，也可用于将用户定义的对象存储在树结构中（如 set 所使用的）的容器。因为指针是一种特殊的迭代器，因此诸如 copy( ) 等 STL 函数可用于常规数组。

统一的容器设计使得不同类型的容器之间具有明显关系。例如，可以使用 copy( ) 将常规数组中的值复制到 vector 对象中，将 vector 对象中的值复制到 list 对象中，将 list 对象中的值复制到 set 对象中。可以用= =来比较不同类型的容器，如 deque 和 vector。之所以能够这样做，是因为容器重载的= =运算符使用迭代器来比较内容，因此如果 deque 对象和 vector 对象的内容相同，并且排列顺序也相同，则它们是相等的。

16.6.1 算法组

STL 将算法库分成 4 组：

• 非修改式序列操作；
• 修改式序列操作；
• 排序和相关操作；
• 通用数字运算。

前 3 组在头文件 algorithm（以前为 algo.h）中描述，第 4 组是专用于数值数据的，有自己的头文件，称为 numeric（以前它们也位于 algol.h 中）。

非修改式序列操作对区间中的每个元素进行操作。这些操作不修改容器的内容。例如，find( ) 和 for_each( ) 就属于这一类。

修改式序列操作也对区间中的每个元素进行操作。然而，顾名思义，它们可以修改容器的内容。可以修改值，也可以修改值的排列顺序。transform( )、random_shuffle( ) 和 copy( ) 属于这一类。

排序和相关操作包括多个排序函数（包括 sort( )）和其他各种函数，包括集合操作。

数字操作包括将区间的内容累积、计算两个容器的内部乘积、计算小计、计算相邻对象差的函数。通常，这些都是数组的操作特性，因此 vector 是最有可能使用这些操作的容器。

16.6.2 算法的通用特征

正如您多次看到的，STL 函数使用迭代器和迭代器区间。从函数原型可知有关迭代器的假设。例如，copy( ) 函数的原型如下：

因为标识符 InputIterator 和 OutputIterator 都是模板参数，所以它们就像 T 和 U 一样。然而，STL 文档使用模板参数名称来表示参数模型的概念。因此上述声明告诉我们，区间参数必须是输入迭代器或更高级别的迭代器，而指示结果存储位置的迭代器必须是输出迭代器或更高级别的迭代器。

对算法进行分类的方式之一是按结果放置的位置进行分类。有些算法就地完成工作，有些则创建拷贝。例如，在 sort( ) 函数完成时，结果被存放在原始数据的位置上，因此，sort( ) 是就地算法（in-place algorithm）；而 copy( ) 函数将结果发送到另一个位置，所以它是复制算法（copying algorithm）。transform( ) 函数可以以这两种方式完成工作。与 copy( ) 相似，它使用输出迭代器指示结果的存储位置；与 copy( ) 不同的是，transform( ) 允许输出迭代器指向输入区间，因此它可以用计算结果覆盖原来的值。

有些算法有两个版本：就地版本和复制版本。STL 的约定是，复制版本的名称将以_copy 结尾。复制版本将接受一个额外的输出迭代器参数，该参数指定结果的放置位置。例如，函数 replace( ) 的原型如下：

它将所有的 old_value 替换为 new_value，这是就地发生的。由于这种算法同时读写容器元素，因此迭代器类型必须是 ForwardIterator 或更高级别的。复制版本的原型如下：

在这里，结果被复制到 result 指定的新位置，因此对于指定区间而言，只读输入迭代器足够了。

注意，replace_copy( ) 的返回类型为 OutputIterator。对于复制算法，统一的约定是：返回一个迭代器，该迭代器指向复制的最后一个值后面的一个位置。

另一个常见的变体是：有些函数有这样的版本，即根据将函数应用于容器元素得到的结果来执行操作。这些版本的名称通常以_if 结尾。例如，如果将函数用于旧值时，返回的值为 true，则 replace_if( ) 将把旧值替换为新的值。下面是该函数的原型：

如前所述，谓词是返回 bool 值的一元函数。还有一个 replace_copy_if( ) 版本，您不难知道其作用和原型。

与 InputIterator 一样，Predicate 也是模板参数名称，可以为 T 或 U。然而，STL 选择用 Predicate 来提醒用户，实参应模拟 Predicate 概念。同样，STL 使用诸如 Generator 和 BinaryPredicate 等术语来指示必须模拟其他函数对象概念的参数。请记住，虽然文档可指出迭代器或函数符需求，但编译器不会对此进行检查。如果您使用了错误的迭代器，则编译器试图实例化模板时，将显示大量的错误消息。

16.6.3 STL 和 string 类

string 类虽然不是 STL 的组成部分，但设计它时考虑到了 STL。例如，它包含 begin( )、end( )、rbegin( ) 和 rend( ) 等成员，因此可以使用 STL 接口。程序清单 16.17 用 STL 显示了使用一个词的字母可以得到的所有排列组合。排列组合就是重新安排容器中元素的顺序。next_permutation( ) 算法将区间内容转换为下一种排列方式。对于字符串，排列按照字母递增的顺序进行。如果成功，该算法返回 true；如果区间已经处于最后的序列中，则该算法返回 false。要得到区间内容的所有排列组合，应从最初的顺序开始，为此程序使用了 STL 算法 sort( )。

程序清单 16.17 strgst1.cpp

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

注意，算法 next_permutation( ) 自动提供唯一的排列组合，这就是输出中“awl”一词的排列组合比“all”（它有重复的字母）的排列组合要多的原因。

16.6.4 函数和容器方法

有时可以选择使用 STL 方法或 STL 函数。通常方法是更好的选择。首先，它更适合于特定的容器；其次，作为成员函数，它可以使用模板类的内存管理工具，从而在需要时调整容器的长度。

例如，假设有一个由数字组成的链表，并要删除链表中某个特定值（例如 4）的所有实例。如果 la 是一个 list<int>对象，则可以使用链表的 remove( ) 方法：

调用该方法后，链表中所有值为 4 的元素都将被删除，同时链表的长度将被自动调整。

还有一个名为 remove( ) 的 STL 算法（见附录 G），它不是由对象调用，而是接受区间参数。因此，如果 lb 是一个 list<int>对象，则调用该函数的代码如下：

然而，由于该 remove( ) 函数不是成员，因此不能调整链表的长度。它将没被删除的元素放在链表的开始位置，并返回一个指向新的超尾值的迭代器。这样，便可以用该迭代器来修改容器的长度。例如，可以使用链表的 erase( ) 方法来删除一个区间，该区间描述了链表中不再需要的部分。程序清单 16.18 演示了这是如何进行的。

程序清单 16.18 listrmv.cpp

下面是程序清单 16.18 中程序的输出：

从中可知，remove( ) 方法将链表 la 从 10 个元素减少到 6 个元素。但对链表 lb 应用 remove( ) 后，它仍然包含 10 个元素。最后 4 个元素可任意处理，因为其中每个元素要么为 4，要么与已经移到链表开头的值相同。

尽管方法通常更适合，但非方法函数更通用。正如您看到的，可以将它们用于数组、string 对象、STL 容器，还可以用它们来处理混合的容器类型，例如，将矢量容器中的数据存储到链表或集合中。

16.6.5 使用 STL

STL 是一个库，其组成部分被设计成协同工作。STL 组件是工具，但也是创建其他工具的基本部件。我们用一个例子说明。假设要编写一个程序，让用户输入单词。希望最后得到一个按输入顺序排列的单词列表、一个按字母顺序排列的单词列表（忽略大小写），并记录每个单词被输入的次数。出于简化的目的，假设输入中不包含数字和标点符号。

输入和保存单词列表很简单。可以按程序清单 16.8 和程序清单 16.9 那样创建一个 vector<string>对象，并用 push_back( ) 将输入的单词添加到矢量中：

如何得到按字母顺序排列的单词列表呢？可以使用 sort( )，然后使用 unique( )，但这种方法将覆盖原始数据，因为 sort( ) 是就地算法。有一种更简单的方法，可以避免这种问题：创建一个 set<string>对象，然后将矢量中的单词复制（使用插入迭代器）到集合中。集合自动对其内容进行排序，因此无需调用 sort( )；集合只允许同一个键出现一次，因此无需调用 unique( )。这里要求忽略大小写，处理这种情况的方法之一是使用 transform( ) 而不是 copy( )，将矢量中的数据复制到集合中。使用一个转换函数将字符串转换成小写形式。

ToLower( ) 函数很容易编写，只需使用 transform( ) 将 tolower( ) 函数应用于字符串中的各个元素，并将字符串用作源和目标。记住，string 对象也可以使用 STL 函数。将字符串按引用传递和返回意味着算法不必复制字符串，而可以直接操作原始字符串。下面是函数 ToLower( ) 的代码：

一个可能出现的问题是：tolower( ) 函数被定义为 int tolower（int），而一些编译器希望函数与元素类型（即 char）匹配。一种解决方法是，使用 toLower 代替 tolower，并提供下面的定义：

要获得每个单词在输入中出现的次数，可以使用 count( ) 函数。它将一个区间和一个值作为参数，并返回这个值在区间中出现的次数。可以使用 vector 对象来提供区间，并使用 set 对象来提供要计算其出现次数的单词列表。即对于集合中的每个词，都计算它在矢量中出现的次数。要将单词与其出现的次数关联起来，可将单词和计数作为 pair<const string, int>对象存储在 map 对象中。单词将作为键（只出现一次），计数作为值。这可以通过一个循环来完成：

map 类有一个有趣的特征：可以用数组表示法（将键用作索引）来访问存储的值。例如，wordmap[“the”]表示与键“the”相关联的值，这里是字符串“the”出现的次数。因为 wordset 容器保存了 wordmap 使用的全部键，所以可以用下面的代码来存储结果，这是一种更具吸引力的方法：

因为 si 指向 wordset 容器中的一个字符串，所以*si 是一个字符串，可以用作 wordmap 的键。上述代码将键和值都放到 wordmap 映象中。

同样，也可以使用数组表示法来报告结果：

如果键无效，则对应的值将为 0。

程序清单 16.19 把这些想法组合在一起，同时包含了用于显示 3 个容器（包含输入内容的矢量、包含单词列表的集合和包含单词计数的映象）内容的代码。

程序清单 16.19 usealgo.cpp

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

这里的寓意在于，使用 STL 时应尽可能减少要编写的代码。STL 通用、灵活的设计将节省大量工作。另外，STL 设计者就是非常关心效率的算法人员，算法是经过仔细选择的，并且是内联的。