31、map与unordered_map对比
时间: 2023-10-21 20:30:44 浏览: 68
map和unordered_map都是STL中的容器,用于存储键值对,但它们在底层实现和使用上有很大的不同。
1. 底层实现:map底层实现采用红黑树,因此它的元素是按照键值有序排列的;而unordered_map底层实现采用哈希表,因此它的元素是无序的。
2. 查找效率:由于map是按照键值有序排列的,因此在查找时可以使用二分查找等优化算法,因此查找效率较高,时间复杂度为O(logn);而unordered_map是无序的,查找时需要遍历哈希桶中的元素,时间复杂度为O(1)。
3. 内存占用:由于map底层实现采用红黑树,需要额外存储指针等信息,因此内存占用较大;而unordered_map底层实现采用哈希表,不需要额外的指针信息,因此内存占用较小。
4. 插入、删除效率:由于map底层实现采用红黑树,插入、删除元素时需要执行平衡操作,因此效率较低,时间复杂度为O(logn);而unordered_map底层实现采用哈希表,插入、删除元素时只需要进行哈希计算和移动指针等操作,因此效率较高,时间复杂度为O(1)。
5. 迭代器稳定性:由于map底层实现采用红黑树,因此在插入、删除元素时,迭代器不会失效;而unordered_map底层实现采用哈希表,可能会因为扩容等原因导致迭代器失效。
综上所述,map适用于需要按照键值有序排列的场景,而unordered_map适用于无序场景下需要高效查找、插入、删除元素的场景。
相关问题
unordered_map与unordered_set
unordered_map与unordered_set有什么区别?
回答: unordered_map和unordered_set都是关联式容器,类似于键值对 (key-value) 的模型。它们的底层实现方式不同,unordered_map使用哈希表作为底层数据结构,而unordered_set也是使用哈希表。unordered_map和unordered_set的区别在于它们存储的类型不同,即unordered_map存储键值对,而unordered_set存储单个元素。此外,unordered_map和unordered_set在功能上也有一些区别。unordered_map提供了以键为索引的查找功能,而unordered_set则提供了判断元素是否存在的功能。从效率上来看,unordered_map和unordered_set的增删查改操作的时间复杂度都是O(1),即常数时间。而map和set的时间复杂度为O(logN),其中N是容器中的元素数量。所以在对效率要求较高的情况下,选择unordered_map和unordered_set会更合适。但是,unordered_map和unordered_set相比于map和set会消耗更多的内存空间。因此,在对数据有排序或者对空间有要求的情况下,选择map和set;而对于对效率有要求的情况,选择unordered_map和unordered_set更合适。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [STL详解(十二)—— unordered_set、unordered_map的介绍及使用](https://blog.csdn.net/chenlong_cxy/article/details/122277348)[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^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [模拟实现unordered_map和unordered_set超详解(C++)](https://blog.csdn.net/m0_67430750/article/details/124760725)[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^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* [unordered_set和unordered_map的使用【STL】](https://blog.csdn.net/m0_63312733/article/details/128000844)[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^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]
unordered_set、unordered_multiset、unordered_map、unordered_multimap底层原理
unordered_set、unordered_multiset、unordered_map和unordered_multimap的底层原理是基于哈希表实现的。哈希表是一种数据结构,通过将关键字映射到哈希表中的一个位置来快速查找和插入元素。在哈希表中,每个元素被存储在一个桶中,桶的数量和大小根据哈希表的大小和负载因子动态调整。
当插入一个元素时,哈希表首先使用哈希函数计算关键字的哈希值,然后根据哈希值找到对应的桶。如果桶是空的,则直接插入元素;如果桶不为空,则通过开放定址法或链地址法解决冲突,将元素插入到合适的位置。插入操作的平均时间复杂度是常数级别的。
当查找一个元素时,哈希表通过哈希函数计算关键字的哈希值,然后根据哈希值找到对应的桶。如果桶中有元素,则通过比较关键字找到目标元素;如果桶中没有元素,则表示目标元素不存在。查找操作的平均时间复杂度是常数级别的。
删除一个元素的操作也类似于查找操作,先找到元素所在的桶,然后删除元素。删除操作的平均时间复杂度也是常数级别的。
阅读全文