set multiset unorderedset map multimap unorderedmap
时间: 2023-11-11 19:04:06 浏览: 42
set是一个关键字集合,其中每个关键字只能出现一次。multiset与set类似,但是允许关键字重复出现。unordered_set是一个无序的关键字集合,其中每个关键字只能出现一次。map是一个关键字-值对的集合,其中每个关键字只能出现一次。multimap与map类似,但是允许关键字重复出现。unordered_map是一个无序的关键字-值对的集合,其中每个关键字只能出现一次。
需要注意的是,unordered_set、unordered_map、unordered_multiset和unordered_multimap是使用哈希函数组织的,因此它们的元素是无序的。而set、map、multiset和multimap是使用红黑树组织的,因此它们的元素是有序的。
这些容器都可以在C++ STL中使用,它们都有自己的头文件。set和map的头文件是<set>和<map>,multiset和multimap的头文件是<set>和<map>,unordered_set和unordered_map的头文件是<unordered_set>和<unordered_map>,unordered_multiset和unordered_multimap的头文件是<unordered_set>和<unordered_map>。
相关问题
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 ]
unordered_set、unordered_multiset、unordered_map、unordered_multimap底层原理
unordered_set、unordered_multiset、unordered_map和unordered_multimap的底层原理是基于哈希表实现的。哈希表是一种数据结构,通过将关键字映射到哈希表中的一个位置来快速查找和插入元素。在哈希表中,每个元素被存储在一个桶中,桶的数量和大小根据哈希表的大小和负载因子动态调整。
当插入一个元素时,哈希表首先使用哈希函数计算关键字的哈希值,然后根据哈希值找到对应的桶。如果桶是空的,则直接插入元素;如果桶不为空,则通过开放定址法或链地址法解决冲突,将元素插入到合适的位置。插入操作的平均时间复杂度是常数级别的。
当查找一个元素时,哈希表通过哈希函数计算关键字的哈希值,然后根据哈希值找到对应的桶。如果桶中有元素,则通过比较关键字找到目标元素;如果桶中没有元素,则表示目标元素不存在。查找操作的平均时间复杂度是常数级别的。
删除一个元素的操作也类似于查找操作,先找到元素所在的桶,然后删除元素。删除操作的平均时间复杂度也是常数级别的。