第19章 STL集合类

标准模板库（STL）向程序员提供了一些容器类，以便在应用程序中进行频繁而快速的搜索。std::set和std::multiset用于存储一组经过排序的元素，其查找元素的复杂度为对数，而unordered集合的插入和查找时间是固定的。

在本章中，您将学习：

• 如何使用STL容器set、multiset、unordered_set和unordered_multiset；

• 插入、删除和查找元素；

• 使用STL容器set、multiset、unordered_set和unordered_multiset的优缺点；

19.1 简介

容器 set和 multiset让程序员能够在容器中快速查找键，键是存储在一维容器中的值。set和multiset之间的区别在于，后者可存储重复的值，而前者只能存储唯一的值。

图19.1表明，set只能包含唯一的人名，而multiset可存储重复的人名。STL容器是泛型模板类，因此是通用的，可用于存储字符串、整型、结构或类对象。

图19.1 包含人名的set和multiset的可视化表示

为实现快速搜索，STL set和multiset的内部结构像二叉树，这意味着将元素插入到 set或multiset时将对其进行排序，以提高查找速度。这还意味着不像 vector 那样可以使用其他元素替换给定位置的元素，位于set中特定位置的元素不能替换为值不同的新元素，这是因为set将把新元素同二叉树中的其他元素进行比较，进而将其放在其他位置。

要使用std::set或set::multiset类，需要包含头文件<set>：

19.2 STL set和multiset的基本操作

STL set和multiset都是模板类，要使用其成员函数，必须先实例化。

19.2.1 实例化std::set对象

要实例化一个特定类型的set或multiset，必须针对该类型具体化模板类std::set或std::multiset：

要声明一个包含Tuna对象的set或multiset，应这样编写代码：

要声明一个指向set或multiset中元素的迭代器，应这样做：

如果需要一个可用于修改值或调用非const函数的迭代器，应将const_iterator替换为iterator。

鉴于set和multiset都是在插入时对元素进行排序的容器，如果您没有指定排序标准，它们将使用默认谓词std::less，确保包含的元素按升序排列。

要创建二元排序谓词，可在类中定义一个operator()，让它接受两个参数（其类型与集合存储的数据类型相同），并根据排序标准返回true。下面是一个这样的排序谓词，它按降序排列元素：

然后，在实例化set或multiset时指定该谓词，如下所示：

除上述实例化方式外，还可这样创建set或multiset，即包含另一个set或multiset的部分或全部元素，如程序清单19.1所示。

程序清单19.1 各种实例化set和multiset的方式

分析：

这个程序没有输出，但演示了各种实例化整型set和multiset的方式。第17和18行演示了最简单的实例化方式：省略除类型外的其他所有模板参数，这导致使用默认排序谓词，即std::less<T>。如果要覆盖这种默认行为，需要像第3～10行那样定义一个谓词，并像第21和22行那样使用它。该谓词将元素按降序排列（默认为升序）。最后，第25和26行演示了这样两种实例化方式：使用一个set来实例化另一个set；使用set的特定范围内的元素来实例化multiset，这里也可使用vector、list或其他任何STL容器类，只要它能够通过cbegin()和cend()返回描述边界的迭代器。

cbegin()和cend()导致了编译错误吗？

如果要使用不遵循C++11的编译器编译该程序，请将cbegin()和cend()分别替换为begin()和end()。cbegin()和cend()是C++11新增的，它们返回一个const迭代器，不能用于修改元素。

19.2.2 在set或multiset中插入元素

set和multiset的大多数函数的用法类似，它们接受类似的参数，返回类型也类似。例如，要在这两种容器中插入元素，都可使用成员函数insert，这个函数接受要插入的值：

程序清单19.2演示了如何在这些容器中插入元素。

程序清单19.2 在STL set或multiset中插入元素

输出：

分析：

第4～13行是通用的模板函数DisplayContents()，您在第17和18章见过，它将STL容器的内容显示到控制台（屏幕）。第17行和第18行定义了一个set对象和一个multiset对象。第20～22行调用成员函数insert()将值插入到set中。第19行演示了如何使用insert()将一个set的内容插入到一个multiset中，这里是将 setIntegers的内容插入到multiset msetIntegers中。第 27行插入一个值为 3000的元素，该元素已存储在multiset中。从输出可知，multiset能够存储多个相同的值。第32行和第33行演示了成员函数multiset::count()的用法，它返回multiset中有多少个元素存储了指定的值。

mulitset::count()确定multiset包含多少个这样的元素，即其值与通过实参传递给这个函数的值相同。

关键字auto导致了编译错误吗？

在程序清单19.2中，函数DisplayContents()使用了C++11关键字auto来指定迭代器的类型，如第7行所示。另外，它还使用了C++11新增的cbegin()和cend()，它们返回一个const_iterator。

对于这个示例以及后面的示例，如果要使用不遵循C++11的编译器进行编译，需要将auto替换为显式类型。

因此，如果使用的是较旧的编译器，需要将DisplayContents()修改成下面这样：

19.2.3 在STL set或multiset中查找元素

诸如set、multiset、map和multimap等关联容器都提供了成员函数find()，它让您能够根据给定的键来查找值：

程序清单19.3演示了find()的用法。multiset可包含多个值相同的元素，因此对于multiset，这个函数查找第一个与给定键匹配的元素。

程序清单19.3 使用成员函数find

输出：

分析：

第21～27行演示了成员函数find()的用法。第24行将find()返回的迭代器与end()进行比较，以核实是否找到了指定的元素。如果该迭代器有效，便可使用*iElementFound访问它指向的值。

程序清单19.3所示的示例也适用于multiset，只需在将第6行的set替换为multiset即可，这不会影响应用程序。

19.2.4 删除STL set或multiset中的元素

诸如set、multiset、map和multimap等关联容器都提供了成员函数erase()，它让您能够根据键删除值：

erase函数的另一个版本接受一个迭代器作为参数，并删除该迭代器指向的元素：

通过使用迭代器指定的边界，可将指定范围内的所有元素都从set或multiset中删除：

程序清单19.4演示了如何使用erase()来删除mset或multiset中的元素。

程序清单19.4 使用multiset的成员函数erase

输出：

分析：

注意到第15行使用了typedef。第38行使用了count()来确定有多少个元素包含特定的值。实际的删除操作是在第42行执行的，它删除与特定值匹配的所有元素。

函数erase()被重载了。可将迭代器（如find返回的迭代器）传递给erase()，以删除找到的元素，如下所示：

同样，erase()还可用于从multiset中删除指定范围内的元素：

上述代码删除从开头到值为nValue的所有元素（不包含nValue）。要清空set和multiset的内容，可使用其成员函数clear()。

学习set和multiset的基本函数后，接下来看一个使用set容器的实际应用程序。程序清单19.5是基于菜单的电话簿的简单实现，它让用户能够插入、查找、删除和显示人名和电话号码。

程序清单19.5 一个使用STL set及其成员函数 find和erase的电话簿

输出：

分析：

这个程序清单与按字母顺序对std::list进行排序的程序清单18.7很像，差别在于std::set排序是在插入元素时进行的。输出表明，您不需要调用任何函数来对set中的元素进行排序，因为排序是在插入元素时进行的。您让用户指定要删除的条目，然后第64行调用find()找到该条目，而第68行使用erase()删除该条目。

这个电话簿实现是基于 STL set的，因此不允许多个元素包含相同的值。如果要让电话簿能够存储两个相同的人名（如Tom），则应使用STL multiset。如果setContacts为multiset，上述代码仍可正确运行。要使用multiset存储多个值相同的元素，应使用count()成员函数来获悉有多少个元素包含特定的值，这在前面的代码示例中演示过。在 multiset 中，类似的元素是相邻的，find 函数返回一个迭代器，它指向找到的第一个元素。可将该迭代器递增以获取下一个元素。

19.3 使用STL set和multiset的优缺点

对需要频繁查找的应用程序来说，STL set和multiset很有优势，因为其内容是经过排序的，因此查找速度更快。然而，为提供这种优势，容器在插入元素时进行排序。因此，插入元素时有额外开销，因为需要对元素进行排序——如果应用程序将频繁使用find()等函数，则这种开销是值得的。

find()利用了内部的二叉树结构。这种有序的二叉树结构使得set和multiset与顺序容器（如vector）相比有一个缺点：在vector中，可以使用新值替换迭代器（如std::find()返回的迭代器）指向的元素；但set根据元素的值对其进行了排序，因此不能使用迭代器覆盖元素的值，虽然通过编程可实现这种功能。

C++11

STL散列集合实现std::unordered_set和std::unordered_multiset

STL std::set和 std::multiset使用 std::less<T>或提供的谓词对元素（同时也是键）进行排序。相对于vector 等未经排序的容器，在经过排序的容器中查找的速度更快，其 sort 的复杂度为对数。这意味着在set中查找元素时，所需的时间不是与元素数成正比，而是与元素数的对数成正比。因此，相比于包含 100个元素的 set，在包含 10000个元素的 set中查找时，需要的平均时间将翻一倍（因为 100^2 = 10000，即 log(10000) = 2 × log(100)）。

相比于未经排序的容器（查找时间与元素数成正比），这极大地改善了性能，但有时候这还不够。程序员和数学家都喜欢探索插入和排序时间固定的方式，一种这样的方式是使用基于散列的实现，即使用散列函数来计算排序索引。将元素插入散列集合时，首先使用散列函数计算出一个唯一的索引，再根据该索引决定将元素放到哪个桶（bucket）中。

STL提供的容器类std::unordered_set就是基于散列的set。

要使用STL容器std::unordered_set或std::unordered_multiset，需要包含头文件<unordered_set>：

相比于std::set，这个类的用法差别不大：

然而，unordered_set的一个重要特征是，有一个负责确定排列顺序的散列函数：

程序清单19.6演示了std::unordered_set提供的一些常见方法的用法。

程序清单19.6 使用std::unordered_set及其方法insert()、find()、size()、max_bucket_count()、load_factor()和max_load_factor()

输出：

分析：

这个示例创建了一个整型 unordered_set ，在其中插入 8 个值，再显示其内容，包括max_bucket_count()、load_factor()和max_load_factor()提供的统计信息，如第8～10行所示。输出表明，最初的桶数为8个，而该容器包含8个元素，因此负载系数为1，与最大负载系数相同。插入第9个元素时，unordered_set重新组织：创建64个桶并重新创建散列表，而负载系数降低了。main()中的其他代码表明，在unordered_set中查找元素的语法与set类似。find()返回一个迭代器，在使用该迭代器之前，需要核实find()是否成功，如第44行所示。

散列函数通常用于根据键在散列表中查找值，详情请参阅第 20 章中介绍std::unordered_map的一节。

std::unordered_map是C++11新增的一种散列表实现。

19.4 总结

本章介绍了STL set和multiset及其重要的成员函数和特征，还通过一个基于菜单的简单电话簿演示了如何使用set和multiset，该电话簿提供了搜索和删除功能。

19.5 问与答

问：如何声明一个其元素按降序排列的整型set？

答：set<int>定义一个整型set，这种set使用默认排序谓词std::less<T>将元素按升序排列，也可将其定义为 set<int, less <int>>。要按降序排列，应将 set定义为 set<int, greater <int>>。

问：如果在一个字符串set中插入字符串Jack两次，将发生什么情况？

答：set不能存储多个相同的值，因此std::set类的实现不允许插入第二个Jack。

问：在前一个例子中，如果需要两个Jack，该如何办？

答：set只能存储唯一的值。应选择使用multiset。

问：multiset的哪个成员函数指出容器有多少个元素包含特定的值？

答：函数 count (value)。

问：我使用函数find在set中找到了一个元素，并有一个指向该元素的迭代器。能否使用这个迭代器来修改它指向的元素的值？

答：不能。有些STL实现可能允许用户通过迭代器（如find函数返回的迭代器）修改元素的值，但不应这样做。应将指向set中元素的迭代器视为const迭代器，即使STL实现没有强制这样做。

19.6 作业

作业包括测验和练习，前者帮助读者加深对所学知识的理解，后者提供了使用新学知识的机会。请尽量先完成测验和练习题，然后再对照附录 D 的答案。在继续学习下一章前，请务必弄懂这些答案。

19.6.1 测验

1．使用 set <int>声明整型 set时，排序标准将由哪个函数提供？

2．在multiset中，重复的值以什么方式出现？

3．set和multiset的哪个成员函数指出容器包含多少个元素？

19.6.2 练习

1．在不修改 ContactItem 的情况下，扩展本章的电话簿应用程序，使其能够根据电话号码查找人名（提示：定义set时指定一个二元谓词，以便根据电话号码对元素进行排序，从而覆盖根据运算符<进行排序的默认方式）。

2．定义一个multiset来存储单词及其含义，即将multiset用作词典（提示：multiset存储的对象应是一个包含两个字符串的结构，其中一个字符串为单词，另一个字符串是单词的含义）。

3．通过一个简单程序演示set不接受重复的元素，而multiset接受。