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

2024-02-20 21:04

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

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

set
multiset
unordered_set
unordered_multiset

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

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

set与multiset的相同点

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

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

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

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

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)。

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