C++中的map vs unordered_map：选错容器让你的程序慢10倍！
<p>大家好！今天咱们聊一个看似简单却经常被忽视的话题：<strong>C++中的map和unordered_map到底有啥区别</strong>？</p><p>选错了容器，你的程序可能就慢了 10 倍不止！这可不是危言耸听，而是实打实的性能差距。</p>
<h2 id="一一个真实的血泪故事">一、一个真实的"血泪"故事</h2>
<p>前几天我同事小王一脸沮丧地走过来："我的程序怎么这么慢啊，数据量一大就卡得不行..."</p>
<p>我瞄了一眼他的代码，发现他在处理几十万条数据时用的是<code>map</code>，而不是<code>unordered_map</code>。简单改了一下容器类型后，程序速度立马提升了 8 倍多！</p>
<p>小王震惊了："啥？就改个容器名字，速度差这么多？"</p>
<p>是的，就是这么神奇！今天我就带大家彻底搞清楚这两个容器的区别，以后再也不踩这个坑。</p>
<blockquote>
<p>微信搜索 「<strong>跟着小康学编程</strong>」，关注我，后续还有更多硬核技术文章分享，带你玩转 Linux C/C++ 编程！😆</p>
</blockquote>
<h2 id="二它们到底是啥">二、它们到底是啥？</h2>
<h3 id="map有序的绅士">map：有序的绅士</h3>
<p><code>map</code>就像一个有序的字典，它会<strong>自动把你放进去的键值对按键排序</strong>。</p>
<pre><code class="language-cpp">#include <iostream>
#include <map>
int main() {
std::map<std::string, int> scoreMap;
scoreMap["Zhang"] = 85;
scoreMap["Li"] = 92;
scoreMap["Wang"] = 78;
// 遍历时会按键的字母顺序输出
for (const auto& student : scoreMap) {
std::cout << student.first << ": " << student.second << std::endl;
}
return 0;
}
// 输出结果：
// Li: 92
// Wang: 78
// Zhang: 85
// （按照字母顺序）
</code></pre>
<h3 id="unordered_map随性的混世魔王">unordered_map：随性的混世魔王</h3>
<p><code>unordered_map</code>则像个不讲究顺序的字典，它只关心能不能快速找到东西，至于排序？不存在的！</p>
<pre><code class="language-cpp">#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> scoreMap;
scoreMap["Zhang"] = 85;
scoreMap["Li"] = 92;
scoreMap["Wang"] = 78;
// 遍历时输出顺序不确定
for (const auto& student : scoreMap) {
std::cout << student.first << ": " << student.second << std::endl;
}
return 0;
}
// 可能的输出结果：
// Wang: 78
// Zhang: 85
// Li: 92
// （顺序可能每次运行都不同）
</code></pre>
<h2 id="三它们内部是咋实现的">三、它们内部是咋实现的？</h2>
<h3 id="map红黑树有规有矩的大家族">map：红黑树（有规有矩的大家族）</h3>
<p><code>map</code>内部是用 <strong>红黑树</strong> 实现的。红黑树是一种自平衡的二叉查找树。</p>
<p>想象一下，如果把<code>map</code>比作一个图书馆：</p>
<ul>
<li>每本书（键值对）都有固定的位置</li>
<li>所有书按书名（键）字母顺序排列</li>
<li>要找一本书，图书管理员会从中间的书架开始，然后告诉你"往左边找"或"往右边找"</li>
<li>找书的过程就像二分查找</li>
</ul>
<pre><code class="language-plain">// map的简化结构示意图（红黑树）
D
/ \
B F
/ \ / \
A C E G
</code></pre>
<p>在上面的图中，每个字母代表一个键。查找键"E"的过程：</p>
<ol>
<li>从根节点"D"开始</li>
<li>"E"比"D"大，向右走到"F"</li>
<li>"E"比"F"小，向左走到"E"</li>
<li>找到了！</li>
</ol>
<h3 id="unordered_map哈希表杂乱但高效的仓库">unordered_map：哈希表（杂乱但高效的仓库）</h3>
<p><code>unordered_map</code>内部是用<strong>哈希表</strong>实现的。</p>
<p>继续用图书馆打比方：</p>
<ul>
<li>这是一个特殊的图书馆，没有明显的排序</li>
<li>但图书管理员有一个神奇的公式，输入书名就能直接告诉你书在哪个架子上</li>
<li>你直接去那个架子就能找到书，不需要一步步查找</li>
<li>这个"神奇公式"就是哈希函数</li>
</ul>
<pre><code class="language-plain">// unordered_map的简化结构示意图（哈希表）
桶0: ->
桶1:
桶2:
桶3: ->
桶4:
桶5:
桶6: ->
桶7: ->
</code></pre>
<p>在上图中，每个字母代表一个键。查找键"H"的过程：</p>
<ol>
<li>计算"H"的哈希值，假设结果为 3</li>
<li>直接检查桶 3</li>
<li>桶 3 有一个链表，检查链表中的每个元素</li>
<li>找到"H"！</li>
</ol>
<h2 id="四性能对比差距到底有多大">四、性能对比：差距到底有多大？</h2>
<p>让我们做个全面的性能对比，分别测试插入、查找、删除和修改这四种操作：</p>
<pre><code class="language-cpp">#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();
return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
}
int main() {
const int 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 * 2;
}
});
auto unorderedMapInsertTime = timeOperation([&]() {
for (int i = 0; i < COUNT; i++) {
unorderedMap = i * 2;
}
});
// 2. 查找性能（顺序访问）
auto mapLookupTime = timeOperation([&]() {
int result = 0;
for (int i = 0; i < COUNT; i++) {
result += orderedMap;
}
// 防止编译器优化掉
volatile int dummy = result;
});
auto unorderedMapLookupTime = timeOperation([&]() {
int result = 0;
for (int i = 0; i < COUNT; i++) {
result += unorderedMap;
}
// 防止编译器优化掉
volatile int dummy = result;
});
// 3. 查找性能（随机访问）
auto mapRandomLookupTime = timeOperation([&]() {
int result = 0;
for (int key : keys) {
result += orderedMap;
}
// 防止编译器优化掉
volatile int dummy = result;
});
auto unorderedMapRandomLookupTime = timeOperation([&]() {
int result = 0;
for (int key : keys) {
result += unorderedMap;
}
// 防止编译器优化掉
volatile int dummy = result;
});
// 4. 修改性能
auto mapUpdateTime = timeOperation([&]() {
for (int i = 0; i < COUNT; i++) {
orderedMap = i * 3;
}
});
auto unorderedMapUpdateTime = timeOperation([&]() {
for (int i = 0; i < COUNT; i++) {
unorderedMap = 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;
return 0;
}
// 输出结果：
// 操作 map(微秒) unordered_map(微秒) 性能比
// 插入 225419 116690 1.93178
// 顺序查找 103715 20122 5.15431
// 随机查找 127432 25890 4.92205
// 修改 104918 20597 5.09385
// 删除 130040 29996 4.33524
</code></pre>
<h3 id="性能分析">性能分析：</h3>
<p>从测试结果可以清晰地看出：</p>
<ol>
<li><strong>插入操作</strong>：<code>unordered_map</code>比<code>map</code>快约1.9倍。这是因为<code>map</code>每次插入都需要维护红黑树的平衡，而<code>unordered_map</code>只需计算哈希值并放入对应的桶。</li>
<li><strong>查找操作</strong>：
<ul>
<li>顺序查找：<code>unordered_map</code>比<code>map</code>快约5.2倍</li>
<li>随机查找：<code>unordered_map</code>比<code>map</code>快约4.9倍</li>
</ul>
</li>
</ol>
<p>查找是<code>unordered_map</code>最显著的优势，无论是顺序还是随机访问模式下都有明显提升。</p>
<ol start="3">
<li><strong>修改操作</strong>：<code>unordered_map</code>比<code>map</code>快约5.1倍。修改操作本质上是先查找再赋值，所以性能差距与查找操作接近。</li>
<li><strong>删除操作</strong>：<code>unordered_map</code>比<code>map</code>快约4.3倍。<code>map</code>删除元素后可能需要重新平衡树，而<code>unordered_map</code>只需从哈希表中删除节点。</li>
</ol>
<h3 id="小结">小结：</h3>
<p>综合来看，<code>unordered_map</code>在所有操作上都显著优于<code>map</code>，特别是在查找和修改操作上，性能提升达到了5倍左右。这意味着在大多数不需要有序遍历的场景下，<code>unordered_map</code>是更优的选择。</p>
<p>记住这些差异，在实际开发中选择合适的容器，可以为你的程序带来显著的性能提升。</p>
<h2 id="五什么时候用哪个">五、什么时候用哪个？</h2>
<h3 id="用-map-的情况">用 map 的情况</h3>
<p>1、 <strong>需要有序遍历</strong>：如果你需要按键的顺序遍历元素</p>
<pre><code class="language-cpp">// 想按学生姓名字母顺序打印成绩单
std::map<std::string, int> scoreCard;
// ... 添加数据 ...
for (const auto& item : scoreCard) {
std::cout << item.first << ": " << item.second << std::endl;
}
</code></pre>
<p>2、 <strong>需要范围查询</strong>：找出所有键在某个范围内的元素</p>
<pre><code class="language-cpp">// 查找所有名字在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;
}
</code></pre>
<p>3、 <strong>需要稳定的性能</strong>：最坏情况下查找复杂度是确定的O(log n)</p>
<h3 id="用-unordered_map-的情况">用 unordered_map 的情况</h3>
<p>1、 <strong>只关心查找速度</strong>：大多数情况下只是用来查找，不关心顺序</p>
<pre><code class="language-cpp">// 快速查找某个学生的成绩
std::unordered_map<std::string, int> scoreDB;
// ... 添加数据 ...
std::cout << "Zhang's score: " << scoreDB["Zhang"] << std::endl;
</code></pre>
<p>2、 <strong>数据量大</strong>：对于大数据量，unordered_map 的常数时间复杂度 O(1) 明显优于 map 的 O(log n)</p>
<p>3、 <strong>不需要排序</strong>：如果不需要按键排序，就没必要付出排序的成本</p>
<h2 id="六常见坑点">六、常见坑点</h2>
<h3 id="坑1自定义类型做键">坑1：自定义类型做键</h3>
<p>对于<code>unordered_map</code>，如果用自定义类型作为键，必须提供哈希函数和相等比较函数：</p>
<pre><code class="language-cpp">struct Student {
std::string name;
int id;
bool operator==(const Student& other) const {
return id == other.id;
}
};
// 为Student提供哈希函数
namespace std {
template<>
struct hash<Student> {
size_t operator()(const Student& s) const {
return hash<int>()(s.id);
}
};
}
// 现在可以使用了
std::unordered_map<Student, int> studentScores;
</code></pre>
<h3 id="坑2性能波动">坑2：性能波动</h3>
<p><code>unordered_map</code>在某些情况下可能会遇到哈希冲突，导致性能下降。如果你的应用对性能稳定性要求高，可能需要考虑使用<code>map</code>。</p>
<h3 id="坑3内存占用">坑3：内存占用</h3>
<p><code>unordered_map</code>通常比<code>map</code>消耗更多内存，因为哈希表为了降低冲突概率，会预留一定的空间。</p>
<h2 id="七实际使用建议">七、实际使用建议</h2>
<ol>
<li><strong>默认选择unordered_map</strong>：除非有特殊需求，一般情况下优先使用<code>unordered_map</code></li>
<li><strong>测试决定</strong>：对于性能关键的代码，最好实际测试两种容器的性能差异</li>
<li><strong>根据需求选择</strong>：如果需要有序遍历或范围查询，选择<code>map</code>；如果只需要快速查找，选择<code>unordered_map</code></li>
<li><strong>考虑数据规模</strong>：数据量越大，两者的性能差距可能越明显</li>
</ol>
<h2 id="总结">总结</h2>
<p>选对容器，事半功倍；选错容器，徒增烦恼。</p>
<ul>
<li><strong>map</strong>：有序、稳定、支持范围查询，但速度较慢（O(log n)）</li>
<li><strong>unordered_map</strong>：无序、速度快（O(1)），但内存占用较大，且不支持范围查询</li>
</ul>
<p>记住这些区别，下次写代码时，就能轻松选择正确的容器，让你的程序飞起来！</p>
<p>你遇到过因为选错容器导致的性能问题吗？欢迎在评论区分享你的"血泪"经历~</p>
<hr>
<h2 id="-拨开性能迷雾探索-c-之美">🔍 拨开性能迷雾，探索 C++ 之美</h2>
<p>如果你也对性能优化着迷，或想让你的代码更加高效，不妨关注我的公众号「<strong>跟着小康学编程</strong>」。</p>
<p>在这里，我用简单的比喻解释复杂概念，用有趣的案例展示技术原理。无论是 STL 容器选择，还是内存优化策略，都能找到通俗易懂的解答。</p>
<p><strong>每周更新，不见不散！</strong> 👋</p>
<p>如果你觉得这篇文章对你有帮助，别忘了<strong>点赞、收藏、关注</strong>哦~ 你的支持是我持续创作的动力！</p>
<h4 id="怎么关注我的公众号">怎么关注我的公众号？</h4>
<p><strong>点击下方公众号名片即可关注</strong>。</p>
<p><img src="https://files.mdnice.com/user/71186/0dde803d-d52f-4ed8-b74b-b7f3da5817b9.png"></p>
<p>哦对了，我还建了个技术交流群，大家一起聊技术、解答问题。卡壳了？不懂的地方？随时在群里提问！不只是我，群里还有一堆技术大佬随时准备帮你解惑。一起学，才有动力嘛！</p>
<p><img src="https://files.mdnice.com/user/48364/971ccaa3-8f57-4e33-8bc9-d0863eeade81.png"></p><br><br>
来源：https://www.cnblogs.com/xiaokang-coding/p/18849267
頁:
[1]