C++中的 map vs unordered_map：選錯容器讓你的程序慢十倍！
作者：xiaokang1998
今天我就帶大家徹底搞清楚map 和 unordered_map這兩個容器的區別，記住這些區別，下次寫代碼時，就能輕松選擇正確的容器，讓你的程序飛起來！?
大家好，我是小康。
今天咱們聊一個看似簡單卻經常被忽視的話題：C++中的map和unordered_map到底有啥區別？
選錯了容器，你的程序可能就慢了 10 倍不止！這可不是危言聳聽，而是實打實的性能差距。
一、一個真實的"血淚"故事
前幾天我同事小王一臉沮喪地走過來："我的程序怎么這么慢啊，數據量一大就卡得不行..."
我瞄了一眼他的代碼，發現他在處理幾十萬條數據時用的是map，而不是unordered_map。簡單改了一下容器類型后，程序速度立馬提升了 8 倍多！
小王震驚了："啥？就改個容器名字，速度差這么多？"
是的，就是這么神奇！今天我就帶大家徹底搞清楚這兩個容器的區別，以后再也不踩這個坑。
二、它們到底是啥？
1. map：有序的紳士
map就像一個有序的字典，它會自動把你放進去的鍵值對按鍵排序。
#include <iostream>
#include <map>
int main() {
std::map<std::string, int> scoreMap;
scoreMap["Zhang"] = 85;
scoreMap["Li"] = 92;
scoreMap["Wang"] = 78;
// 遍歷時會按鍵的字母順序輸出
for (constauto& student : scoreMap) {
std::cout << student.first << ": " << student.second << std::endl;
}
return0;
}
// 輸出結果：
// Li: 92
// Wang: 78
// Zhang: 85
// （按照字母順序）2. unordered_map：隨性的混世魔王
unordered_map則像個不講究順序的字典，它只關心能不能快速找到東西，至于排序？不存在的！
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> scoreMap;
scoreMap["Zhang"] = 85;
scoreMap["Li"] = 92;
scoreMap["Wang"] = 78;
// 遍歷時輸出順序不確定
for (constauto& student : scoreMap) {
std::cout << student.first << ": " << student.second << std::endl;
}
return0;
}
// 可能的輸出結果：
// Wang: 78
// Zhang: 85
// Li: 92
// （順序可能每次運行都不同）三、它們內部是咋實現的？
1. map：紅黑樹（有規有矩的大家族）
map內部是用 紅黑樹 實現的。紅黑樹是一種自平衡的二叉查找樹。
想象一下，如果把map比作一個圖書館：
- 每本書（鍵值對）都有固定的位置
- 所有書按書名（鍵）字母順序排列
- 要找一本書，圖書管理員會從中間的書架開始，然后告訴你"往左邊找"或"往右邊找"
- 找書的過程就像二分查找
// map的簡化結構示意圖（紅黑樹）
D
/ \
B F
/ \ / \
A C E G在上面的圖中，每個字母代表一個鍵。查找鍵"E"的過程：
- 從根節點"D"開始
- "E"比"D"大，向右走到"F"
- "E"比"F"小，向左走到"E"
- 找到了！
2. unordered_map：哈希表（雜亂但高效的倉庫）
unordered_map內部是用哈希表實現的。
繼續用圖書館打比方：
- 這是一個特殊的圖書館，沒有明顯的排序
- 但圖書管理員有一個神奇的公式，輸入書名就能直接告訴你書在哪個架子上
- 你直接去那個架子就能找到書，不需要一步步查找
- 這個"神奇公式"就是哈希函數
// unordered_map的簡化結構示意圖（哈希表）
桶0: [C] -> [K]
桶1: [A]
桶2:
桶3: [D] -> [H]
桶4: [B]
桶5: [G]
桶6: [F] -> [J]
桶7: [E] -> [I]在上圖中，每個字母代表一個鍵。查找鍵"H"的過程：
- 計算"H"的哈希值，假設結果為 3
- 直接檢查桶 3
- 桶 3 有一個鏈表，檢查鏈表中的每個元素
- 找到"H"！
四、性能對比：差距到底有多大？
讓我們做個全面的性能對比，分別測試插入、查找、刪除和修改這四種操作：
#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>
#include <string>
#include <vector>
#include <random>
// 計時輔助函數
template<typename Func>
long long timeOperation(Func func) {
auto start = std::chrono::high_resolution_clock::now();
func();
auto end = std::chrono::high_resolution_clock::now();
returnstd::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
}
int main() {
constint COUNT = 100000;
// 準備隨機數據
std::vector<int> keys;
for (int i = 0; i < COUNT; i++) {
keys.push_back(i);
}
// 打亂順序用于隨機訪問
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(keys.begin(), keys.end(), g);
std::map<int, int> orderedMap;
std::unordered_map<int, int> unorderedMap;
// 1. 插入性能
auto mapInsertTime = timeOperation([&]() {
for (int i = 0; i < COUNT; i++) {
orderedMap[i] = i * 2;
}
});
auto unorderedMapInsertTime = timeOperation([&]() {
for (int i = 0; i < COUNT; i++) {
unorderedMap[i] = i * 2;
}
});
// 2. 查找性能（順序訪問）
auto mapLookupTime = timeOperation([&]() {
int result = 0;
for (int i = 0; i < COUNT; i++) {
result += orderedMap[i];
}
// 防止編譯器優化掉
volatileint dummy = result;
});
auto unorderedMapLookupTime = timeOperation([&]() {
int result = 0;
for (int i = 0; i < COUNT; i++) {
result += unorderedMap[i];
}
// 防止編譯器優化掉
volatileint dummy = result;
});
// 3. 查找性能（隨機訪問）
auto mapRandomLookupTime = timeOperation([&]() {
int result = 0;
for (int key : keys) {
result += orderedMap[key];
}
// 防止編譯器優化掉
volatileint dummy = result;
});
auto unorderedMapRandomLookupTime = timeOperation([&]() {
int result = 0;
for (int key : keys) {
result += unorderedMap[key];
}
// 防止編譯器優化掉
volatileint dummy = result;
});
// 4. 修改性能
auto mapUpdateTime = timeOperation([&]() {
for (int i = 0; i < COUNT; i++) {
orderedMap[i] = i * 3;
}
});
auto unorderedMapUpdateTime = timeOperation([&]() {
for (int i = 0; i < COUNT; i++) {
unorderedMap[i] = i * 3;
}
});
// 5. 刪除性能
auto mapEraseTime = timeOperation([&]() {
for (int key : keys) {
if (key % 2 == 0) { // 刪除一半的元素
orderedMap.erase(key);
}
}
});
auto unorderedMapEraseTime = timeOperation([&]() {
for (int key : keys) {
if (key % 2 == 0) { // 刪除一半的元素
unorderedMap.erase(key);
}
}
});
// 打印結果
std::cout << "操作\t\tmap(微秒)\tunordered_map(微秒)\t性能比" << std::endl;
std::cout << "插入\t\t" << mapInsertTime << "\t\t" << unorderedMapInsertTime
<< "\t\t\t" << (float)mapInsertTime / unorderedMapInsertTime << std::endl;
std::cout << "順序查找\t" << mapLookupTime << "\t\t" << unorderedMapLookupTime
<< "\t\t\t" << (float)mapLookupTime / unorderedMapLookupTime << std::endl;
std::cout << "隨機查找\t" << mapRandomLookupTime << "\t\t" << unorderedMapRandomLookupTime
<< "\t\t\t" << (float)mapRandomLookupTime / unorderedMapRandomLookupTime << std::endl;
std::cout << "修改\t\t" << mapUpdateTime << "\t\t" << unorderedMapUpdateTime
<< "\t\t\t" << (float)mapUpdateTime / unorderedMapUpdateTime << std::endl;
std::cout << "刪除\t\t" << mapEraseTime << "\t\t" << unorderedMapEraseTime
<< "\t\t\t" << (float)mapEraseTime / unorderedMapEraseTime << std::endl;
return0;
}
// 輸出結果：
// 操作 map(微秒) unordered_map(微秒) 性能比
// 插入 225419 116690 1.93178
// 順序查找 103715 20122 5.15431
// 隨機查找 127432 25890 4.92205
// 修改 104918 20597 5.09385
// 刪除 130040 29996 4.335241. 性能分析
從測試結果可以清晰地看出：
(1) 插入操作：unordered_map比map快約1.9倍。這是因為map每次插入都需要維護紅黑樹的平衡，而unordered_map只需計算哈希值并放入對應的桶。
(2) 查找操作：
- 順序查找：unordered_map比map快約5.2倍
- 隨機查找：unordered_map比map快約4.9倍
查找是unordered_map最顯著的優勢，無論是順序還是隨機訪問模式下都有明顯提升。
- 修改操作：unordered_map比map快約5.1倍。修改操作本質上是先查找再賦值，所以性能差距與查找操作接近。
- 刪除操作：unordered_map比map快約4.3倍。map刪除元素后可能需要重新平衡樹，而unordered_map只需從哈希表中刪除節點。
2. 小結
綜合來看，unordered_map在所有操作上都顯著優于map，特別是在查找和修改操作上，性能提升達到了5倍左右。這意味著在大多數不需要有序遍歷的場景下，unordered_map是更優的選擇。
記住這些差異，在實際開發中選擇合適的容器，可以為你的程序帶來顯著的性能提升。
五、什么時候用哪個？
1. 用 map 的情況
(1) 需要有序遍歷：如果你需要按鍵的順序遍歷元素
// 想按學生姓名字母順序打印成績單
std::map<std::string, int> scoreCard;
// ... 添加數據 ...
for (const auto& item : scoreCard) {
std::cout << item.first << ": " << item.second << std::endl;
}(2) 需要范圍查詢：找出所有鍵在某個范圍內的元素
// 查找所有名字在A到C之間的學生
auto start = scoreCard.lower_bound("A");
auto end = scoreCard.upper_bound("C");
for (auto it = start; it != end; ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}(3) 需要穩定的性能：最壞情況下查找復雜度是確定的O(log n)
2. 用 unordered_map 的情況
(1) 只關心查找速度：大多數情況下只是用來查找，不關心順序
// 快速查找某個學生的成績
std::unordered_map<std::string, int> scoreDB;
// ... 添加數據 ...
std::cout << "Zhang's score: " << scoreDB["Zhang"] << std::endl;(2) 數據量大：對于大數據量，unordered_map 的常數時間復雜度 O(1) 明顯優于 map 的 O(log n)
(3) 不需要排序：如果不需要按鍵排序，就沒必要付出排序的成本
六、常見坑點
坑1：自定義類型做鍵
對于unordered_map，如果用自定義類型作為鍵，必須提供哈希函數和相等比較函數：
struct Student {
std::string name;
int id;
booloperator==(const Student& other) const {
return id == other.id;
}
};
// 為Student提供哈希函數
namespacestd {
template<>
struct hash<Student> {
size_t operator()(const Student& s) const {
return hash<int>()(s.id);
}
};
}
// 現在可以使用了
std::unordered_map<Student, int> studentScores;坑2：性能波動
unordered_map在某些情況下可能會遇到哈希沖突，導致性能下降。如果你的應用對性能穩定性要求高，可能需要考慮使用map。
坑3：內存占用
unordered_map通常比map消耗更多內存，因為哈希表為了降低沖突概率，會預留一定的空間。
七、實際使用建議
- 默認選擇unordered_map：除非有特殊需求，一般情況下優先使用unordered_map
- 測試決定：對于性能關鍵的代碼，最好實際測試兩種容器的性能差異
- 根據需求選擇：如果需要有序遍歷或范圍查詢，選擇map；如果只需要快速查找，選擇unordered_map
- 考慮數據規模：數據量越大，兩者的性能差距可能越明顯
八、總結
選對容器，事半功倍；選錯容器，徒增煩惱。
- map：有序、穩定、支持范圍查詢，但速度較慢（O(log n)）
- unordered_map：無序、速度快（O(1)），但內存占用較大，且不支持范圍查詢
記住這些區別，下次寫代碼時，就能輕松選擇正確的容器，讓你的程序飛起來！
責任編輯：趙寧寧
來源：
跟著小康學編程
