C++ map 与 multimap 使用指南：原理、API 及算法实战

注意： map 的 key 具有唯一性。如果插入已存在的 key，操作不会生效，且返回的 second 为 false。

2. 遍历方式

迭代器遍历

for (auto it = dict.begin(); it != dict.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

范围 for (C++11)

for (const auto& e : dict) {
    std::cout << e.first << ": " << e.second << std::endl;
}

结构化绑定 (C++17)

for (const auto& [k, v] : dict) {
    std::cout << k << ": " << v << std::endl;
}

3. 查找与修改

find

返回迭代器，若未找到则返回 end()。

auto it = dict.find("apple");
if (it != dict.end()) {
    it->second++; // 可以通过迭代器修改 value
}

operator[] vs at()

这是 map 使用中容易混淆的两个接口。

operator[] 的实现逻辑：

1. 若 key 不存在，先插入一个默认构造的 value。
2. 返回该 value 的引用。

// 如果 "sort" 不存在，会自动插入空字符串
std::cout << dict["sort"] << std::endl;

// 安全访问，不存在会报错
try {
    dict.at("unknown_key");
} catch (const std::out_of_range& e) {
    // 处理异常
}

4. 删除操作

// 通过迭代器删除
auto pos = dict.find("left");
if (pos != dict.end()) {
    dict.erase(pos);
}

// 通过 key 删除
dict.erase("left");

Multimap 的差异

multimap 与 map 的使用基本类似，主要区别在于 multimap 允许 key 重复。因此，multimap 不支持 operator[]，因为无法确定应该返回哪个重复 key 对应的 value。查找时，find 返回中序遍历的第一个匹配项。

算法实战

1. 随机链表的复制

在 LeetCode 138 题中，利用 map 建立原节点与新节点的映射关系，可以简化 random 指针的处理。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        std::map<Node*, Node*> nodeMap;
        Node* copyhead = nullptr, *copytail = nullptr;
        Node* cur = head;

        // 第一步：复制所有节点并建立映射
        while (cur) {
            Node* copy = new Node(cur->val);
            if (!copytail) {
                copyhead = copytail = copy;
            } else {
                copytail->next = copy;
                copytail = copy;
            }
            nodeMap[cur] = copy;
            cur = cur->next;
        }

        // 第二步：设置 random 指针
        cur = head;
        Node* copy = copyhead;
        while (cur) {
            if (cur->random) {
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

2. 前 K 个高频单词

统计词频后，需要按频率降序排列，频率相同则按字典序升序。

class Solution {
public:
    struct kv_pair {
        bool operator()(const std::pair<std::string, int>& kv1,
                        const std::pair<std::string, int>& kv2) {
            // 频率高的在前，频率相同字典序小的在前
            if (kv1.second == kv2.second) {
                return kv1.first < kv2.first;
            }
            return kv1.second > kv2.second;
        }
    };

    std::vector<std::string> topKFrequent(std::vector<std::string>& words, int k) {
        std::map<std::string, int> countMap;
        for (auto& str : words) {
            countMap[str]++;
        }

        std::vector<std::pair<std::string, int>> v(countMap.begin(), countMap.end());
        std::stable_sort(v.begin(), v.end(), kv_pair());

        std::vector<std::string> ret;
        for (size_t i = 0; i < k; ++i) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

完整示例代码

以下是一个整合了常见操作的测试示例。

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

void Test_map() {
    map<string, string> dict;
    
    // 插入
    dict.insert(make_pair("sort", "排序"));
    dict.insert({"left", "左边"});
    
    // 遍历 (C++17 结构化绑定)
    for (const auto& [k, v] : dict) {
        cout << k << ": " << v << endl;
    }
    
    // 查找与修改
    auto pos = dict.find("left");
    if (pos != dict.end()) {
        pos->second = "新左边";
    }
    
    // operator[] 与 at() 对比
    cout << dict["right"] << endl; // 不存在则插入空字符串
    try {
        cout << dict.at("insert") << endl; // 不存在则抛异常
    } catch (...) {
        cout << "at() 访问失败" << endl;
    }
}

int main() {
    Test_map();
    return 0;
}

总结

掌握 map 的关键在于理解其底层有序性及 key 的唯一性。在实际开发中，operator[] 适合用于计数或允许自动初始化的场景，而 at() 更适合需要严格校验 key 存在的逻辑。结合 multimap 处理多值映射，配合算法题中的哈希思想，能显著提升解决复杂问题的效率。