C++ STL 关联式容器详解：map 与 set 使用

2.2 重要接口与使用示例

✅ 构造方式

set<int> s1; // 默认构造
set<int> s2(s1.begin(), s1.end()); // 迭代器区间构造
set<int> s3 = {1, 2, 3, 4}; // 初始化列表构造
set<int, greater<int>> s4; // 降序 set

✅ 插入与遍历

s.insert(10);
s.insert({20, 30, 40}); // 支持 initializer_list
// 遍历（只读）
for (auto it = s.begin(); it != s.end(); ++it) {
    // *it = 100; // ❌ 错误！不能修改 key
    cout << *it << " ";
}

✅ 查找与删除

auto pos = s.find(30);
if (pos != s.end()) {
    s.erase(pos); // 通过迭代器删除
}
size_t num = s.erase(100); // 直接删除值，返回删除个数（0 或 1）
// 使用 count 判断是否存在
if (s.count(20)) {
    cout << "20 exists" << endl;
}

2.3 multiset：允许重复元素的 set

multiset<int> ms = {5, 2, 5, 1, 5};
cout << ms.count(5); // 输出：3
ms.erase(5); // 删除所有值为 5 的元素

🔴 易错点：multiset::erase(value) 会删除所有等于该值的元素，若只想删除一个，需先 find 获取迭代器再删除。

2.4 经典例题解析

📌 349. 两个数组的交集

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    set<int> s1(nums1.begin(), nums1.end());
    set<int> s2(nums2.begin(), nums2.end());
    vector<int> res;
    auto it1 = s1.begin(), it2 = s2.begin();
    while (it1 != s1.end() && it2 != s2.end()) {
        if (*it1 < *it2)
            ++it1;
        else if (*it1 > *it2)
            ++it2;
        else {
            res.push_back(*it1);
            ++it1;
            ++it2;
        }
    }
    return res;
}

✅ 优点：利用 set 自动去重 + 有序，双指针遍历即可，时间复杂度 O(NlogN)。

📌 142. 环形链表 II（set 降维打击版）

ListNode* detectCycle(ListNode* head) {
    set<ListNode*> visited;
    ListNode* cur = head;
    while (cur) {
        if (visited.count(cur)) return cur;
        visited.insert(cur);
        cur = cur->next;
    }
    return nullptr;
}

✅ 优点：代码简洁，逻辑清晰，无需复杂数学证明，时间复杂度 O(NlogN)，空间复杂度 O(N)。

🗺️ 三、map 系列详解

3.1 map 的基本特性

• 存储键值对 pair<const Key, T>
• key 唯一，按 key 排序
• 支持通过 key 快速查找 value
• 允许修改 value，不允许修改 key

3.2 pair 类型简介

pair<string, int> p1 = {"Alice", 25};
cout << p1.first << " " << p1.second; // Alice 25
auto p2 = make_pair("Bob", 30); // 使用 make_pair 构造

3.3 重要接口与使用示例

✅ 构造与遍历

map<string, int> m = {{"Alice", 90}, {"Bob", 85}};
for (const auto& kv : m) {
    cout << kv.first << ": " << kv.second << endl;
}
// 或使用迭代器
for (auto it = m.begin(); it != m.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

✅ 插入的四种方式

m.insert({"Charlie", 88});
m.insert(make_pair("David", 92));
m.insert(pair<string, int>("Eve", 95));
m["Frank"] = 70; // 最常用！若不存在则插入，存在则修改

🔴 易错点：insert 时如果 key 已存在，不会覆盖原有 value，而 operator[] 会。

✅ operator[] 的三重功能

map<string, int> m;
m["apple"] = 10; // 1. 插入（key 不存在）
m["apple"] = 20; // 2. 修改（key 存在）
int num = m["apple"]; // 3. 查找（返回 value，若不存在则插入默认值 0）

✅ 内部实现简析：

3.4 multimap：允许重复 key 的 map

• 不支持 operator[]（因为一个 key 可能对应多个 value）
• find 返回第一个匹配的迭代器
• count 返回 key 的出现次数

multimap<string, int> mm;
mm.insert({"A", 1});
mm.insert({"A", 2});
cout << mm.count("A"); // 输出：2

3.5 经典例题解析

📌 统计单词频率（map 的经典应用）

string arr[] = {"apple", "banana", "apple", "orange", "banana", "apple"};
map<string, int> countMap;
// 方法 1：find + insert
for (const auto& word : arr) {
    auto it = countMap.find(word);
    if (it == countMap.end()) {
        countMap.insert({word, 1});
    } else {
        it->second++;
    }
}
// 方法 2：operator[] 一行搞定
for (const auto& word : arr) {
    countMap[word]++;
}
for (const auto& kv : countMap) {
    cout << kv.first << ": " << kv.second << endl;
}

📌 138. 随机链表的复制（map 映射法）

Node* copyRandomList(Node* head) {
    map<Node*, Node*> nodeMap;
    Node* cur = head;
    // 第一遍：建立原节点 -> 新节点的映射
    while (cur) {
        nodeMap[cur] = new Node(cur->val);
        cur = cur->next;
    }
    // 第二遍：设置 next 和 random
    cur = head;
    while (cur) {
        nodeMap[cur]->next = nodeMap[cur->next];
        nodeMap[cur]->random = nodeMap[cur->random];
        cur = cur->next;
    }
    return nodeMap[head];
}

✅ 优点：逻辑清晰，无需修改原链表，时间复杂度 O(N)。

📌 692. 前 K 个高频单词（map + 排序）

vector<string> topKFrequent(vector<string>& words, int k) {
    map<string, int> countMap;
    for (const auto& w : words) countMap[w]++;
    vector<pair<string, int>> vec(countMap.begin(), countMap.end());
    // 自定义排序：频率降序，频率相同时字典序升序
    sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
        return a.second > b.second || (a.second == b.second && a.first < b.first);
    });
    vector<string> res;
    for (int i = 0; i < k; ++i) res.push_back(vec[i].first);
    return res;
}

🔄 四、有序 vs 无序容器

📌 选择建议：如果需要有序遍历，选 set/map；如果只关心存在性/快速查找，且不关心顺序，选 unordered_xxx；如果 key 是自定义类型，使用 unordered_xxx 需自定义哈希函数。

💎 五、核心总结与易错点

✅ 必须掌握的重点：

1. set 用于去重排序，map 用于键值映射
2. operator[] 在 map 中具有插入、修改、查找三重功能
3. 关联式容器的迭代器是双向迭代器，支持 ++ 和 --
4. 红黑树保证操作时间复杂度为 O(logN)，且遍历有序

❌ 常见易错点：

1. 试图修改 set 或 map 的 key → 编译错误
2. 误以为 map::insert 会覆盖 value → 实际上不会
3. 对 multimap 使用 operator[] → 编译错误（不支持）
4. 忽略 unordered_xxx 的最坏时间复杂度 → 哈希冲突可能导致 O(N)
5. 遍历时删除元素未更新迭代器 → 可能导致未定义行为

🚀 六、进阶练习建议

1. 尝试用 map 实现一个简单的电话簿系统（姓名→电话）
2. 用 set 实现论文查重中的停用词过滤
3. 结合 priority_queue 和 map 实现实时 TopK 统计
4. 自定义一个类作为 map 的 key，实现比较运算符或哈希函数