目录

📌 一、std::unordered_map 核心特性

📌 二、常用函数解析（附代码示例）

1. 构造函数

2. 插入与赋值

3. 查找与访问

4. 删除与清空

5. 桶操作与性能优化

📌 三、性能分析与优化建议

1. 时间复杂度对比

2. 性能优化建议

📌 四、常见陷阱与解决方案

1. 迭代器失效

2. 误用 operator[] 导致键插入

3. 自定义键类型未定义哈希函数

📌 五、典型应用场景

1. 统计词频

2. 缓存管理

3. 数据库索引

🧠 总结

C++从入门到入土学习导航_c++学习进程-CSDN博客

---

📌 一、std::unordered_map 核心特性

std::unordered_map 是 C++ STL 中的 无序关联容器，底层基于 哈希表（Hash Table） 实现，具有以下核心特性：

特性	说明
键值对存储	每个元素由唯一的键（Key）和对应的值（Value）组成。
无序性	元素存储顺序与插入顺序无关，按哈希值分布。
键唯一性	所有键必须唯一，重复键插入失败。
高效查找	查找、插入、删除的时间复杂度为 O(1)（平均情况）。
哈希冲突	多个键可能映射到同一哈希桶，通过链表或开放寻址法解决。

---

📌 二、常用函数解析（附代码示例）

1. 构造函数

#include <unordered_map>
#include <iostream>

int main() {
    // 1. 默认构造空 unordered_map
    std::unordered_map<int, std::string> um1;

    // 2. 初始化列表（C++11）
    std::unordered_map<int, std::string> um2 = {{1, "Apple"}, {2, "Banana"}};

    // 3. 范围初始化
    std::vector<std::pair<int, std::string>> vec = {{3, "Cherry"}, {4, "Date"}};
    std::unordered_map<int, std::string> um3(vec.begin(), vec.end());

    // 4. 复制构造
    std::unordered_map<int, std::string> um4 = um3;

    // 打印所有 unordered_map 内容
    for (const auto& [key, value] : um4) {
        std::cout << key << ": " << value << "\n";
    }
    return 0;
}

---

2. 插入与赋值

std::unordered_map<int, std::string> um;

// 1. insert() 插入
um.insert({1, "Apple"});  // 插入单个键值对
um.insert({{2, "Banana"}, {3, "Cherry"}});  // 插入多个键值对

// 2. operator[] 插入或赋值
um[4] = "Date";  // 插入新键值对
um[4] = "Dragonfruit";  // 修改已有键的值

// 3. emplace() 原地构造（C++11）
um.emplace(5, "Elderberry");  // 避免临时 pair 对象

// 4. try_emplace()（C++17）安全插入
um.try_emplace(6, "Fig");  // 如果键不存在才插入

---

3. 查找与访问

std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}, {3, "C"}};

// 1. find() 查找键是否存在
auto it = um.find(2);
if (it != um.end()) {
    std::cout << "Found: " << it->second << "\n";  // 输出 B
}

// 2. at() 访问（C++11）
try {
    std::cout << um.at(3) << "\n";  // 输出 C
    std::cout << um.at(4) << "\n";  // 抛出 std::out_of_range 异常
} catch (const std::out_of_range& e) {
    std::cout << "Key not found: " << e.what() << "\n";
}

// 3. count() 统计键出现次数（unordered_map 中为 0 或 1）
std::cout << "Count of 2: " << um.count(2) << "\n";  // 输出 1

---

4. 删除与清空

std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}, {3, "C"}};

// 1. erase() 删除单个键
um.erase(2);  // 删除键为 2 的元素

// 2. erase() 删除范围
um.erase(um.begin(), um.find(3));  // 删除前两个元素

// 3. clear() 清空 unordered_map
um.clear();
std::cout << "Size after clear: " << um.size() << "\n";  // 输出 0

---

5. 桶操作与性能优化

std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}, {3, "C"}};

// 1. 桶数量与负载因子
std::cout << "Bucket count: " << um.bucket_count() << "\n";
std::cout << "Load factor: " << um.load_factor() << "\n";

// 2. 重新调整桶数量（rehash）
um.rehash(10);  // 强制调整桶数量为 10

// 3. 设置最大负载因子
um.max_load_factor(0.75);  // 设置最大负载因子为 0.75

---

📌 三、性能分析与优化建议

1. 时间复杂度对比

操作类型	std::map	std::unordered_map
查找	O(log n)	O(1)（平均）
插入	O(log n)	O(1)（平均）
删除	O(log n)	O(1)（平均）
遍历	O(n)	O(n)

---

2. 性能优化建议

• 避免频繁插入重复键：unordered_map 会自动检查键唯一性，重复插入会增加哈希冲突开销。
• 预分配桶空间：通过 reserve() 预分配足够桶空间，减少 rehash 次数。
• 自定义哈希函数：对复杂键类型（如结构体）需自定义哈希函数和相等比较器。
• 优先使用 try_emplace 替代 operator[]：避免不必要的默认构造。

// 示例：自定义结构体键类型
struct Key {
    int a, b;
    bool operator==(const Key& other) const {
        return a == other.a && b == other.b;
    }
};

// 自定义哈希函数
struct KeyHash {
    std::size_t operator()(const Key& k) const {
        return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);
    }
};

std::unordered_map<Key, int, KeyHash> myMap;

---

📌 四、常见陷阱与解决方案

1. 迭代器失效

• 问题：unordered_map 插入/删除操作可能导致迭代器失效（尤其在 rehash 时）。
• 解决方案：插入后避免使用旧迭代器，删除后更新迭代器。

for (auto it = um.begin(); it != um.end(); ) {
    if (it->second == "A") {
        it = um.erase(it);  // 必须赋值给 it
    } else {
        ++it;
    }
}

---

2. 误用 operator[] 导致键插入

• 问题：operator[] 会自动插入默认值，可能导致意外行为。
• 解决方案：优先使用 find 或 at()。

std::unordered_map<int, std::string> um;
std::cout << um[42] << "\n";  // 自动插入键 42，值为空字符串

---

3. 自定义键类型未定义哈希函数

• 问题：键类型未定义哈希函数和相等比较器，编译报错。
• 解决方案：重载 operator== 并定义哈希结构体。

struct Key {
    int a, b;
    bool operator==(const Key& other) const {
        return a == other.a && b == other.b;
    }
};

struct KeyHash {
    std::size_t operator()(const Key& k) const {
        return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);
    }
};

std::unordered_map<Key, int, KeyHash> myMap;

---

📌 五、典型应用场景

1. 统计词频

• 适用场景：统计文本中单词出现次数。

#include <sstream>
#include <unordered_map>

std::unordered_map<std::string, int> wordCount;
std::string text = "hello world hello";
std::istringstream iss(text);
std::string word;

while (iss >> word) {
    ++wordCount[word];
}

for (const auto& [word, count] : wordCount) {
    std::cout << word << ": " << count << "\n";
}

---

2. 缓存管理

• 适用场景：实现 LRU 缓存或快速查找缓存项。

std::unordered_map<int, std::string> cache;
cache[1001] = "Alice";
cache[1002] = "Bob";

auto it = cache.find(1001);
if (it != cache.end()) {
    std::cout << "Cached: " << it->second << "\n";
}

---

3. 数据库索引

• 适用场景：快速查找数据库记录。

std::unordered_map<int, User> userDB;
userDB[1001] = {"Alice", 25};
userDB[1002] = {"Bob", 30};

auto it = userDB.find(1001);
if (it != userDB.end()) {
    std::cout << "User: " << it->second.name << "\n";
}

---

🧠 总结

特性	适用场景	优势	注意事项
无序性	不需要有序数据	查找/插入 O(1)	遍历顺序不稳定
哈希冲突	高性能场景	平均 O(1) 操作	需优化哈希函数
自定义键	复杂键类型	灵活扩展	需实现哈希和比较器
内存效率	内存敏感场景	内存占用较低	rehash 开销较高