C++ set(STL set)容器是什么

从本节开始，将介绍 set (集合)的使用。集合是一个简单直观的数学概念，即具有共同特征的事物的集合。集合在 STL 中有两个概念，它们都涉及一系列的数学思想。集合可以是由两个迭代器定义的范围内的一系列对象，也可以是一种有特殊特征的容器类型。set 容器是关联容器，其中的对象是对象它们自己的键。

除了没有单独的键，set 容器和 map 容器很相似。定义 set 的模板有 4 种，其中两种默认使用 less<T> 来对元素排序，另外两种使用哈希值来保存元素。有序 set 的模板定义在 set 头文件中。无序 set 的模板定义在 unordered_set 头文件中。因此有序 set 包含的元素必须支持比较运算，无序 set 中的元素必须支持哈希运算。

定义 set 容器的模板如下：

• set<T> 容器保存 T 类型的对象，而且保存的对象是唯一的。其中保存的元素是有序的，默认用 less<T> 对象比较。可以用相等、不相等来判断对象是否相同。
• multiSet<T> 容器和 set<T> 容器保存 T 类型对象的方式相同，但它可以保存重复的对象。
• unorderd_set<T> 容器保存 T 类型的对象，而且对象是唯一的。元素在容器中的位置由元素的哈希值决定。默认用 equal_to<T> 对象来判断元素是否相等。
• unordered_multiset<T> 容器保存 T 类型对象的方式和 unorderd_set<T> 相同，但它可以保存重复的对象。

从有序和无序关联容器获取的各种迭代器之间有一些区别。我们可以从有序容器得到正向和反向迭代器，但是只能从无序容器得到正向迭代器。

如果之前没有用过 set 容器，你可能不知道如何检索这种容器中的对象，这需要提供一个相同的对象。如果我们已经有这个对象，那为什么还需要再去获取它？对此你也许会感到惊讶，set 容器有很多用途。

和一组事物相关的程序可以用 set 来保存候选数据，它可以确定程序需要的数据集。大学里的班级就是一个示例。每个班都可以用一个包含学生的set容器来表示。这里使用 set 容器比较合适，因为同一个班级中不可能有重复的学生；显然，两个学生可以同名，但是它们所表示的人是不同的。可以很容易查看某个学生是否申请了某门课程，也可以查看某个学生申请了哪些课程。

一般来说，当 set 中有大量元素时，在无序 set 上执行的随机插入和检索操作要比有序 set 快。在有 n 个元素的有序 set 中检索元素的时间复杂度是 logn。在无序 set 中检索元素的平均时间复杂度是常量，这和元素的个数无关，尽管实际性能会受元素哈希操作和内部组织效率的影响。

对象在容器中的存放位置取决于有序 set 的比较函数和无序 set 的哈希函数，对于保存同一种对象的不同 set，我们可以使用不同的比较函数或哈希函数。这里有一个简单的示例，用 Person 类来表示公司的员工，这个类会封装一些个人信息。类中应该包括个人 ID、部门、姓名、年龄、地址、性别、电话号码、薪酬等级等信息。然后可以用各种方式对员工进行分类。可以在一个 set 中用工作部门的哈希比较，在另一个 set 中用薪酬等级的哈希比较。这样我们就可以得到特定薪酬等级或特定部门的员工。这些 set 中不会保存重复的 Person 对象。可以在自由存储区创建 Person 对象，然后将它们的智能指针保存在容器中。在本章的后面你会看到一些相关示例。为了简化代码，假定在本章使用了 std::string。