46.C++中的map和unordered_map的区别和使用场景

2026-01-23
1921 字 · 10 分钟
C++ STL 容器 哈希表 红黑树

🔬 C++中的map和unordered_map的区别和使用场景

📋 总结

📖 内容概览 本文将详细介绍C++ STL中map和unordered_map两种关联容器的区别，包括它们的底层实现、性能特点、适用场景以及使用方法。通过对比分析，帮助开发者在实际项目中选择合适的容器。 📚 头文件与命名空间

容器类型所需头文件命名空间
map#include <map>std::map
unordered_map#include <unordered_map>std::unordered_map
🎯 底层实现原理

2.1 map的实现

map内部实现了一个红黑树（Red-Black Tree），这是一种非严格平衡的二叉搜索树，具有以下特点：

  • 自动排序特性：元素按照键的大小顺序存储
  • 每个节点包含键值对、父节点指针、左右子节点指针以及颜色标记
  • 基本操作（插入、查找、删除）的时间复杂度为O(log n)
  • 使用中序遍历可以按键值从小到大访问所有元素

2.2 unordered_map的实现

unordered_map内部实现了一个哈希表（Hash Table），通过哈希函数将键映射到桶（Bucket）中，具有以下特点：

  • 无序存储：元素的存储顺序与插入顺序无关
  • 由哈希表和链表/红黑树（解决冲突）组成
  • 平均情况下基本操作的时间复杂度为O(1)
  • 最坏情况下（哈希冲突严重）时间复杂度为O(n) 🔍 核心特性对比 | 特性 | map | unordered_map | |------|-----|---------------| | 内部结构 | 红黑树 | 哈希表 | | 元素顺序 | 有序（按键排序） | 无序 | | 查找速度 | O(log n) | 平均O(1)，最坏O(n) | | 插入速度 | O(log n) | 平均O(1)，最坏O(n) | | 删除速度 | O(log n) | 平均O(1)，最坏O(n) | | 内存占用 | 较低（每个节点仅需少量额外空间） | 较高（需要哈希表和冲突解决结构） | | 迭代器稳定性 | 插入/删除操作不会使迭代器失效（除了被删除的元素） | 插入可能导致rehash，使所有迭代器失效 | | 键类型要求 | 必须支持<运算符 | 必须支持哈希函数和==运算符 | ⚖️ 优缺点分析

4.1 map的优缺点

优点：

  • 元素自动排序，便于范围查找和遍历
  • 插入和删除操作稳定，迭代器不易失效
  • 内存使用相对高效
  • 适用于需要频繁进行范围查询的场景 缺点：
  • 查找和修改操作的时间复杂度为O(log n)，不如unordered_map高效
  • 不适合需要快速随机访问的场景

4.2 unordered_map的优缺点

  • 平均查找、插入、删除操作的时间复杂度为O(1)，效率极高
  • 适合需要频繁进行查找操作的场景
  • 元素无序，无法直接进行范围查询
  • 哈希表建立和rehash过程耗时
  • 内存占用较高
  • 迭代器在rehash时会失效 🛠️ 适用场景

5.1 适合使用map的场景

  1. 需要有序数据：当需要元素保持特定顺序时
  2. 范围查询频繁：需要经常使用lower_bound()、upper_bound()等范围查询函数
  3. 内存敏感场景：当可用内存有限时
  4. 插入删除频繁且需要迭代器稳定：当需要保持迭代器有效性时

5.2 适合使用unordered_map的场景

  1. 频繁查找操作：需要快速查找特定元素
  2. 对元素顺序无要求：不关心元素的存储顺序
  3. 大量随机访问：需要快速访问任意元素 💻 代码示例与使用方法

6.1 基本使用示例

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
    // 1. map的使用
    cout << "=== map示例 ===" << endl;
    map<int, string> mapExample;


    // 插入元素
    mapExample[1] = "张三";
    mapExample.insert(pair<int, string>(2, "李四"));
    mapExample.emplace(3, "王五");
    // 遍历元素（有序）
    for (const auto& pair : mapExample) {
        cout << pair.first << ": " << pair.second << endl;
    }
    // 查找元素
    auto mapIter = mapExample.find(2);
    if (mapIter != mapExample.end()) {
        cout << "找到元素: " << mapIter->second << endl;
    // 2. unordered_map的使用
    cout << "\n=== unordered_map示例 ===" << endl;
    unordered_map<int, string> unorderedMapExample;
    unorderedMapExample[1] = "张三";
    unorderedMapExample.insert(pair<int, string>(2, "李四"));
    unorderedMapExample.emplace(3, "王五");
    // 遍历元素（无序）
    for (const auto& pair : unorderedMapExample) {
        cout << pair.first << ": " << pair.second << endl;
    }


    // 查找元素
    auto unorderedMapIter = unorderedMapExample.find(2);
    if (unorderedMapIter != unorderedMapExample.end()) {
        cout << "找到元素: " << unorderedMapIter->second << endl;
    }
    return 0;
}

6.2 输出结果对比

map输出（有序）： === map示例 === 1: 张三 2: 李四 3: 王五 找到元素: 李四 unordered_map输出（无序）： === unordered_map示例 ===

6.3 常用操作汇总

操作函数签名功能描述
插入insert(const value_type& val)插入键值对
插入operator[](const key_type& k)访问或插入键值对
查找find(const key_type& k)查找键k，返回迭代器
计数count(const key_type& k)统计键k出现的次数（0或1）
删除erase(const key_type& k)删除键k对应的元素
大小size()返回元素个数
清空clear()清空所有元素
判空empty()判断容器是否为空
⏱️ 性能对比测试
以下是一个简单的性能对比测试，展示两种容器在不同操作下的性能差异：
#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>
#include <cstdlib>
#include <ctime>
using namespace std;
using namespace chrono;


const int TEST_SIZE = 1000000;


int main() {
    map<int, int> mapTest;
    unordered_map<int, int> unorderedMapTest;


    // 生成随机数据
    srand(time(nullptr));
    int* keys = new int[TEST_SIZE];
    for (int i = 0; i < TEST_SIZE; ++i) {
        keys[i] = rand();
    }


    // 测试map插入性能
    cout << "测试插入性能..." << endl;
    auto start = high_resolution_clock::now();
    for (int i = 0; i < TEST_SIZE; ++i) {
        mapTest[keys[i]] = i;
    }
    auto end = high_resolution_clock::now();
    auto mapInsertTime = duration_cast<milliseconds>(end - start).count();
    cout << "map插入时间: " << mapInsertTime << "ms" << endl;


    // 测试unordered_map插入性能
    start = high_resolution_clock::now();
    for (int i = 0; i < TEST_SIZE; ++i) {
        unorderedMapTest[keys[i]] = i;
    }
    end = high_resolution_clock::now();
    auto unorderedMapInsertTime = duration_cast<milliseconds>(end - start).count();
    cout << "unordered_map插入时间: " << unorderedMapInsertTime << "ms" << endl;


    // 测试map查找性能
    cout << "\n测试查找性能..." << endl;
    start = high_resolution_clock::now();
    for (int i = 0; i < TEST_SIZE; ++i) {
        mapTest.find(keys[i]);
    }
    end = high_resolution_clock::now();
    auto mapFindTime = duration_cast<milliseconds>(end - start).count();
    cout << "map查找时间: " << mapFindTime << "ms" << endl;


    // 测试unordered_map查找性能
    start = high_resolution_clock::now();
    for (int i = 0; i < TEST_SIZE; ++i) {
        unorderedMapTest.find(keys[i]);
    }
    end = high_resolution_clock::now();
    auto unorderedMapFindTime = duration_cast<milliseconds>(end - start).count();
    cout << "unordered_map查找时间: " << unorderedMapFindTime << "ms" << endl;


    delete[] keys;
    return 0;
}

🌟 最佳实践建议

  1. 优先考虑unordered_map：在大多数情况下，unordered_map的性能更优，尤其是查找操作频繁时
  2. 需要有序数据时使用map：当需要元素保持特定顺序或进行范围查询时
  3. 注意键类型的选择：
    • 对于map，确保键类型支持<运算符
    • 对于unordered_map，确保键类型有合适的哈希函数
  4. 自定义类型作为键：
    • 对于map，需要重载<运算符
    • 对于unordered_map，需要重载==运算符并提供哈希函数
  5. 内存与性能权衡：unordered_map通常比map占用更多内存，但提供更快的访问速度
  6. 避免频繁rehash：对于unordered_map，可以通过reserve()预先分配足够的空间，减少rehash次数 📋 总结 | 对比维度 | map | unordered_map | |---------|-----|---------------| | 实现机制 | 红黑树 | 哈希表 | | 元素顺序 | 有序 | 无序 | | 时间复杂度 | O(log n) | 平均O(1) | | 空间占用 | 较低 | 较高 | | 迭代器稳定性 | 稳定 | 不稳定（rehash时失效） | | 适用场景 | 有序数据、范围查询 | 频繁查找、对顺序无要求 | 在实际开发中，应根据具体需求选择合适的容器：
  • 如果需要有序数据或范围查询，选择map
  • 如果需要快速查找或大量随机访问，选择unordered_map
  • 考虑内存限制：map的内存占用更低
  • 考虑迭代器稳定性：map的迭代器更稳定 通过合理选择容器，可以显著提高程序的性能和效率，减少不必要的资源消耗。
Thanks for reading!

46.C++中的map和unordered_map的区别和使用场景

2026-01-23
1921 字 · 10 分钟
C++ STL 容器 哈希表 红黑树
© Gxy | CC BY-NC-SA 4.0
打赏作者
已复制链接
45.new可以重载吗，可以改写new函数吗
47.他们是线程安全的吗

评论区

分享你的想法，与大家交流讨论

目录