4.3.4. STL容器：集合和映射¶
回顾前面的内容，我们学习了哈希表这种特殊的数据表，它具有能够以接近常数时间的效率进行元素增删查改的优秀性能，但是它对元素的类型有一定的要求，即要求元素是所谓的键值对形式的数据项，其中键这个部分要求是唯一的，不同的数据项必须有不同的键。在实际的算法问题编程中，很少遇见需要自己编写一个哈希表的情况，但是经常会用到集合和映射这两种数据结构，它们往往是基于哈希表来实现的。前面我们也已经说过，如果哈希表中保存的数据项是键值合一的，那么就相当于一个集合，如果是键值分开的，那么就相当于一个映射。
C++和Java等其他现代高级语言一般都会提供多种集合和映射容器，其中一定会有一些是基于哈希表技术来实现的，比如Java的 HashSet 和 HashMap 就是。算法竞赛所使用的C++98，其STL库也提供了集合 set 和映射 map 两种容器，它们是基于二叉检索树技术的，因此能够让容器中的元素根据键值大小保持有序，但是增删查的效率略微低一点。自从C++11标准开始增加了无序集合 unordered_set 和无序映射 unordered_map 容器，它们是基于哈希表来实现的，时间效率就高了，但可惜目前很多信息学算法竞赛不支持使用C++11标准。另外，C++的STL容器还提供了键值可重复的集合和映射容器，分别是 multiset 和 multimap，C++11开始同样地为无序集合和无序映射提供了键值可重复的版本 unordered_multiset 和 unordered_multimap。
本节我们将简单介绍STL的集合容器和映射容器的使用方法进行介绍。
4.3.4.1. 集合的基本概念¶
集合本身是一个数学概念，是现代数学的基石。数学上所述的集合概念非常简单，就是一系列互不相等的元素所构成的一个整体。数学的集合有以下几个性质：
元素的类型可以多种多样，并不一定需要是同类型的。比如数字和几何图形也可以是同一个集合中的元素，只要是某种具体的东西都可以放进任何集合里去。
元素的数量没有任何要求，最少可以是0个（空集），可以是有限个，比如10以内自然数的集合，也可以是无限个，比如一条线段上所有点的集合。
元素的顺序没有任何规定，比如 {1,2,3} 和 {3,2,1} 是相同的集合，和它们的元素排列顺序没有关系。
编程语言提供的集合容器，会尽量地模拟数学上的集合概念，但是终究会有所不同。最显而易见的不同就是受到计算机存储空间的限制，不可能真正实现无限集合。根据实现技术的不同，有些集合容器会确保元素之间保持一定的顺序，例如C++的 set 容器会利用元素之间的小于比较运算来确保元素按照大小关系从小到大存放，Java的 LinkedSet 容器会保证元素按照添加入集合中的顺序来存放。有些则不会，例如C++11的 unordered_set 和Java的 HashSet 容器就不保证元素之间的任何存放顺序，因为它们都是基于哈希表实现的。
编程语言提供的集合容器对于元素的数据类型也是多少有一点限制的。例如C++的 set 容器，在定义的时候要求指定一个数据类型，以后放入集合中的元素就必须是这种类型的，并不是数学上集合概念所说的完全没有任何限制，Java的集合容器也是一样。在算法编程中，这样的限制并不会带来太多麻烦，一般算法编程不会遇到要把不同类型数据放在一个集合里去的情况。
补充
但是工程性质的软件开发时就不一样了，不同类型数据希望放在一个集合里去的情况时有发生，这时候就需要用到面向对象编程技术来解决问题。C++、Java和其他绝大多数现代编程语言都支持面向对象的编程技术，通过类型之间的继承关系，可以使用一个公共的父类型（也叫基类）来定义容器，然后所有继承自这个公共基类的子类型就都可以放进去了。
例如最经典的解决方案来自Java语言，Java有一个理念叫做Everything is object，万物皆对象。在Java语言中预先定义了一个最基础的基类叫做 Object，所有其他任何类型都继承自它，都是它的子子孙孙，因此就叫做 Everything is object。在Java的世界里已经消灭了“你是不是东西？”这个千古难题，只剩下“你是个什么东西？”这个问题了。正因为如此，我们可以这样定义一个允许放进去任何东西的集合：
Set<Object> h = new HashSet<Object>();
C++虽然没有Java做得这么彻底，并没有一个最基础的基类，但是并不妨碍我们自己定义一个呀。如果使用C++的面向对象编程，我们完全可以自己定义一个类似这样的基类。当然了，这是面向对象的编程技术，在学习算法编程时我们不去学它，作为补充知识有所了解就可以了。
4.3.4.2. STL集合容器¶
前面已经说过，STL的集合容器总共有四种：set、multiset、unordered_set 和 unordered_multiset。实际上，所有四种容器在使用上几乎完全相同。下面我们首先看最基础的 set 容器。
set 是C++98的STL库中就提供的标准集合容器，是目前所有算法竞赛都允许使用的。这个容器是采用二叉检索树作为底层结构来实现的，它能够让集合中的所有元素按照大小顺序有序排列，增删查的时间复杂度都是 \(O(\log n)\)，虽然比不上C++11新增的使用哈希表作为底层结构的 unordered_set 容器，但是也已经够快了，毕竟它还能实现元素的自动排序。要使用 set 容器，和别的所有其他STL容器一样，要引入同名的库，要使用 std 命名空间，定义具体的集合时要指定元素数据类型，也可以利用一些已有的其他容器（或数组）来初始化新定义的集合。例如：
#include <set>
using namespace std;
set<int> s1; // 定义一个空的集合，元素为int类型
int data[] = { 1, 2, 3, 4, 5 };
set<int> s2(data, data+5); // 定义一个集合，用数组data的一段数据来初始化
set 也和其他STL容器一样，可以用迭代器来进行元素访问，也有四种迭代器：头部迭代器 begin()、尾部迭代器 end()、反向头部迭代器 rbegin() 和反向尾部迭代器 rend()。它也有常规的 empty() 和 size() 成员函数用来判断容器是否为空和获取元素数量，也有 clear() 成员函数用来清空集合，有 swap() 成员函数用来交换两个集合的内容。这些都是STL容器的标准成员函数，这里就不再一一详细说明了。
和 vector 这些我们已经学过的线性表类型容器不同的是，set 对它的元素数据类型有特殊的要求，即元素的数据类型必须支持大小比较。内置的数据类型和C++ string天生具有大小比较的能力，因此直接可以用做集合的元素数据类型；自定义的结构等派生数据类型，我们需要重载小于运算；而数组和C-string，不能直接作为集合的元素，我们需要用一个结构把它包装起来并重载一个小于运算才行。例如：
struct Point4D {
double coord[4];
bool operator<(const Point4D &p) const
{
double l1 = coord[0] * coord[0];
double l2 = p.coord[0] * p.coord[0];
for (int d = 1; d < 4; ++d) {
l1 += coord[d] * coord[d];
l2 += p.coord[d] * p.coord[d];
}
return l1 < l2;
}
};
set<Point4D> s_p4d;
上面的结构表示四维空间中的点，它的坐标由4个 double 型浮点数构成，一般可以用一个长度为4的 double 型数组来表示。但是数组不能直接用做集合的元素类型，所以我们用一个结构来包装它。并且我们需要重载这个结构的小于比较运算符，让它们可以比较大小，这里我们用比较点到空间原点的距离的规则来比较点的大小，离原点越近的就认为越小。上面这样一个结构 Point4D 就可以作为集合的元素数据类型了。
接下来就是集合容器特殊的元素访问操作了，一共增删查三种操作。因为集合元素是键值合一的数据项，所以不提供修改操作。增删查三种操作一共四个成员函数。
添加元素的成员函数为 insert()，我们只需记得它最最常用的用法：提供一个数据项参数作为要添加的元素，不用理会它的返回值。例如：
Point4D p(1,2,3,4);
s_p4d.insert(p);
删除元素的成员函数为 erase()，它有两种常用的用法：一种是提供一个数据项参数，删除集合中与之相等的那个元素；另一种是提供一个指向集合中某个元素的迭代器，然后删除这个元素。例如：
Point4D q(1,1,1,1);
s_p4d.erase(q); // 删除值为(1,1,1,1)的那个元素
s_p4d.erase(s_p4d.begin()+1); // 删除集合中第2小的那个元素
查找元素的成员函数有两个：find() 函数需要提供一个数据项参数，查找集合中是否存在与之相等的元素，如果存在，返回指向该元素的迭代器，不存在则返回尾部迭代器；count() 函数同样需要一个数据项参数并在集合中查找，返回的是集合中与之相等的元素的数量。由于 set 集合要求元素全部互不相等，所以实际上 count() 函数的返回值只有两种，要么是0要么是1，不会有其他返回值。
set 容器的最常用的操作就上述这些，很简单。在实际编程中，除了真正用做集合，这个容器还经常被利用来进行某些特殊场景下的排序，例如下面这个非常简单的练习。
练习
连续输入20个整数，用空格或换行来分隔。要求剔除其中所有重复的数之后按照从大到小的顺序输出，每个数一行。使用 set 容器完成这个任务。
警告
虽然遇到上面这个练习这样的场景，用 set 似乎挺简单，而且时间复杂度也是 \(O(n\log n)\)，但是要注意，set 的实际排序速度比 sort() 要慢，而且它读取单个元素的时间也是 \(O(\log n)\)，也就是说遍历集合元素的整体时间是 \(O(n\log n)\)，比线性表容器慢！所以在需要高效率的算法问题中，不要利用 set 集合来做排序的事情。
有时候我们遇到的场景是会出现值相同的不同元素，即两个元素的数据是完全相等的，但是我们需要把它们区分为两个不同的集合元素。比如我们在研究四维空间中的一系列动点的运动轨迹问题，我们有许多的四维动点，用前面所介绍过的那个 Point4D 结构来表示。我们把多个要研究的动点按其初始坐标值放在集合 s_p4d 中，然后用一个程序不断地从集合中取出第一个点（就是离原点最近的那个点），计算并更新为下一时刻的坐标值后重新把它放回集合中去。这个程序看起来就好像一个四维空间的雷达，从原点开始沿着四维球面由里向外地扫描空间中的动点，找到一个离原点最近的动点就让它运动到下一个位置，再重新从原点开始由内向外扫描最近动点，这样不断循环地跟踪所有动点的运动轨迹。但是，我们无法确保所有动点在任何时刻运动轨迹都不会相交。因此我们需要考虑动点在四维空间某处发生“碰撞”的情况。当碰撞发生时，两个不同动点的坐标值完全相同，但是它们依然是两个不同的动点，在集合中不能被合并为一个元素。
这种情况下就需要用到可重复值集合容器 multiset 了。这个容器允许集合中存在值相等的元素，其他和 set 容器没有任何区别。它一样是基于二叉检索树实现的，能确保集合中的元素在使用迭代器访问时保持元素值从小到大的递增顺序。它有和 set 集合完全一样的成员函数，在使用上仅有以下几个细微但显而易见不同之处：
find()成员函数根据值来查找元素，当具有这个值的元素有多个时，不保证返回的是其中哪一个，只确保会返回其中某一个的迭代器。count()成员函数统计具有特定值的元素数量，返回值有可能大于1。erase()成员函数在根据值来删除元素时，所有具有该值的元素都会被同时删除，有可能多于1个。
其他没有任何区别！
思考
如果你已经知道了怎样实现 set 容器，现在要改成 multiset，请思考一下怎样修改最为简单。
C++11开始，STL库提供了哈希表版本的集合容器 unordered_set 和 unordered_multiset，称为无序集合。因为采用了哈希表作为集合的基础数据结构，所以访问的时间效率得到了大幅提升，通常情况下会接近常数级时间。同时我们可以从容器的名字看出来，这两个容器不再确保其中的元素可以按某个明确的顺序来访问了，我们知道这也正是哈希表的特征之一。
无序集合除了多了几个与哈希策略相关的成员函数外，增删查等常规用法与 set 和 multiset 完全一样，没有任何不同。所以关于这两个无序集合，我们现在就先暂时不去仔细学习了，有所了解就好。
4.3.4.3. 映射的概念和STL映射容器简介¶
映射是一个很重要的数学概念，纯数学的映射（map）是指两个集合的元素相互之间的对应关系。例如函数就是映射的一种，比如说整数函数 \(f(n)=2n\) 就是一个从整数集合到偶数集合的映射，每一个整数集合中的整数，通过乘以2这个方式对应了偶数集合中的一个且是唯一的互不相同的一个偶数，1对应2、2对应4、-3对应-6、0对应0（这里认为0也是偶数）。
在计算机软件使用的数据结构中，通常用键值对这种方式来表示映射。当然这是对数学意义上的映射的模仿，实际上二者还是有所不同的。前面已经介绍过，键值对就是由键和值两部分配对构成的一个二元组。其中键这个部分应当是唯一的、各不相同的、可以比较大小的而且不能改变的，一旦一个键值对构造好之后，不能再改变它的键。值则完全没有上述的约束，不同的键值对可以有相同的值，不同的值之间完全可以没有大小关系或任何其他序关系，而且一般总是允许随时修改值。
例如每个人的身份证号码和姓名就可以构成一个简单的键值对，其中身份证号码是一个18位的字符串，姓名可以是一个任意长度的字符串。按照JavaScript引入的JSON字符串格式，现在习惯上都用 { 键 : 值 } 这样的格式来表示一个键值对数据项。
C++98的STL库提供了两个映射类容器：标准的 map 和允许键值重复的 multimap，它们把键这个部分存放在集合里，map 容器中数据项的键用一个 set 来存放，multimap 容器中数据项的键当然是用一个 multiset 来存放。因此，无论是 map 还是 multimap，它们都要求键所使用的数据类型至少支持小于比较运算。
map 的使用方法和 set 几乎完全一样，不同之处在于我们在定义一个 map 的时候需要指定两个数据类型，前面一个是键的数据类型，后一个是值的数据类型。另外，map 支持对其中元素用方括号加键的形式进行直接访问，很像数组元素的方括号加下标访问方式。其他和 set 就没有什么不同了。
仍然用我们前面的四维空间动点的例子，当我们发现多个四维空间的动点在运动中可能出现轨迹交叉，即多个点有相同的坐标值的时候，前面我们使用 multiset 来解决了这个问题。但是现在我们可以有更好的解决方案，我们可以给每一个点取一个名字，比如A点、B点、P点、P1点、Q2点等等，用一个字符串来存放每一个点的名字，确保名字没有重复。这样就可以用点的名字作为键、坐标作为值来构成键值对，把所有点的键值对放进 map 中去。
#include <map>
#include <string>
#include <cstdio>
using namespace std;
map<string, Point4D> p;
p["O"] = Point4D();
p["P1"] = Point4D(1, 2, 3, 4);
printf("(%.2lf, %.2lf)\n", p["P1"].coord[0], p["P1"].coord[1]); // 输出P1点在XY平面上的投影坐标
这样做还有一个好处，就是现在我们可以随心所欲地任意改变每一个点的坐标值了，例如：
Points["P1"].coord[2] += 1.5;
这就是 map 这个容器的基本用法，其他和 set 容器相同的用法这里就不再赘述了。至于 multimap 的用法相信也不用多说了吧。总之，映射容器在实际的工程软件开发中应用非常广泛，非常重要，但是在算法问题编程中用到的场景并不多，远远少于需要用到集合的情况。鉴于 map 和 set 的极大相似程度，只要掌握了 set 的使用，那么学会使用 map 就十分简单了。
最后还是要提一下，C++11的STL库还提供了基于哈希表键集合的映射容器两种：unordered_map 和 unordered_multimap。这也不多说了，应该一看名字就能够知道怎么回事和该怎么使用。