STL map/multimap 接口使用与核心特性详解

增删查操作

插入

insert 返回 pair<iterator, bool>，第二个元素表示是否插入成功。若 key 已存在，即使 value 不同也不插入。

pair<iterator, bool> ret = dict.insert({"new", "val"});
if (!ret.second) {
    // key 已存在
}

查找与删除

find 返回迭代器，未找到返回 end()。count 在 map 中只能返回 0 或 1。erase 可删除指定位置、key 或区间。

auto it = dict.find("key");
if (it != dict.end()) {
    dict.erase(it);
}

边界查找

lower_bound 返回 >= k 的第一个元素，upper_bound 返回 > k 的第一个元素，equal_range 同时返回两者。

数据修改与 operator[]

map 的核心在于修改 value。通过 find 返回的迭代器可直接修改 second 成员。而 operator[] 是最强大的接口，集插入、查找、修改于一身。

// operator[] 原理：若 key 不存在则插入默认构造的 value，并返回引用
string& val = dict["key"];
val = "new value"; // 修改

场景对比：

• 传统方式：先 find，再判断是否存在，不存在则 insert，存在则修改。
• operator[] 方式：直接 dict[key]++，一行搞定统计逻辑。

实战案例

词频统计

统计水果出现次数，operator[] 写法极其简洁。

map<string, int> countMap;
string arr[] = {"苹果", "西瓜", "苹果"};
for (const auto& str : arr) {
    countMap[str]++; // 不存在插入 0 后自增，存在则自增
}

随机链表复制（LeetCode 138）

利用 map 建立原节点到拷贝节点的映射，O(logN) 时间处理 random 指针。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodeMap;
        Node* cur = head;
        while (cur) {
            nodeMap[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while (cur) {
            if (cur->random) nodeMap[cur]->random = nodeMap[cur->random];
            cur = cur->next;
        }
        return nodeMap[head];
    }
};

前 K 个高频单词（LeetCode 692）

结合 map 统计词频，再用 sort 或 priority_queue 排序。注意 stable_sort 能保持相同频率下的字典序。

multimap 差异

multimap 允许 key 重复，因此不支持 operator[]（无法确定返回哪个 value）。find 返回中序第一个匹配项，erase(key) 会删除所有匹配项。

总结

1. map 是 key/value 搜索结构，节点存储 pair<const Key, T>。
2. 插入：key 已存在时失败，与 value 无关。
3. 查找：find 返回迭代器，可通过它修改 value。
4. operator[]：灵魂接口，兼具插入、查找、修改功能。
5. multimap：支持 key 重复，无 operator[]，适合一对多映射。
6. 应用场景：词频统计、复杂链表拷贝、TopK 问题等，代码简洁高效。