map 和 unordered_map 都是 C++ STL 里的关联容器，都可以用来存储这种结构：

key -> value

比如：

std::map<std::string, int> mp;
std::unordered_map<std::string, int> ump;

mp["apple"] = 10;
ump["apple"] = 10;

它们最大的区别是：底层数据结构不同，所以查找效率、是否有序、使用场景都不同。

---

1. map：底层一般是红黑树

std::map 的底层通常是红黑树，也就是一种平衡二叉搜索树。

它的特点是：key 会自动按顺序排列。

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string, int> mp;

    mp["banana"] = 2;
    mp["apple"] = 1;
    mp["cat"] = 3;

    for (auto& [key, value] : mp) {
        cout << key << " " << value << endl;
    }

    return 0;
}

输出结果是：

apple 1
banana 2
cat 3

虽然插入顺序是：

banana -> apple -> cat

但是 map 会按照 key 自动排序。

所以 map 的核心特点是：

有序
底层一般是红黑树
查找、插入、删除复杂度是 O(log n)

---

2. unordered_map：底层是哈希表

std::unordered_map 的底层是哈希表。

它不关心顺序，而是通过哈希函数快速定位元素。

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> ump;

    ump["banana"] = 2;
    ump["apple"] = 1;
    ump["cat"] = 3;

    for (auto& [key, value] : ump) {
        cout << key << " " << value << endl;
    }

    return 0;
}

输出顺序是不固定的，可能是：

cat 3
apple 1
banana 2

也可能是别的顺序。

所以 unordered_map 的核心特点是：

无序
底层是哈希表
平均查找、插入、删除复杂度是 O(1)
最坏情况下可能退化到 O(n)

---

3. 核心区别总结

对比项	map	unordered_map
底层结构	红黑树	哈希表
是否有序	有序，按 key 排序	无序
查找效率	O(log n)	平均 O(1)
插入效率	O(log n)	平均 O(1)
删除效率	O(log n)	平均 O(1)
最坏情况	O(log n)	O(n)
key 的要求	需要能比较大小	需要能计算哈希值
适合场景	需要有序遍历、范围查找	只关心快速增删改查

---

4. 使用时怎么选？

一句话：

不需要顺序，优先用 unordered_map；需要 key 有序，使用 map。

比如你只是想快速根据用户名查信息：

unordered_map<string, User> users;

这种场景下，unordered_map 更合适，因为你只关心：

users["zhangsan"]

能不能快速找到。

---

如果你需要按 key 的顺序遍历：

map<int, string> students;

比如学号从小到大输出：

for (auto& [id, name] : students) {
    cout << id << " " << name << endl;
}

这种就应该用 map。

---

5. map 适合的场景

map 适合这些情况：

1. 需要按 key 自动排序
2. 需要范围查询
3. 需要找大于等于某个 key 的第一个元素
4. 需要稳定的 O(log n) 性能

比如：

map<int, string> mp;

mp[10] = "A";
mp[20] = "B";
mp[30] = "C";

查找第一个大于等于 15 的元素：

auto it = mp.lower_bound(15);

if (it != mp.end()) {
    cout << it->first << " " << it->second << endl;
}

输出：

20 B

这种范围查找、顺序查找是 map 的优势。

---

6. unordered_map 适合的场景

unordered_map 适合这些情况：

1. 不关心顺序
2. 只需要快速查找
3. key 是 string、int 这类常见类型
4. 数据量比较大，希望查询快

比如统计单词出现次数：

unordered_map<string, int> count;

count["apple"]++;
count["banana"]++;
count["apple"]++;

这种场景下，unordered_map 一般比 map 更合适。

---

7. 一个很重要的细节：operator[] 会插入元素

无论是 map 还是 unordered_map，使用 [] 访问不存在的 key，都会自动插入一个默认值。

例如：

unordered_map<string, int> mp;

cout << mp["hello"] << endl;

这时候 "hello" 原本不存在，但是执行之后，容器里会多出：

"hello" -> 0

所以如果你只是想判断 key 是否存在，建议用：

if (mp.find("hello") != mp.end()) {
    cout << "exist" << endl;
}

C++20 之后也可以用：

if (mp.contains("hello")) {
    cout << "exist" << endl;
}

8. 总结

默认用 unordered_map
需要有序时用 map
需要范围查询时用 map
需要极致平均查询速度时用 unordered_map
担心哈希冲突或需要稳定复杂度时用 map

实际工程里，很多时候会优先考虑 unordered_map，因为它平均 O(1)，适合高频查找。

但是 map 的优势是它有序，而且性能上界更稳定。

最终总结一句：

map 是基于树的有序 key-value 容器，适合排序和范围查询；unordered_map 是基于哈希表的无序 key-value 容器，适合快速查找。普通查询优先 unordered_map，需要顺序或范围操作时选择 map。