STL map 与 multimap 深度解析：接口、特性与实战应用

STL map 和 multimap 是关联式容器中的核心成员，底层基于红黑树实现。与 set 不同，它们存储的是键值对（pair），支持通过 key 快速映射到 value。

map 类基础

map 的模板声明如下：

template <class Key,      // map::key_type
class T,                  // map::mapped_type
class Compare = less<Key>,// map::key_compare
class Alloc = allocator<pair<const Key,T>>> // map::allocator_type
class map;

关键参数：

• Key：键类型，必须唯一。
• T：映射值的类型。
• Compare：比较仿函数，默认按 key 升序排列。
• Alloc：空间配置器。

底层特性：

• 结构：平衡二叉搜索树（红黑树）。
• 复杂度：增删查改均为 O(logN)。
• 遍历：中序遍历，key 有序。
• 限制：支持修改 value，严禁修改 key（会破坏树结构）。

pair 类型详解

map 节点实际存储的是 pair<const Key, T>。pair 将两个数据组合成一个单元：

template<class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;   // key
    T2 second;  // value
    
    pair() : first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b) : first(a), second(b) {}
};

使用要点：

• first 访问 key（const，不可改）。
• second 访问 value（可改）。
• 推荐用 make_pair() 或 {key, value} 初始化列表创建对象。

构造与迭代器

构造方式

1. 无参默认构造。
2. 迭代器区间构造。
3. 拷贝构造。
4. 初始化列表构造（最常用）。

map<string, string> dict = {{"left", "左边"}, {"right", "右边"}};

迭代器操作

• begin()/end()：正向遍历，指向最小 key。
• rbegin()/rend()：反向遍历，指向最大 key。
• 双向迭代器，支持 ++/--。
• 遍历时可直接修改 it->second，但不可动 it->first。

增删查操作

插入

insert() 返回 pair<iterator, bool>，指示是否插入成功。若 key 已存在，即使 value 不同也会失败。

auto ret = dict.insert({"new_key", "value"});
if (ret.second) {
    // 插入成功
}

查找

• find(k)：返回迭代器，未找到返回 end()。
• count(k)：map 中返回 0 或 1。

删除

• erase(pos)：删除迭代器位置元素。
• erase(k)：删除指定 key 的元素，返回删除个数。
• erase(first, last)：删除区间元素。

边界查找

• lower_bound(k)：返回 >= k 的第一个元素。
• upper_bound(k)：返回 > k 的第一个元素。
• equal_range(k)：返回 [lower_bound, upper_bound) 范围。

核心特性：数据修改

迭代器修改 value

通过 find 获取迭代器后，直接修改 second 成员：

auto it = dict.find("left");
if (it != dict.end()) {
    it->second = "新内容"; // 合法
    // it->first = "right"; // 非法，编译错误
}

operator[] 的多功能用法

operator[] 是 map 的灵魂接口，集插入、查找、修改于一身。

mapped_type& operator[](const key_type& k);

原理： 内部调用 insert，若 key 不存在则插入默认构造的 value，然后返回 value 引用。

场景：

1. 插入：key 不存在时，自动插入 {key, default_value}。
2. 修改：key 存在时，直接赋值修改 value。
3. 查找：返回 value 引用。

map<string, int> countMap;
countMap["apple"]++; // 不存在则插入 0 再自增，存在则自增

实战案例

词频统计

利用 operator[] 的简洁性统计单词出现次数：

string arr[] = {"苹果", "西瓜", "苹果", "香蕉"};
map<string, int> counts;
for (const auto& s : arr) {
    counts[s]++; // 一行搞定查找 + 插入 + 修改
}

复杂链表复制（LeetCode 138）

建立原节点到拷贝节点的映射，解决 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];
    }
};

Top K 高频单词（LeetCode 692）

结合 map 排序特性与 priority_queue 或 sort 解决：

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string,int>& x, const pair<string,int>& y) const {
            return x.second < y.second || (x.second == y.second && x.first > y.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for (auto& w : words) countMap[w]++;
        priority_queue<pair<string,int>, vector<pair<string,int>>, Compare> pq(countMap.begin(), countMap.end());
        vector<string> res;
        while (k-- && !pq.empty()) {
            res.push_back(pq.top().first);
            pq.pop();
        }
        return res;
    }
};

multimap 的使用

multimap 允许 key 重复，其他接口与 map 基本一致。

特性	map	multimap
键值冗余	❌ 不支持	✅ 支持
insert	key 存在失败	总是成功
find	返回任意	返回第一个
erase(key)	删除 0/1 个	删除所有匹配
operator[]	✅ 支持	❌ 不支持

注意： multimap 不支持 operator[]，因为无法确定返回哪个重复 key 对应的 value 引用。

总结

1. map 基于红黑树，key 唯一且有序，O(logN) 效率。
2. 修改限制：只能改 value，不能改 key。
3. operator[] 是最常用的接口，兼具插入与查找功能。
4. multimap 支持重复 key，但不支持 operator[]。
5. 应用场景：词频统计、复杂指针映射、Top K 问题等。

掌握这些特性，能让你在处理键值映射问题时游刃有余。