c++中std::map和std::unordered_map怎么选_map与unordered_map的区别与性能对比-C++-PHP中文网

c++中std::map和std::unordered_map怎么选_map与unordered_map的区别与性能对比

下次还敢

发布： 2025-10-31 16:59:02

原创

129人浏览过

std::map基于红黑树实现，有序且操作稳定O(log n)；std::unordered_map基于哈希表，平均O(1)但最坏O(n)，无序且内存开销大。

c++中std::map和std::unordered_map怎么选_map与unordered_map的区别与性能对比

在C++中，std::map 和 std::unordered_map 都是关联容器，用于存储键值对。它们都能实现快速查找，但在底层实现、性能特征和使用场景上有显著区别。选择哪一个取决于具体需求。

1. 底层实现不同

std::map 基于红黑树（一种自平衡二叉搜索树）实现，元素按键的顺序自动排序。默认情况下是升序排列。

std::unordered_map 基于哈希表实现，元素无固定顺序，依赖哈希函数将键映射到桶中。

2. 性能对比

这是选择的关键因素：

立即学习“C++免费学习笔记（深入）”；

插入/删除/查找时间复杂度：
- std::map：稳定为 O(log n)
- std::unordered_map：平均 O(1)，最坏情况 O(n)（哈希冲突严重时）
内存开销：
- std::map 每个节点有左右子指针和颜色标记，额外开销较小但存在
- std::unordered_map 需要维护哈希桶数组，可能预留大量空间以减少冲突，内存占用通常更高
缓存局部性：
- std::map 是树结构，访问分散，缓存表现较差
- std::unordered_map 的桶通常是连续内存，命中时缓存友好，性能更优

3. 是否需要有序遍历

如果你需要按键有序地遍历数据，比如输出从最小到最大的所有键值对，必须用 std::map。

例如：

for (const auto& [k, v] : my_map) {
    std::cout << k << ": " << v << "\n";
}

登录后复制

这段代码在 std::map 中会有序输出，在 std::unordered_map 中顺序不可预测。

Calliper 文档对比神器

文档内容对比神器

查看详情

4. 键类型的限制

std::map 只要求键支持比较操作（默认小于

std::unordered_map 要求键类型有合适的哈希函数。标准类型如 int、string 已内置 hash，自定义类型需提供 hash 特化或传入仿函数。

例如自定义结构体作为 key 时，使用 unordered_map 需额外工作：

struct Point {
    int x, y;
};

struct Hash {
    size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) ^ std::hash<int>{}(p.y);
    }
};

std::unordered_map<Point, int, Hash> umap;

登录后复制