[已解决]unordered_map,map的时间空间复杂度?前者会不会出问题?后者可以嵌套吗....哪一个更好?

zhangjinxuan

关于 unordered_map 和 map，我有以下几个问题：

1. unordered_map 的最坏空间复杂度？（我很关心，就怕有时候用上会MLE)
2. unordered_map 的最坏时间复杂度真的是 O(1) 吗？
3. 竞赛中使用 unordered_map 会不会出问题？我听某些人说会出问题
4. map 的最坏时间复杂度? （我很关心，就怕有时候用上会TLE)
5. map 的最坏空间复杂度？
6. 推荐嵌套 map 或 unordered_map 吗？例如写成：

map<int, map<int, bool>> a;

7. map 是不是有序的，unordered_map 即使无序那有没有什么排序规律呢？
8. 这两个哪一个更好一些？


不好意思，问题有点多，回答的问题数量过 75% 我就可以给最佳答案，希望大佬给予详细解答，感谢

最佳答案

月排行榜 / 总排行榜

yuxijian2020

2022-11-24 09:48:48

unordered_map 内部是 哈希(STL内部hash函数只有字符串类型)
map 内部是红黑树
至于竞赛使用会不会出问题....   只能说出问题的永远是人....
最坏时间复杂度的问题和它们的内部数据结构时一样的，不需要质疑
map 是红黑树，所以没有最坏情况   时间复杂度永远是 O(logn)
unordered_map 是hash   最好O(1)，最坏O(n)
是否有序    map是红黑树所以有序，unordered_map是hash所以无序，有没有规律那肯定是有的，但是hash函数肯定是尽量复杂以保证较少的出现hash冲突
哪个更好？没有最好的数据结构只有最适合的
map 有序，空间复杂度比unorder_map低
unorder_map 空间复杂度比map高，执行效率比map高

至于最坏空间复杂度，最大占用空间？我没太明白交给大佬解决....

跳转到最佳答案楼层

yuxijian2020

unordered_map 内部是 哈希(STL内部hash函数只有字符串类型)
map 内部是红黑树
至于竞赛使用会不会出问题....   只能说出问题的永远是人....
最坏时间复杂度的问题和它们的内部数据结构时一样的，不需要质疑
map 是红黑树，所以没有最坏情况   时间复杂度永远是 O(logn)
unordered_map 是hash   最好O(1)，最坏O(n)
是否有序    map是红黑树所以有序，unordered_map是hash所以无序，有没有规律那肯定是有的，但是hash函数肯定是尽量复杂以保证较少的出现hash冲突
哪个更好？没有最好的数据结构只有最适合的
map 有序，空间复杂度比unorder_map低
unorder_map 空间复杂度比map高，执行效率比map高

至于最坏空间复杂度，最大占用空间？我没太明白交给大佬解决....

zhangjinxuan

yuxijian2020 发表于 2022-11-24 09:48
unordered_map 内部是 哈希(STL内部hash函数只有字符串类型)
map 内部是红黑树
至于竞赛使用会不会出问题 ...

unordered_map 的查询最坏是 O(n) 吗？

zhangjinxuan

yuxijian2020 发表于 2022-11-24 09:48
unordered_map 内部是 哈希(STL内部hash函数只有字符串类型)
map 内部是红黑树
至于竞赛使用会不会出问题 ...

但是 O(n) > O(log n) 啊 unordered_map 的效率比 map 效率高吗？

yuxijian2020

zhangjinxuan 发表于 2022-11-24 09:58
unordered_map 的查询最坏是 O(n) 吗？

参照hash表查询，大量出现hash冲突时会存在O(n)复杂度，所以hash函数很重要

zhangjinxuan

yuxijian2020 发表于 2022-11-24 10:05
参照hash表查询，大量出现hash冲突时会存在O(n)复杂度，所以hash函数很重要

明白了，空间复杂度你说是 unordered_map 比 map 的空间复杂度要高是吗？

yuxijian2020

zhangjinxuan 发表于 2022-11-24 10:08
明白了，空间复杂度你说是 unordered_map 比 map 的空间复杂度要高是吗？

写错了    map确实空间复杂度比unordered_map低

zhangjinxuan

yuxijian2020 发表于 2022-11-24 10:10
写错了    map确实空间复杂度比unordered_map低

哦，原来写错了

yuxijian2020

zhangjinxuan 发表于 2022-11-24 10:11
哦，原来写错了

抱歉，改过了

dolly_yos2

先说整体思路：根本依据是标准中的规定，但最后使用的是某个具体的实现，所以究竟是否和标准一致，尤其是标准中给出的是“推荐”或“建议”的时候还要看具体的实现。寻找相关信息的方法我记得我之前在另一个回复中提到过。
1和5：无论是标准还是 GCC 的手册里我都没有找到关于空间的规定或描述，我建议如果真的很重要的话在和评测平台尽可能相近的环境下进行实验测试来确定，至少对量级心中有数
2：当然不是，访问、查找和删除操作平均时间复杂度为常数，最坏情况是 O(size)
3：谁说出问题，出了什么问题？可以查阅一下实际测试环境使用的实现版本的 bug tracker 或者下一个版本的更新内容，看看这个版本有没有已知的问题报告，像是标准库的哪个部分或功能工作不正常，使用的时候避开它们。总的来说，出问题大概率是使用的不正确导致的
4：map 的访问、查找和删除均只说明了时间复杂度为对数级别，没有描述所谓“最坏情况”
6：有需要就用，没有特别推荐或者不推荐的理由
7：map 保证了遍历时符合指定的比较函数定义的序关系；不应该假设任何 unordered_map 中元素的顺序
8：看具体应用场景下哪个合适。一个细小的差别是 unordered 系列在插入元素时可能会无效化现有迭代器，而非 unordered 系列插入元素时永远不会

zhangjinxuan

yuxijian2020 发表于 2022-11-24 10:15
抱歉，改过了

我想我应该求稳，求空间少，以后就用 map 吧

这样吧，剩下的问题我之后追问，就把你设为最佳吧