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
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）

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）

692. 前 K 个高频单词

解法 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 个问题等场景中具有不可替代的优势，代码简洁高效，是降维打击的利器。