本文最后更新于 34 天前，其中的信息可能已经有所发展或是发生改变。
一、基本概念对比
1. 共同点
- 都是关联容器，存储键值对（key-value pairs）
- 提供快速的查找、插入、删除操作
- 键（key）唯一，不能重复
2. 核心区别
| 特性 | map | unordered_map |
|---|---|---|
| 底层实现 | 红黑树（平衡二叉搜索树） | 哈希表 |
| 排序 | 按键的升序自动排序 | 无序 |
| 查找时间复杂度 | O(log n) | 平均O(1)，最坏O(n) |
| 内存占用 | 较低 | 较高（哈希表需要额外空间） |
| 迭代器稳定性 | 稳定（插入删除不影响其他元素） | 插入可能使所有迭代器失效 |
二、map（有序映射）
1. 基本特性和头文件
#include <iostream>
#include <map> // map头文件
#include <string>
using namespace std;
int main() {
// 创建map
map<string, int> studentScores;
return 0;
}2. map的常用操作
插入数据的三种方式
map<string, int> scores;
// 方式1：使用insert和pair
scores.insert(pair<string, int>("Alice", 95));
scores.insert(make_pair("Bob", 88));
// 方式2：使用insert和花括号（C++11）
scores.insert({"Charlie", 92});
// 方式3：使用[]操作符（最常用）
scores["David"] = 87;
scores["Eve"] = 91;
// 注意：如果键已存在，insert不会覆盖，[]会覆盖
scores.insert({"David", 50}); // 不会插入，David还是87
scores["David"] = 100; // 覆盖，David变为100查找和访问
map<string, int> scores = {{"Alice", 95}, {"Bob", 88}};
// 方式1：使用[]（如果键不存在会创建）
cout << "Alice: " << scores["Alice"] << endl; // 95
// 注意：使用不存在的键会创建新元素（值为默认值）
cout << "Unknown: " << scores["Unknown"] << endl; // 创建并输出0
// 方式2：使用at()（安全访问，键不存在会抛出异常）
try {
cout << "Bob: " << scores.at("Bob") << endl; // 88
cout << "Invalid: " << scores.at("Invalid") << endl; // 抛出异常
} catch (const out_of_range& e) {
cout << "键不存在: " << e.what() << endl;
}
// 方式3：使用find()（推荐的安全查找）
auto it = scores.find("Alice");
if (it != scores.end()) {
cout << "找到Alice: " << it->second << endl;
} else {
cout << "未找到Alice" << endl;
}遍历map
map<string, int> scores = {{"Alice", 95}, {"Bob", 88}, {"Charlie", 92}};
// 方式1：使用迭代器（自动按键排序）
cout << "=== 迭代器遍历 ===" << endl;
for (auto it = scores.begin(); it != scores.end(); ++it) {
cout << it->first << ": " << it->second << endl;
}
// 输出：Alice: 95, Bob: 88, Charlie: 92（按键排序）
// 方式2：范围for循环（推荐）
cout << "=== 范围for循环 ===" << endl;
for (const auto& pair : scores) {
cout << pair.first << ": " << pair.second << endl;
}
// 方式3：使用结构化绑定（C++17）
cout << "=== 结构化绑定 ===" << endl;
for (const auto& [name, score] : scores) {
cout << name << ": " << score << endl;
}删除操作
map<string, int> scores = {
{"Alice", 95}, {"Bob", 88}, {"Charlie", 92}, {"David", 87}
};
// 方式1：通过键删除
scores.erase("Bob"); // 删除Bob
// 方式2：通过迭代器删除
auto it = scores.find("Charlie");
if (it != scores.end()) {
scores.erase(it); // 删除Charlie
}
// 方式3：删除一个范围
auto first = scores.find("Alice");
auto last = scores.end();
scores.erase(first, last); // 删除从Alice到末尾的所有元素
cout << "剩余元素数量: " << scores.size() << endl; // 0其他常用操作
map<string, int> scores = {{"Alice", 95}, {"Bob", 88}};
// 检查大小
cout << "元素个数: " << scores.size() << endl;
cout << "是否为空: " << (scores.empty() ? "是" : "否") << endl;
// 清空map
scores.clear();
// 检查键是否存在
if (scores.count("Alice") > 0) {
cout << "Alice存在" << endl;
} else {
cout << "Alice不存在" << endl;
}三、unordered_map（无序映射）
1. 基本特性和头文件
#include <iostream>
#include <unordered_map> // unordered_map头文件
#include <string>
using namespace std;
int main() {
// 创建unordered_map
unordered_map<string, int> studentScores;
return 0;
}2. unordered_map的常用操作
基本使用（与map类似）
unordered_map<string, int> scores;
// 插入数据
scores["Alice"] = 95;
scores["Bob"] = 88;
scores["Charlie"] = 92;
// 查找数据
if (scores.find("Alice") != scores.end()) {
cout << "Alice的成绩: " << scores["Alice"] << endl;
}
// 遍历（无序！）
for (const auto& [name, score] : scores) {
cout << name << ": " << score << endl;
}
// 输出顺序不确定，可能是Charlie, Bob, Alice等哈希表的特殊操作
unordered_map<string, int> scores = {{"Alice", 95}, {"Bob", 88}};
// 查看桶信息
cout << "桶数量: " << scores.bucket_count() << endl;
cout << "负载因子: " << scores.load_factor() << endl;
cout << "最大负载因子: " << scores.max_load_factor() << endl;
// 遍历每个桶
for (size_t i = 0; i < scores.bucket_count(); ++i) {
cout << "桶 " << i << " 有 " << scores.bucket_size(i) << " 个元素" << endl;
}
// 调整哈希表性能
scores.rehash(100); // 设置至少100个桶
scores.reserve(200); // 预留空间给200个元素四、性能对比实战
测试代码
#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <vector>
using namespace std;
using namespace std::chrono;
void testPerformance() {
const int ELEMENT_COUNT = 100000;
vector<int> keys;
vector<int> values;
// 生成随机数据
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 1000000);
for (int i = 0; i < ELEMENT_COUNT; ++i) {
keys.push_back(dis(gen));
values.push_back(dis(gen));
}
// 测试map插入性能
auto start = high_resolution_clock::now();
map<int, int> orderedMap;
for (int i = 0; i < ELEMENT_COUNT; ++i) {
orderedMap[keys[i]] = values[i];
}
auto end = high_resolution_clock::now();
auto mapInsertTime = duration_cast<milliseconds>(end - start);
// 测试unordered_map插入性能
start = high_resolution_clock::now();
unordered_map<int, int> unorderedMap;
for (int i = 0; i < ELEMENT_COUNT; ++i) {
unorderedMap[keys[i]] = values[i];
}
end = high_resolution_clock::now();
auto unorderedMapInsertTime = duration_cast<milliseconds>(end - start);
// 测试查找性能
start = high_resolution_clock::now();
for (int i = 0; i < ELEMENT_COUNT; ++i) {
orderedMap.find(keys[i]);
}
end = high_resolution_clock::now();
auto mapFindTime = duration_cast<milliseconds>(end - start);
start = high_resolution_clock::now();
for (int i = 0; i < ELEMENT_COUNT; ++i) {
unorderedMap.find(keys[i]);
}
end = high_resolution_clock::now();
auto unorderedMapFindTime = duration_cast<milliseconds>(end - start);
cout << "=== 性能测试结果（" << ELEMENT_COUNT << "个元素）===" << endl;
cout << "map插入时间: " << mapInsertTime.count() << "ms" << endl;
cout << "unordered_map插入时间: " << unorderedMapInsertTime.count() << "ms" << endl;
cout << "map查找时间: " << mapFindTime.count() << "ms" << endl;
cout << "unordered_map查找时间: " << unorderedMapFindTime.count() << "ms" << endl;
}
int main() {
testPerformance();
return 0;
}五、实际应用场景
场景1：单词频率统计（适合unordered_map）
#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
using namespace std;
void wordFrequency(const string& text) {
unordered_map<string, int> freq;
istringstream iss(text);
string word;
// 统计单词频率
while (iss >> word) {
// 转换为小写
for (char& c : word) {
c = tolower(c);
}
freq[word]++;
}
// 输出结果（无序）
cout << "单词频率统计:" << endl;
for (const auto& [word, count] : freq) {
cout << word << ": " << count << endl;
}
}
int main() {
string text = "Hello world hello C++ world programming C++";
wordFrequency(text);
return 0;
}场景2：学生成绩管理系统（适合map，需要排序）
#include <iostream>
#include <map>
#include <string>
using namespace std;
class GradeSystem {
private:
map<string, int> grades; // 按姓名排序
public:
void addGrade(const string& name, int grade) {
grades[name] = grade;
}
void printAllGrades() {
cout << "=== 所有学生成绩（按姓名排序）===" << endl;
for (const auto& [name, grade] : grades) {
string level;
if (grade >= 90) level = "优秀";
else if (grade >= 80) level = "良好";
else if (grade >= 60) level = "及格";
else level = "不及格";
cout << name << ": " << grade << " (" << level << ")" << endl;
}
}
void findGrade(const string& name) {
auto it = grades.find(name);
if (it != grades.end()) {
cout << name << "的成绩是: " << it->second << endl;
} else {
cout << "未找到学生: " << name << endl;
}
}
};
int main() {
GradeSystem system;
system.addGrade("张三", 85);
system.addGrade("李四", 92);
system.addGrade("王五", 78);
system.addGrade("赵六", 88);
system.printAllGrades();
cout << endl;
system.findGrade("李四");
system.findGrade("钱七");
return 0;
}场景3：缓存系统（适合unordered_map）
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
template<typename Key, typename Value>
class LRUCache {
private:
struct Node {
Key key;
Value value;
Node* prev;
Node* next;
Node(Key k, Value v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
unordered_map<Key, Node*> cache;
Node* head;
Node* tail;
size_t capacity;
void moveToHead(Node* node) {
// 实现LRU逻辑
}
public:
LRUCache(size_t cap) : capacity(cap), head(nullptr), tail(nullptr) {}
Value* get(const Key& key) {
auto it = cache.find(key);
if (it != cache.end()) {
moveToHead(it->second);
return &(it->second->value);
}
return nullptr;
}
void put(const Key& key, const Value& value) {
// 实现插入逻辑
}
};六、自定义类型作为键
1. 在map中使用自定义类型
#include <iostream>
#include <map>
using namespace std;
struct Student {
string name;
int id;
// 需要定义小于操作符用于排序
bool operator<(const Student& other) const {
if (name == other.name) {
return id < other.id;
}
return name < other.name;
}
};
int main() {
map<Student, int> scores;
scores[{"Alice", 1001}] = 95;
scores[{"Bob", 1002}] = 88;
scores[{"Alice", 1003}] = 92; // 不同的ID，可以存在
for (const auto& [student, score] : scores) {
cout << student.name << "(" << student.id << "): " << score << endl;
}
return 0;
}2. 在unordered_map中使用自定义类型
#include <iostream>
#include <unordered_map>
using namespace std;
struct Student {
string name;
int id;
// 需要定义相等操作符
bool operator==(const Student& other) const {
return name == other.name && id == other.id;
}
};
// 需要定义哈希函数
struct StudentHash {
size_t operator()(const Student& s) const {
return hash<string>()(s.name) ^ hash<int>()(s.id);
}
};
int main() {
unordered_map<Student, int, StudentHash> scores;
scores[{"Alice", 1001}] = 95;
scores[{"Bob", 1002}] = 88;
for (const auto& [student, score] : scores) {
cout << student.name << "(" << student.id << "): " << score << endl;
}
return 0;
}七、选择指南
什么时候用map？
- 需要有序遍历：按键排序输出
- 内存敏感：哈希表有额外内存开销
- 需要稳定的性能：红黑树保证O(log n)操作
- 键的比较操作简单：只需要定义<操作符
什么时候用unordered_map？
- 查找性能关键：需要O(1)平均查找时间
- 不需要排序：不关心元素的顺序
- 哈希函数高效：有良好的哈希函数实现
- 内存充足：可以接受哈希表的额外开销
八、重要注意事项
1. 迭代器失效问题
// map：迭代器相对稳定
map<int, int> m = {{1, 10}, {2, 20}, {3, 30}};
auto it = m.find(2);
m.erase(1); // 删除其他元素，it仍然有效
cout << it->first << ": " << it->second << endl; // 安全
// unordered_map：插入可能使所有迭代器失效
unordered_map<int, int> um = {{1, 10}, {2, 20}};
auto it2 = um.find(2);
um[3] = 30; // 插入可能引起rehash
// cout << it2->first << endl; // 危险！可能失效2. []操作符的副作用
map<string, int> m;
// ❌ 错误用法：检查键是否存在
if (m["key"] == 0) { // 如果key不存在，会创建新元素！
cout << "键不存在" << endl;
}
// ✅ 正确用法：使用find检查
if (m.find("key") == m.end()) {
cout << "键不存在" << endl;
}九、总结表格
| 操作 | map | unordered_map |
|---|---|---|
| 插入 | O(log n) | 平均O(1)，最坏O(n) |
| 查找 | O(log n) | 平均O(1)，最坏O(n) |
| 删除 | O(log n) | 平均O(1)，最坏O(n) |
| 遍历 | 有序 | 无序 |
| 内存 | 较低 | 较高 |
| 稳定性 | 高 | 低（哈希冲突时） |
十、最佳实践口诀
选择容器要慎重，需求分析第一步
需要排序用map，红黑树来保证序
追求速度unordered，哈希表来加速查
内存紧张选map少，空间充足unordered
自定义键要注意，比较哈希要定义
迭代器失效要小心，unordered插入要当心通过这个详细指南，你应该能够根据具体需求在map和unordered_map之间做出明智的选择！