C++ STL map 核心解析：从底层原理到 LeetCode 实战

map 支持多种构造方式，包括默认构造、迭代器区间构造、初始化列表构造等，实际开发中初始化列表构造最常用：

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

void test_map1() {
    // 1. 默认构造（空 map）
    map<string, string> dict1;
    
    // 2. 初始化列表构造（C++11，比较推荐）
    map<string, string> dict2 = {
        {"sort", "排序"},
        {"left", "左边"},
        {"right", "右边"}
    };
    
    // 3. 迭代器区间构造（从其他 map 或容器拷贝）
    map<string, string> dict3(dict2.begin(), dict2.end());
    
    // 4. 拷贝构造
    map<string, string> dict4(dict3);
    
    cout << "dict2 初始化结果：" << endl;
    for (const auto& [k, v] : dict2) { // C++17 结构化绑定（简洁遍历）
        cout << k << ":" << v << endl;
    }
}

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

注意：遍历结果按 Key 升序排列（left < right < sort，按 ASCII 码比较），体现 map 自动排序特性。

2.2 迭代器遍历

map 的迭代器是双向迭代器，支持 ++/-- 操作，遍历方式包括'迭代器循环''范围 for''结构化绑定'，其中结构化绑定（C++17+）最简洁：

void test_map2() {
    map<string, string> dict = {
        {"sort", "排序"},
        {"left", "左边"},
        {"right", "右边"},
        {"string", "字符串"},
        {"map", "地图，映射"}
    };

    // 方式 1：普通迭代器遍历（支持修改 Value）
    map<string, string>::iterator it = dict.begin();
    while (it != dict.end()) {
        // 关键：迭代器解引用得到 pair<const Key, T>，需通过 -> 访问 first/second
        // (*it).first 等价于 it->first（推荐后者，更简洁）
        cout << it->first << ":" << it->second << endl;
        
        // 尝试修改 Key（编译报错！Key 是 const 的）
        // it->first = "new_left"; 
        
        // 修改 Value（合法）
        if (it->first == "left") {
            it->second = "左边（修改后）";
        }
        ++it;
    }
    cout << endl;

    // 方式 2：范围 for 遍历（传引用避免拷贝，const 保护不被修改）
    for (const auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;

    // 方式 3：C++17 结构化绑定（最简洁，直接拆分 Key 和 Value）
    for (const auto& [k, v] : dict) {
        cout << k << ":" << v << endl;
    }
}

核心细节：map 的 iterator 和 const_iterator 都不能修改 Key，但 iterator 可以修改 Value；若只需读取，优先用 const auto& 传引用，避免拷贝开销。

2.3 插入操作（insert）

map 的 insert 接口用于插入键值对，返回 pair<iterator, bool>，其中：

• iterator：指向插入成功的新节点，或已存在的相同 Key 节点；
• bool：true 表示插入成功，false 表示 Key 已存在、插入失败。

insert 支持多种插入形式，实际开发中推荐'初始化列表'和'make_pair'，以及多参数隐式类型转换：

void test_map3() {
    map<string, string> dict;
    
    // 方式 1：插入 pair 对象（C++98 风格，较繁琐)
    pair<string, string> kv1("sort", "排序");
    dict.insert(kv1);
    
    // 方式 2：插入匿名 pair 对象（略简洁）
    dict.insert(pair<string, string>("left", "左边"));
    
    // 方式 3：用 make_pair 生成 pair（推荐，无需显式写类型）
    dict.insert(make_pair("right", "右边"));
    
    // 方法 4：初始化列表插入（C++11+，最简洁),用多参数的隐式类型转换
    dict.insert({"move", "移动"});
    
    // 批量插入多个键值对
    dict.insert({{"map", "映射"},{"erase", "删除"}});
    
    // 插入重复 Key（返回 false，不修改原数据）
    auto ret = dict.insert({"left", "左边（重复插入）"});
    if (!ret.second) {
        cout << "Key 'left' 已存在，当前值：" << ret.first->second << endl;
    }
    
    // 输出结果
    for (const auto& [k, v] : dict) {
        cout << k << ":" << v << endl;
    }
}

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

2.4 查找与删除（find/erase）

（1）查找：find 与 count

• find(Key)：查找指定 Key，返回指向该 Key 的迭代器；若不存在，返回 end()（O(log N) 效率）；
• count(Key)：返回 Key 的出现次数（map 中 Key 唯一，故返回 0 或 1，可间接用于查找）。

（2）删除：erase

erase 支持三种删除形式：删除指定迭代器、删除指定 Key、删除迭代器区间，其中'删除迭代器'需先通过 find 确认 Key 存在，避免删除 end() 崩溃：

void test_map4() {
    map<string, string> dict = {
        {"sort", "排序"},
        {"left", "左边"},
        {"right", "右边"}
    };
    
    // 1. 查找 Key 'left'
    auto pos = dict.find("left");
    if (pos != dict.end()) {
        cout << "找到 Key 'left'，值：" << pos->second << endl;
        
        // 2. 删除迭代器指向的节点（安全删除）
        dict.erase(pos);
        cout << "删除 Key 'left' 后：" << endl;
        for (const auto& [k, v] : dict) {
            cout << k << ":" << v << endl;
        }
    }
    
    // 3. 直接删除指定 Key（返回删除的个数，map 中 0 或 1）
    size_t del_cnt = dict.erase("right");
    cout << "删除 Key 'right'，影响个数：" << del_cnt << endl;
    
    // 4. 删除迭代器区间（删除所有元素）
    dict.erase(dict.begin(), dict.end());
    cout << "删除所有元素后，map 大小：" << dict.size() << endl;
}

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

2.5 核心特性：operator[] 的多功能性

map 的 operator[] 是最灵活的接口，兼具'插入、查找、修改'三种功能，其内部实现依赖 insert，逻辑如下：

// operator[] 内部伪代码
mapped_type& operator[](const key_type& k) {
    // 插入 {k, mapped_type()}（默认构造的 Value，如 int 为 0，string 为空）
    pair<iterator, bool> ret = insert({k, mapped_type()});
    // 返回 Value 的引用（无论插入成功与否，都指向 Key 对应的 Value）
    return ret.first->second;
}

基于此实现，operator[] 可灵活应对不同场景：

void test_map5() {
    map<string, int> countMap;
    // 统计水果出现次数
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "香蕉"};
    
    // 场景 1：插入 + 修改（统计次数，最常用）
    for (const auto& fruit : arr) {
        // 若 fruit 不存在：插入 {fruit, 0}，返回 0 的引用，++ 后变为 1；
        // 若 fruit 已存在：返回现有 Value 的引用，++ 后次数增加；
        countMap[fruit]++;
    }
    cout << "水果统计结果：" << endl;
    for (const auto& [fruit, cnt] : countMap) {
        cout << fruit << ":" << cnt << endl;
    }
    cout << endl;
    
    // 场景 2：纯粹插入（Key 不存在时，插入默认 Value）
    map<string, string> dict;
    dict["insert"]; // 插入 { "insert", "" }（string 默认空）
    cout << "插入 'insert' 后，值：" << dict["insert"] << endl;
    
    // 场景 3：插入 + 修改（Key 不存在时插入，存在时修改）
    dict["left"] = "左边";           // 插入 { "left", "左边" }
    dict["left"] = "左边（修改后）"; // 修改 Value 为 "左边（修改后）"
    cout << "修改 'left' 后，值：" << dict["left"] << endl;
    
    // 场景 4：纯粹查找（Key 存在时，返回 Value 引用）
    cout << "查找 'left'，值：" << dict["left"] << endl;
    
    // 对比：at() 接口（仅支持查找 + 修改，Key 不存在时抛异常，不插入）
    dict.at("left") = "左边（at 修改）"; // 合法，修改 Value
    // dict.at("nonexist") = "不存在"; // 抛出异常：out_of_range
}

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

关键区别：operator[] 在 Key 不存在时会插入默认值，而 at() 会抛异常；若需'严格查找'（不存在时不插入），优先用 find；若需'统计次数''快速赋值'，优先用 operator[]。

三. map 与 multimap 的差异

multimap 是 map 的'兄弟容器'，底层同样基于红黑树，但核心差异是支持 Key 冗余（相同 Key 可重复插入），由此导致接口和使用场景不同：

实际使用示例：

void test_multimap() {
    // multimap 没有 []
    multimap<string, string> dict;
    dict.insert({"right", "右边"});
    dict.insert({"left", "左边"});
    dict.insert({"right", "右边 xx"});
    dict.insert({"right", "右边"});
    
    for (const auto& [k, v] : dict) {
        cout << k << ":" << v << endl;
    }
    cout << endl;
}

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

四. map 实战：LeetCode 经典案例

map 的核心价值在于'高效键值映射'和'自动排序'，在算法题中可简化复杂逻辑，以下是两个典型案例：

4.1 随机链表的复制

题目链接：138. 随机链表的复制 - 力扣（LeetCode）

数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。这里我们直接让{原结点，拷贝结点}建立映射关系放到 map 中，控制随机指针会非常简单方便，这里体现了 map 在解决一些问题时的价值，完全是降维打击。

C++ 算法代码：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> NodeMap;
        Node* copyhead = nullptr, *copytail = nullptr;
        Node* cur = head;
        
        while (cur) {
            if (copyhead == nullptr) {
                copyhead = copytail = new Node(cur->val);
            } else {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            // 原节点和拷贝节点通过 map，kv 存储
            NodeMap.insert({cur, copytail});
            cur = cur->next;
        }
        
        // 处理 random
        cur = head;
        Node* copy = copyhead;
        while (cur) {
            if (cur->random == nullptr)
                copy->random = nullptr;
            else
                // 查找
                copy->random = NodeMap[cur->random];
            
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

4.2 前 k 个高频单词

题目链接：692. 前 K 个高频单词 - 力扣（力扣）

本题目我们利用 map 统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。

解决思路 1： 用排序找前 k 个单词，因为 map 中已经对 key 单词排序过，也就意味着遍历 map 时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到 vector 中用一个稳定的排序就可以实现上面特殊要求，但是 sort 底层是快排，是不稳定的，所以我们要用 stable_sort，他是稳定的。

class Solution {
public:
    struct kv_pair {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
            return x.second > y.second;
        }
    };
    
    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(), kv_pair()); // 得稳定排序
        stable_sort(v.begin(), v.end(), kv_pair());
        
        vector<string> ret;
        for (size_t i = 0; i < k; i++) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

解决思路 2：(两种方法，两种容器) 将 map 统计出的次数的数据放到 vector 中排序，或者放到 priority_queue 中来选出前 k 个。利用仿函数强行控制次数相等的，字典序小的在前面。

方案一：vector

class Solution {
public:
    struct kv_pair {
        // 次数多的在前面，次数相等的时候，字典序小的在前面
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
            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(), kv_pair());
        
        vector<string> ret;
        for (size_t i = 0; i < k; i++) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

方案二：优先级队列

class Solution {
public:
    struct kv_pair {
        // 次数多的在前面，次数相等的时候，字典序小的在前面
        // 要注意优先级队列底层是反的，大堆要实现小于比较，所以这里次数相等，想要字典序小的在前面要比较字典序大的为真
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
            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]++;
        }
        
        priority_queue<pair<string, int>, vector<pair<string, int>>, kv_pair> q(CountMap.begin(), CountMap.end());
        
        vector<string> ret;
        for (size_t i = 0; i < k; i++) {
            ret.push_back(q.top().first);
            q.pop();
        }
        return ret;
    }
};

结语

map 系列容器是 C++ STL 中'键值映射'场景的核心工具，map 的键唯一、multimap 的键冗余特性，精准适配不同业务需求，底层红黑树更是保障了 O(log N) 的高效操作。从 operator[] 的多功能统计，到结构化绑定的简洁遍历，再到算法题中简化复杂逻辑的实战价值，它既降低了开发复杂度，又兼顾了性能与易用性。掌握其使用细节与场景适配，能为日常开发和算法实现提供有力支撑，是 C++ 开发者必备的容器技能。