unordered_map比map慢？
先说结论：unordered_map不维护键的顺序，因此不能按顺序访问元素，因此如果你需要遍历表时若选用unordered_map就肯定比map慢1. 数据结构与底层实现
[*]unordered_map：基于 哈希表 实现。
[*]优点：平均情况下插入、查找和删除操作的时间复杂度为 O(1)O(1)O(1)。
[*]缺点：最坏情况下，时间复杂度可能退化为 O(n)O(n)O(n)（当哈希冲突严重时）。
[*]无序存储，不能按键排序。
[*]map：基于 红黑树（自平衡二叉搜索树） 实现。
[*]优点：插入、查找和删除操作的时间复杂度始终为 O(logn)O(\log n)O(logn)。
[*]缺点：由于需要维护树的平衡，常数因子较大。
[*]按键排序，支持有序遍历。
<hr>2. 插入和查找性能
[*]unordered_map 优势：在大多数情况下，unordered_map 插入和查找的性能优于 map，因为其平均时间复杂度为 O(1)O(1)O(1)。
[*]map 劣势：map 的插入和查找性能稍慢，时间复杂度为 O(logn)O(\log n)O(logn)。
例外情况：
[*]哈希冲突严重：如果 unordered_map 的哈希函数设计不佳或数据分布极端（如大量相同的哈希值），性能可能退化为 O(n)O(n)O(n)。
[*]小规模数据：对于数据规模较小的情况，map 的性能可能优于 unordered_map，因为红黑树的实现有较少的额外开销。
<hr>3. 内存使用
[*]unordered_map 缺点：由于哈希表需要额外的存储空间（如空槽和链表节点），unordered_map 通常比 map 占用更多内存。
[*]map 优势：map 是基于树的实现，占用内存相对较少。
<hr>4. 顺序访问
[*]unordered_map 缺点：unordered_map 不维护键的顺序，因此不能按顺序访问元素。
[*]map 优势：map 自动按键的升序（或指定的比较函数）维护元素顺序，支持有序遍历。
<hr>5. 插入、删除时对迭代器的影响
[*]unordered_map：当发生哈希表的重哈希（rehash）操作时，会使所有迭代器失效。
[*]map：插入和删除元素只会影响相关位置的迭代器，其余迭代器不会失效。
<hr>6. 适用场景
场景推荐使用容器原因快速查找/插入操作unordered_map平均时间复杂度 O(1)O(1)O(1)。数据需要按键排序map支持有序遍历。数据规模较小map红黑树常数因子较小。内存有限mapunordered_map 占用内存较大。哈希函数性能不佳或数据分布差mapunordered_map 性能退化明显。7.举例
B. Gorilla and the Exam
代码：
#include <iostream>#include <algorithm>#include <map>#include <vector>using namespace std;int main() { int t; scanf("%d", &t); while (t--) { int n, k; scanf("%d %d", &n, &k); // 统计频次 map<int, int> times; for (int i = 0; i < n; i++) { int c; scanf("%d", &c); times++; } // 提取频次并排序 vector<int> freq; for (auto it : times) { freq.push_back(it.second); } sort(freq.begin(), freq.end()); // 计算移除最小的 k 次后剩余种类 int m = freq.size(); for (int i = 0; i < m; i++) { if (freq > k) { printf("%d\n", m - i); goto next_case; } k -= freq; } printf("1\n"); next_case:; } return 0;}若这个代码改为unordered_map将会超时，有兴趣的同学可以去提交试试！
总结
[*]如果需要快速插入、删除和查找操作且不关心顺序，优先选择 unordered_map。
[*]如果需要按键排序或者可能遇到哈希冲突问题，选择 map。
[*]如果内存占用敏感，选择 map。
页:
[1]