【C++ STL】set这一类容器

本文主要是介绍【C++ STL】set这一类容器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

set这一类容器总共有四种：

1. set
2. multiset
3. unordered_set
4. unordered_multiset

---

这四种根据实现时使用的数据结构不同可以分成两大类：

一、使用红黑树实现的:set与multiset

set与multiset的相同点

时间复杂度：增删查改操作的平均时间复杂度是O(log n)

• 插入元素的平均时间复杂度是$O(logn)$，因为容器内部使用红黑树（平衡二叉搜索树）实现，插入元素需要将元素按照顺序插入到合适的位置，红黑树的插入操作平均时间复杂度为$O(logn)$。
• 删除元素的平均时间复杂度也是$O(logn)$，因为红黑树的删除操作也需要保持平衡，平均情况下的时间复杂度是$O(logn)$。
• 查找元素的时间复杂度也是$O(logn)$，因为红黑树是一种有序的树结构，通过比较元素大小，在树中进行查找的时间复杂度是$O(logn)$。
• 修改元素的时间复杂度也是$O(logn)$，因为需要先删除旧元素，然后插入新元素。

需要注意的是，这些时间复杂度是在平均情况下的估计，具体情况还取决于实际数据的分布和红黑树的性能。

---

迭代器：迭代器是双向迭代器，可以通过++和--操作来移动迭代器，并且还支持对迭代器所指向的元素进行修改

set与multiset的不同点

set中的元素不会重复，当插入集合中已有的元素时，并不会插入进去，而且set容器里的元素自动从小到大排序
multiset中的元素可以重复，且multiset容器里的元素自动从小到大排序

二、使用哈希表实现的:unordered_set与unordered_multiset

unordered_set与unordered_multiset的相同点

时间复杂度：增删查改操作的平均时间复杂度是O(1)

• 插入元素的时间复杂度是O(1)，因为容器内部使用哈希函数直接确定元素的插入位置，只需要常数时间即可完成插入。
• 删除元素的时间复杂度也是O(1)，同样是因为容器内部使用哈希函数定位到要删除的元素位置，然后直接删除。
• 查找元素的时间复杂度也是O(1)，因为容器内部使用哈希函数快速定位元素所在的桶，然后在桶中进行查找。
• 修改元素的时间复杂度也是O(1)，因为容器内部使用哈希函数快速定位元素所在的桶，然后在桶中进行修改。

需要注意的是，这是在平均情况下的时间复杂度，具体情况还取决于实际数据的分布和哈希函数的效果。在最坏情况下，当哈希函数将大量的元素映射到同一个桶中时，操作的时间复杂度可能会变为O(n)。但在平均情况下，增删查改操作时间复杂度为O(1)。

---

迭代器：迭代器是正向迭代器，只能通过++操作向后移动，不支持--操作。
且迭代器不支持修改操作，如果想修改元素的值，需要从容器中删除该元素，然后插入一个新的值。

unordered_set与unordered_multiset的不同点

unordered_set ：元素无序且只能出现一次
unordered_multiset ：元素无序且可以出现多次

---

这篇关于【C++ STL】set这一类容器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---