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。

本文标题:C++ set(STL set)容器是什么

本文地址:http://www.hosteonscn.com/2936.html

评论

0条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注