面试题：C++ 中 map 和 unordered_map 的区别？分别在什么场景下使用？

在 C++ 中，std::map 和 std::unordered_map 是两种常用的关联容器，用于存储键值对。它们的核心区别在于底层实现和性能特性，因此适用于不同的场景。

1. `std::map`

底层实现：基于红黑树（一种平衡二叉搜索树）。
特性：
- 元素按键的顺序存储（默认按升序排列）。
- 插入、删除和查找操作的时间复杂度为 O(log n)。
- 支持范围查询（如查找某个范围内的键）。
- 内存占用较高（需要存储树结构的相关信息）。
使用场景：
- 需要元素按键排序的场景。
- 需要频繁进行范围查询的场景。
- 对性能要求不是特别高，但需要稳定性能的场景。

示例：

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> m;
    m["apple"] = 3;
    m["banana"] = 5;
    m["cherry"] = 2;

    // 元素按键排序
    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

输出：

apple: 3
banana: 5
cherry: 2

2. `std::unordered_map`

底层实现：基于哈希表。
特性：
- 元素无序存储（顺序取决于哈希函数）。
- 插入、删除和查找操作的平均时间复杂度为 O(1)，最坏情况下为 O(n)（哈希冲突严重时）。
- 不支持范围查询。
- 内存占用较低（哈希表的开销较小）。
使用场景：
- 需要快速查找、插入和删除的场景。
- 不需要元素按键排序的场景。
- 对性能要求较高的场景。

示例：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> um;
    um["apple"] = 3;
    um["banana"] = 5;
    um["cherry"] = 2;

    // 元素无序存储
    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

输出：

cherry: 2
banana: 5
apple: 3

3. 关键区别

特性	`std::map`	`std::unordered_map`
底层实现	红黑树（平衡二叉搜索树）	哈希表
元素顺序	按键排序	无序
插入/删除/查找	O(log n)	平均 O(1)，最坏 O(n)
范围查询	支持	不支持
内存占用	较高	较低
适用场景	需要排序或范围查询	需要快速查找、插入和删除