multiset和set的区别,从底层原理解释
时间: 2024-06-06 19:09:01 浏览: 31
Set是一个集合容器,这个容器中的元素是唯一的,而Multiset是一个可以存储重复元素的容器。从底层原理解释,Set是通过红黑树来实现的,而Multiset是通过红黑树和链表组合起来实现的,链表用来存储相同元素的个数。因此,Multiset的插入、删除、查找操作的复杂度均为O(logN),与Set一致。
相关问题
stl中multiset底层实现红黑树的原理图
multiset是C++标准模板库(STL)中的一个容器,它允许存储多个相同元素的有序集合。在STL中,multiset的底层实现通常是红黑树,它是一种自平衡的二叉查找树。
红黑树是一种特殊的二叉查找树,它的节点上会有一个额外的存储位用来表示节点的颜色,可以是红色或者黑色。红黑树具有以下性质:
1. 每个节点要么是红色,要么是黑色。
2. 根节点是黑色的。
3. 每个叶子节点(NIL节点)是黑色的。
4. 如果一个节点是红色的,则它的两个子节点都是黑色的。
5. 对于每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑色节点。
在红黑树中,通过对节点的颜色和结构进行调整,可以保持树的平衡,即使在插入或删除节点的时候。这样就能够保证在最坏情况下,红黑树的操作的时间复杂度为O(logn)。
在multiset中,使用红黑树作为底层实现可以保证元素按照一定的顺序存储,并且插入、删除、查找等操作的效率都能够得到保障。通过红黑树的自平衡性质,multiset能够高效地处理大量重复元素的存储和查询。因此,红黑树作为multiset的底层实现,为multiset的高效性能提供了坚实的基础。
set multiset unordered_set 区别 表格
下面是set、multiset和unordered_set的区别表格:
| | 插入操作 | 元素顺序 | 重复元素 | []操作符重载 |
|--------------|------------------|-------------------|------------------|-----------------|
| set | insert_unique | 有序 | 不允许重复 | 有 |
| multiset | insert_equal | 有序 | 允许重复 | 有 |
| unordered_set| insert_unique | 无序 | 不允许重复 | 无 |
所以,set和multiset都是有序容器,元素按照一定的顺序存储,并且multiset允许重复元素的存在。而unordered_set是无序容器,元素没有特定的顺序,且不允许重复元素的存在。此外,只有set和unordered_map提供了[]操作符的重载。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [unordered_set、unordered_map、unordered_multiset和unordered_multimap总结](https://blog.csdn.net/sinat_41619762/article/details/115268554)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)