C++ std::map：键、值、查找与插入

按键查找

当你按位置索引时，vector 非常好用：第 0 个元素、第 1 个元素，依此类推。但很多时候你手里没有位置，只有一个名字，想要找到与它关联的东西：用户名和他的分数，单词和它出现的次数，国家代码和它的首都。在 vector 中逐个扫描查找匹配项是 O(n) 的，数据一多就会变慢。

std::map 解决了这个问题。它存储键值对，按键保持有序，并且能在 O(log n) 时间内按键查找值。使用它需要包含 <map>：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> 读作“从 string 键到 int 值的映射”。键是唯一的：对同一个键赋值两次，以第二次的值为准。map 的内部是一棵平衡二叉搜索树，所以所有元素始终有序，查找是对数时间而不是常数时间。

插入元素

插入条目的方式有好几种，它们之间的区别很重要。最常用的是 operator[]，如果键不存在它会创建这个键，并返回一个可以赋值的引用：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // create + assign
    inventory["apples"] += 3;     // read-modify-write, now 15

    cout << "apples: " << inventory["apples"] << "\n";
}

如果你希望插入时不覆盖已有的键，就用 insert 或 emplace。两者都返回一个 pair，它的 .second 是一个 bool，告诉你插入是否真正发生了：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada already exists
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, unchanged
}

如果你想要“最后一次写入为准”，就用 []；如果已有的键应该保持不变，就用 insert/emplace。

operator[] 的陷阱：读取时也会插入

这是 map 最常见的 bug。operator[] 不是单纯的读取：如果键不存在，它会用默认构造的值（int 为 0，string 为 ""，等等）悄悄插入这个键，并返回它的引用。所以仅仅用 [] 检查一个键，就会修改 map：

map<string, int> m;
if (m["maybe"] == 0) {   // BUG: this just created "maybe" -> 0
    // ...
}
cout << m.size();        // 1, not 0 - you inserted a key by accident

在 const map 上这也会坑到你：operator[] 甚至无法编译，因为它可能需要插入。要只读不插入，请使用 find、count/contains 或 at（键不存在时它会抛出异常，而不是插入）：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: returns an iterator, == end() if absent
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) or count (any version)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: throws std::out_of_range if missing - never inserts
    cout << "a = " << m.at("a") << "\n";
}

经验法则：如果只是想读取，就永远不要用 []。键一定存在时用 at，键可能不存在时用 find/contains。

按排序顺序遍历

由于 map 基于树实现，遍历时总是按键的升序访问，而且不需要任何额外代价。每个元素都是一个 pair<const Key, Value>，所以可以用结构化绑定清晰地拆出键和值：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // missing keys start at 0, then ++
    }

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

注意绑定中的键是 const 的：你可以在循环中用 auto& 修改值，但永远不能原地修改键（那会破坏排序顺序）。输出按字母顺序排列（blue、sea、sky），不需要任何排序步骤，这正是在需要有序遍历时，人们选择 map 而不是哈希表的原因。

wordCount[w]++ 这种写法也是“访问即插入”行为的典型用法：在这里你正希望缺失的键从 0 开始，所以 [] 是正确的工具。

删除元素与获取大小

用 erase 按键删除，它返回被删除的元素个数（对 map 来说是 0 或 1）。也可以通过 find 得到的迭代器来删除。用 size() 和 empty() 查看容器的状态：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (wasn't there)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

在循环中删除时有一个陷阱：m.erase(it) 会使迭代器 it 失效，所以之后不能再 ++it。从 C++11 开始，安全的写法是 it = m.erase(it)，它返回指向下一个元素的迭代器。如果要对整个 map 按条件一次性删除，std::erase_if(m, predicate)（C++20）更简洁。

下一步：unordered_map

std::map 提供了有序的键和可预测的 O(log n) 操作，但每次查找都要为这种有序性付出代价。当你不关心键的顺序、只想要尽可能快的查找时，unordered_map 用哈希表代替了有序树，平均访问时间为 O(1)。接下来我们会看看它是如何工作的，它的平均常数时间何时胜过 map 的对数时间，以及随之而来的哈希陷阱（自定义键类型、最坏情况下的冲突）。