STL map/multimap 深度解析：接口使用与核心特性

2.2 pair 的使用要点

接口说明：

• first：访问键值 key（const 属性，不可修改）
• second：访问映射值 value（可修改）
• make_pair()：最推荐的 pair 创建方式，自动类型推导
• {key, value}：C++11 初始化列表语法，最简洁

三、map 的构造与迭代器

3.1 构造接口

// 1. 无参默认构造
explicit map(const key_compare& comp = key_compare(),
             const allocator_type& alloc = allocator_type());

// 2. 迭代器区间构造
template<class InputIterator>
map(InputIterator first, InputIterator last,
    const key_compare& comp = key_compare(),
    const allocator_type& = allocator_type());

// 3. 拷贝构造
map(const map& x);

// 4. initializer_list 构造（最常用）
map(initializer_list<value_type> il,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

3.2 迭代器接口

// 正向迭代器（双向迭代器）
iterator begin();     // 返回指向最小 key 的迭代器
iterator end();       // 返回尾后迭代器

// 反向迭代器
reverse_iterator rbegin(); // 返回指向最大 key 的迭代器
reverse_iterator rend();   // 返回反向尾后迭代器

// const 迭代器
const_iterator cbegin() const;
const_iterator cend() const;
const_reverse_iterator crbegin() const;
const_reverse_iterator crend() const;

迭代器特性：

• 双向迭代器，支持 ++、-- 操作
• 遍历走中序，按 key 升序访问
• 通过迭代器可以 修改 value，但 不能修改 key
• 支持范围 for 循环

四、map 的增删查操作

4.1 插入操作

// 单个数据插入，返回 pair<迭代器，是否成功>
pair<iterator, bool> insert(const value_type& val);

// 列表插入，已存在的 key 不会插入
void insert(initializer_list<value_type> il);

// 迭代器区间插入
template<class InputIterator>
void insert(InputIterator first, InputIterator last);

接口说明：

• insert() 的参数必须是 pair<const Key, T> 类型
• 插入时 按 key 比较，与 value 无关
• 如果 key 已存在，插入失败（即使 value 不同）
• 返回值 pair<iterator, bool>：
  • first：指向已存在元素或新插入元素的迭代器
  • second：true 表示插入成功，false 表示 key 已存在

4.2 查找操作

// 查找 key，返回迭代器，未找到返回 end()
iterator find(const key_type& k);

// 查找 key 的个数（map 中只能是 0 或 1）
size_type count(const key_type& k) const;

接口说明：

• find()：O(logN) 效率，通过返回的迭代器可以 修改 value
• count()：返回值 0 或 1，常用于存在性判断

4.3 删除操作

// 删除迭代器位置的值
iterator erase(const_iterator position);

// 删除 key，返回删除个数（0 或 1）
size_type erase(const key_type& k);

// 删除迭代器区间
iterator erase(const_iterator first, const_iterator last);

4.4 边界查找操作

// 返回 >= k 的第一个元素的迭代器
iterator lower_bound(const key_type& k);
const_iterator lower_bound(const key_type& k) const;

// 返回 > k 的第一个元素的迭代器
iterator upper_bound(const key_type& k);
const_iterator upper_bound(const key_type& k) const;

// 返回 pair<lower_bound, upper_bound>
pair<iterator, iterator> equal_range(const key_type& k);
pair<const_iterator, const_iterator> equal_range(const key_type& k) const;

五、map 的核心特性：数据修改

5.1 通过迭代器修改 value

map 支持修改 value，不支持修改 key。通过 find() 返回的迭代器或遍历时的迭代器，可以直接修改 second 成员：

auto it = dict.find("left");
if (it != dict.end()) {
    it->second = "左边、剩余"; // 修改 value
    // it->first = "right";   // 错误！不能修改 key
}

5.2 operator[] 多功能接口

接口说明：
operator[] 是 map 最强大、最常用的接口，集 插入、查找、修改 于一身：

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

内部实现原理：

mapped_type& operator[](const key_type& k) {
    // 1. 调用 insert：如果 k 不存在，插入 {k, mapped_type()}
    // 如果 k 存在，插入失败，返回已存在节点的迭代器
    pair<iterator, bool> ret = insert({k, mapped_type()});
    
    // 2. 无论插入成功还是失败，ret.first 都指向 k 所在的节点
    iterator it = ret.first;
    
    // 3. 返回 value 的引用
    return it->second;
}

三种场景：

使用样例：

map<string, string> dict;
dict["insert"];          // 1. 插入：key 不存在，插入{"insert", ""}
dict["left"] = "左边";   // 2. 插入 + 修改：插入{"left", "左边"}
dict["left"] = "左边、剩余"; // 3. 修改：key 已存在，修改 value
std::cout << dict["left"]; // 4. 查找：key 已存在，返回 value

六、map 使用详解

6.1 构造、遍历与插入

本示例演示 map 的 构造、遍历和插入 操作。map 的遍历按 key 升序 进行，插入时需构造 pair 对象，共四种构造方式，其中 初始化列表 最简洁。已存在的 key 插入会失败。

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

int main() {
    // 1. initializer_list 构造（最常用）
    map<string, string> dict = {
        {"left", "左边"},
        {"right", "右边"},
        {"insert", "插入"},
        {"string", "字符串"}
    };

    // 2. 迭代器遍历（按 key 升序）
    auto it = dict.begin();
    while (it != dict.end()) {
        // 方式 1：解引用后访问成员
        // cout << (*it).first << ":" << (*it).second << endl;
        // 方式 2：箭头运算符（最常用）
        // 第一个 -> 是迭代器重载，返回 pair*；第二个 -> 是结构指针访问成员
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
    cout << endl;

    // 3. 插入 pair 的 4 种方式（对比学习）
    pair<string, string> kv1("first", "第一个"); // 方式 1：命名对象
    dict.insert(kv1);
    dict.insert(pair<string, string>("second", "第二个")); // 方式 2：匿名对象
    dict.insert(make_pair("sort", "排序")); // 方式 3：make_pair（推荐）
    dict.insert({"auto", "自动的"}); // 方式 4：初始化列表（最简洁）

    // 4. key 已存在，插入失败（即使 value 不同）
    dict.insert({"left", "左边，剩余"});

    // 5. 范围 for 遍历
    for (const auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;

    // 6. 查找演示
    string str;
    while (cin >> str) {
        auto ret = dict.find(str); // O(logN) 查找
        if (ret != dict.end()) {
            cout << "->" << ret->second << endl;
        } else {
            cout << "无此单词，请重新输入" << endl;
        }
    }
    return 0;
}

输出结果（部分）：

insert:插入 left:左边 right:右边 string:字符串 auto:自动的 first:第一个 insert:插入 left:左边 right:右边 second:第二个 sort:排序 string:字符串 

6.2 统计水果次数（find+iterator 版本）

本示例演示 传统方式 统计词频：使用 find() 查找元素是否存在。不存在则插入 {单词，1}，存在则通过迭代器 修改 value（ret->second++）。这种方式逻辑清晰，但代码稍显冗长。

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

int main() {
    // 利用 find 和 iterator 修改功能，统计水果出现的次数
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
    map<string, int> countMap;

    for (const auto& str : arr) {
        // 1. 查找水果在不在 map 中
        auto ret = countMap.find(str);
        if (ret == countMap.end()) {
            // 2. 不存在：第一次出现，插入{水果，1}
            countMap.insert({str, 1});
        } else {
            // 3. 存在：通过迭代器修改 value（次数 +1）
            ret->second++;
        }
    }

    // 遍历输出（按 key 升序：苹果、西瓜、香蕉）
    for (const auto& e : countMap) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    return 0;
}

输出结果：

苹果:6 西瓜:3 香蕉:2 

6.3 统计水果次数（operator[] 版本）

本示例演示 operator[] 的优雅用法。countMap[str]++ 一句代码完成了 插入 + 查找 + 修改 三个功能：

• 如果 str 不存在：插入 {str, 0}，返回 value 引用，++ 后变为 1
• 如果 str 已存在：返回 value 引用，++ 后次数 +1

这是 map 最经典的用法，代码极其简洁高效。

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

int main() {
    // 利用 [] 插入 + 修改功能，巧妙实现统计水果出现的次数
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
    map<string, int> countMap;

    for (const auto& str : arr) {
        // [] 先查找水果在不在 map 中
        // 1、不在：插入{水果，0}，返回次数的引用，++ 后变成 1
        // 2、在：返回水果对应次数的引用，++ 后次数 +1
        countMap[str]++;
    }

    for (const auto& e : countMap) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    return 0;
}

输出结果：

苹果:6 西瓜:3 香蕉:2 

6.4 operator[] 多功能演示

本示例集中演示 operator[] 的 四种使用场景：插入空值、插入 + 修改、修改、查找。理解这个例子就掌握了 map 最核心的操作技巧。

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

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

    // 1. 插入 pair 对象（传统方式）
    dict.insert(make_pair("sort", "排序"));

    // 2. [] 插入空值
    // key 不存在 -> 插入 {"insert", string()} （value 默认构造为空字符串）
    dict["insert"];

    // 3. [] 插入 + 修改
    // key 不存在 -> 插入 {"left", "左边"}
    dict["left"] = "左边";

    // 4. [] 修改
    // key 已存在 -> 修改 value 为"左边、剩余"
    dict["left"] = "左边、剩余";

    // 5. [] 查找
    // key 已存在 -> 返回 value 的引用
    cout << dict["left"] << endl; // 输出：左边、剩余

    // 验证 insert 结果
    for (const auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    return 0;
}

输出结果：

左边、剩余 insert: left:左边、剩余 sort:排序 

七、multimap 的使用

7.1 multimap 与 map 的差异

接口说明：
multimap 与 map 的接口基本一致，主要差异点：

1. 不支持 operator[]：因为 key 可重复，[] 无法确定返回哪个 value 的引用
2. find() 返回 中序遍历的第一个 匹配元素
3. count() 返回 实际重复个数
4. erase(key) 删除所有 匹配 key 的元素

7.2 multimap 使用样例

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

int main() {
    // multimap：支持 key 重复
    multimap<string, string> authors = {
        {"鲁迅", "狂人日记"},
        {"余华", "活着"},
        {"鲁迅", "朝花夕拾"},
        {"余华", "许三观卖血记"},
        {"村上春树", "挪威的森林"}
    };

    // 遍历（按 key 有序，相同 key 连续存放）
    for (const auto& e : authors) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;

    // find 返回中序第一个
    auto pos = authors.find("鲁迅");
    if (pos != authors.end()) {
        cout << "鲁迅的第一部作品：" << pos->second << endl;
    }

    // count 返回实际个数
    cout << "鲁迅作品数：" << authors.count("鲁迅") << endl;

    // erase(key) 删除所有匹配项
    authors.erase("余华");
    for (const auto& e : authors) {
        cout << e.first << ":" << e.second << endl;
    }
    return 0;
}

输出结果：

村上春树：挪威的森林 鲁迅：狂人日记 鲁迅：朝花夕拾 余华：活着 余华：许三观卖血记
鲁迅的第一部作品：狂人日记
鲁迅作品数：2
村上春树：挪威的森林 鲁迅：狂人日记 鲁迅：朝花夕拾

八、map 的应用场景

8.1 场景一：随机链表的复制（力扣 138）

接口讲解：
本示例展示 map 在 复杂链表拷贝 中的妙用。传统方法需要将拷贝节点链接在原节点后，非常繁琐。使用 map 建立 原节点→拷贝节点 的映射关系，处理 random 指针时直接通过 nodeMap[cur->random] O(logN) 获取对应拷贝节点，降维打击。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 1. 建立原节点 -> 拷贝节点的映射
        map<Node*, Node*> nodeMap;
        Node* copyhead = nullptr;
        Node* copytail = nullptr;
        Node* cur = head;

        // 2. 第一次遍历：拷贝 next 指针链，同时建立映射
        while (cur) {
            if (copytail == nullptr) {
                copyhead = copytail = new Node(cur->val);
            } else {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            // 存储映射关系
            nodeMap[cur] = copytail;
            cur = cur->next;
        }

        // 3. 第二次遍历：处理 random 指针
        cur = head;
        Node* copy = copyhead;
        while (cur) {
            if (cur->random == nullptr) {
                copy->random = nullptr;
            } else {
                // O(logN) 查找原节点 random 对应的拷贝节点
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

算法复杂度：

• 时间复杂度：O(NlogN)（N 次 map 查找）
• 空间复杂度：O(N)（存储映射关系）

8.2 场景二：前 K 个高频单词（力扣 692）

解法 1：stable_sort

接口讲解：
本示例要求按 频率降序 返回前 K 个单词，频率相同则按字典序升序。map 已按 key（单词）字典序排序，因此相同频率的单词在遍历时已经是字典序升序。使用 稳定的排序算法 stable_sort 可以保持这一相对顺序。

class Solution {
public:
    struct Compare {
        // 按频率降序
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
            return x.second > y.second;
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        // 1. map 统计词频（自动按单词字典序排序）
        map<string, int> countMap;
        for (auto& e : words) {
            countMap[e]++;
        }

        // 2. 将 map 数据拷贝到 vector 中
        vector<pair<string, int>> v(countMap.begin(), countMap.end());

        // 3. 稳定排序：频率降序，相同频率保持字典序（因为 map 已排序）
        stable_sort(v.begin(), v.end(), Compare());

        // 4. 取前 k 个
        vector<string> strV;
        for (int i = 0; i < k; ++i) {
            strV.push_back(v[i].first);
        }
        return strV;
    }
};

解法 2：sort 统一排序

接口讲解：
本解法将 频率降序 和 字典序升序 两个规则合并到一个仿函数中，直接用 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& e : words) {
            countMap[e]++;
        }
        vector<pair<string, int>> v(countMap.begin(), countMap.end());

        // 仿函数控制排序规则
        sort(v.begin(), v.end(), Compare());

        vector<string> strV;
        for (int i = 0; i < k; ++i) {
            strV.push_back(v[i].first);
        }
        return strV;
    }
};

解法 3：priority_queue

接口讲解：
本解法使用 优先级队列（堆）来选出前 K 个高频单词。需要注意的是，priority_queue 的 仿函数与 sort 相反：sort 的 Compare 返回 true 表示前者应在前；priority_queue 的 Compare 返回 true 表示 前者优先级低（即大堆需要 < 比较）。

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& e : words) {
            countMap[e]++;
        }

        // 将 map 中的<单词，次数>放到 priority_queue 中
        // 仿函数控制大堆：频率高的在堆顶，频率相同时字典序小的在堆顶
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(countMap.begin(), countMap.end());

        vector<string> strV;
        for (int i = 0; i < k; ++i) {
            strV.push_back(p.top().first);
            p.pop();
        }
        return strV;
    }
};

九、总结

核心要点：

1. map 是 key/value 搜索结构，节点存储 pair<const Key, T>
2. 插入：参数必须是 pair 对象，key 已存在时插入失败（与 value 无关）
3. 查找：find() 返回迭代器，可通过迭代器修改 value
4. operator[]：map 的灵魂接口，集 插入、查找、修改 于一身
   • key 不存在：插入 {key, value 默认构造}，返回 value 引用
   • key 已存在：返回 value 引用
5. multimap：支持 key 重复，不支持 operator[]，find() 返回中序第一个，erase(key) 删除所有匹配项
6. 应用价值：map 在处理 键值映射、词频统计、复杂链表拷贝、前 K 个问题 等场景中具有不可替代的优势，代码简洁高效，是 降维打击 的利器。