目录
概述
<unordered_map> 是 C++ STL 中的无序关联容器，用于存储键值对（key-value pairs）。它基于哈希表实现，键是唯一的，元素不按任何顺序排列。相比 <map>，它提供更快的平均查找性能，但牺牲了排序功能。
包含头文件
#include <unordered_map>
#include <iostream>
定义格式
std::unordered_map<键类型, 值类型, 哈希函数, 相等比较器> 变量名;
键类型：键的数据类型（如int、std::string）。值类型：值的数据类型（如int、double）。哈希函数：可选，默认是std::hash<Key>。相等比较器：可选，默认是std::equal_to<Key>。
基本特性
- 键唯一性：每个键只能对应一个值。
- 无序存储：键值对不按任何顺序排列。
- 高效操作：平均时间复杂度 O(1)（插入、删除、查找），最坏 O(n)（哈希冲突时）。
- 动态大小：支持运行时调整。
基本用法
声明和初始化
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um; // 空 unordered_map
std::unordered_map<int, std::string> um2 = {{1, "A"}, {2, "B"}, {3, "C"}}; // 初始化列表（C++11）
std::cout << "um2: ";
for (const auto& pair : um2) {
std::cout << "{" << pair.first << ", " << pair.second << "} ";
}
std::cout << std::endl; // 输出顺序不定，如：{3, C} {1, A} {2, B}
return 0;
}
插入元素
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um;
um.insert({1, "Alice"}); // 插入键值对
um.insert(std::make_pair(2, "Bob"));
um[3] = "Charlie"; // 使用 [] 插入或覆盖
std::cout << "um: ";
for (const auto& pair : um) {
std::cout << "{" << pair.first << ", " << pair.second << "} ";
}
std::cout << std::endl; // 输出顺序不定，如：{2, Bob} {3, Charlie} {1, Alice}
return 0;
}
删除元素
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}, {3, "C"}};
um.erase(2); // 删除键为 2 的元素
std::cout << "After erase: ";
for (const auto& pair : um) {
std::cout << "{" << pair.first << ", " << pair.second << "} ";
}
std::cout << std::endl; // 输出顺序不定，如：{1, A} {3, C}
return 0;
}
查找元素
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}, {3, "C"}};
auto it = um.find(2); // 查找键为 2 的元素
if (it != um.end()) {
std::cout << "Found: {" << it->first << ", " << it->second << "}" << std::endl; // 输出：Found: {2, B}
}
if (um.count(1)) {
std::cout << "Key 1 exists" << std::endl; // 输出：Key 1 exists
}
return 0;
}
访问和修改元素
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}};
std::cout << "Value at 1: " << um[1] << std::endl; // 输出：A
um[1] = "Alice"; // 修改值
std::cout << "New value at 1: " << um.at(1) << std::endl; // 输出：Alice
// um.at(3) 若键不存在会抛出 std::out_of_range
return 0;
}
[]：若键不存在，插入默认值。at()：若键不存在，抛异常。
大小和状态
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}};
std::cout << "Size: " << um.size() << std::endl; // 输出：2
std::cout << "Empty? " << (um.empty() ? "Yes" : "No") << std::endl; // 输出：No
return 0;
}
哈希表特性
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}, {3, "C"}};
std::cout << "Bucket count: " << um.bucket_count() << std::endl; // 桶数
std::cout << "Load factor: " << um.load_factor() << std::endl; // 当前负载因子
std::cout << "Max load factor: " << um.max_load_factor() << std::endl; // 最大负载因子
return 0;
}
迭代器
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<int, std::string> um = {{1, "A"}, {2, "B"}, {3, "C"}};
std::cout << "Elements: ";
for (auto it = um.begin(); it != um.end(); ++it) {
std::cout << "{" << it->first << ", " << it->second << "} ";
}
std::cout << std::endl; // 输出顺序不定，如：{3, C} {1, A} {2, B}
return 0;
}
- 仅支持前向迭代器，无逆向迭代。
与 <map> 的对比
| 特性 | std::unordered_map | std::map |
|---|---|---|
| 数据结构 | 哈希表 | 平衡二叉树 |
| 键顺序 | 无序 | 升序 |
| 重复键 | 不允许 | 不允许 |
| 查找 | 平均 O(1) | O(log n) |
| 插入/删除 | 平均 O(1) | O(log n) |
| 内存开销 | 桶+指针 | 树节点+指针 |
| 迭代器 | 前向 | 双向 |
注意事项
- 哈希冲突：冲突严重时性能退化为 O(n)，需优化哈希函数。
- 迭代器失效：插入不影响现有迭代器，删除使指向被删元素的迭代器失效。
- 自定义键类型：需提供哈希函数和相等比较器。
[]的副作用：访问不存在的键会插入默认值。
自定义键类型示例
#include <unordered_map>
#include <iostream>
#include <string>
struct CustomKey {
std::string name;
int id;
bool operator==(const CustomKey& other) const {
return name == other.name && id == other.id;
}
};
namespace std {
template<> struct hash<CustomKey> {
size_t operator()(const CustomKey& k) const {
return hash<string>()(k.name) ^ hash<int>()(k.id);
}
};
}
int main() {
std::unordered_map<CustomKey, int> um;
um[{"Alice", 1}] = 95;
um[{"Bob", 2}] = 87;
for (const auto& pair : um) {
std::cout << "{" << pair.first.name << ", " << pair.first.id << "}: " << pair.second << "\n";
}
return 0;
}
实用示例：单词计数器
#include <unordered_map>
#include <iostream>
#include <string>
int main() {
std::unordered_map<std::string, int> wordCount;
std::string word;
std::cout << "Enter words (Ctrl+D or Ctrl+Z to stop):\n";
while (std::cin >> word) {
wordCount[word]++;
}
std::cout << "Word frequencies:\n";
for (const auto& pair : wordCount) {
std::cout << pair.first << ": " << pair.second << "\n";
}
return 0;
}
输入示例：
apple banana apple cherry
Ctrl+D
输出（顺序不定）：
Word frequencies:
apple: 2
banana: 1
cherry: 1
小练习
问题
写一个 C++ 程序：
- 定义一个
std::unordered_map<int, std::string>。 - 插入键值对：{1, “A”}、{2, “B”}、{3, “C”}、{2, “D”}（注意重复键）。
- 删除键为 1 的元素。
- 输出所有键值对和大小。
参考答案
#include <unordered_map>
#include <iostream>
#include <string>
int main() {
std::unordered_map<int, std::string> um;
// 插入元素
um.insert({1, "A"});
um.insert({2, "B"});
um.insert({3, "C"});
um[2] = "D"; // 覆盖键 2 的值
// 删除键 1
um.erase(1);
// 输出所有键值对和大小
std::cout << "Elements: ";
for (const auto& pair : um) {
std::cout << "{" << pair.first << ", " << pair.second << "} ";
}
std::cout << "\nSize: " << um.size() << std::endl;
return 0;
}
输出（顺序不定）：
Elements: {2, D} {3, C}
Size: 2
参考资料
- C++ Standard Library Reference:
<unordered_map>的官方文档。
- ISO/IEC 14882:2011 (C++11 Standard)
- cppreference.com: 提供
<unordered_map>的详细说明和示例。 - The C++ Programming Language (4th Edition) by Bjarne Stroustrup: C++ 容器权威书籍。
- Effective STL by Scott Meyers: STL 容器实用建议。
出站链接
- cppreference.com: std::unordered_map – 官方文档和示例。
- C++ Reference: std::unordered_map – 接口说明。
- GeeksforGeeks: unordered_map in C++ – 教程和代码示例。
- LearnCpp: Introduction to std::unordered_map – 初学者教程。
下一步
- 如果你想试试练习，请提交代码，我会帮你检查。
- 如果需要更深入内容（如自定义哈希优化、与
<unordered_multimap>对比），或设计测验题，请告诉我！ - 你也可以提出具体问题，如“如何用
<unordered_map>实现缓存？”或“<unordered_map>的哈希表实现细节？”。
现在，你想做什么？试试练习，还是有其他需求？
发表回复