C++ STL 容器详解：map 与 set 原理及实战

3. 增删查操作

set 的核心接口包括 insert、find、erase、count 以及区间查询 lower_bound/upper_bound。

• insert: 返回 pair<iterator, bool>，bool 指示是否插入成功。
• find: 返回迭代器，若未找到返回 end()。
• erase: 可删除指定位置、指定值或区间。
• count: 对于 set，返回 0 或 1；对于 multiset，返回实际个数。

增删查示例

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s = { 1, 4, 0, 34, 12, 56 };
    
    // 删除最小值
    s.erase(s.begin());
    
    // 直接删除值，返回删除的元素个数
    int x = 0;
    cin >> x;
    if (s.erase(x) == 0) {
        cout << x << "不存在!" << endl;
    }
    
    // 先查找再删除
    int y = 0;
    cin >> y;
    auto pos = s.find(y);
    if (pos != s.end()) {
        s.erase(pos);
    }
    
    // 利用 count 判断存在性
    if (s.count(x)) {
        cout << x << "在！" << endl;
    }
    return 0;
}

区间查询 lower_bound / upper_bound

这两个接口非常实用，用于查找大于等于或大于某值的第一个元素，常用于处理区间问题。

set<int> s = { 10, 20, 35, 40, 50, 65, 70, 80, 90 };
// 查找 >= 30 的位置
auto itlow = s.lower_bound(30);
// 查找 > 60 的位置
auto itup = s.upper_bound(60);
// 删除 [30, 60] 区间的值
s.erase(itlow, itup);

4. Multiset 与 Set 的差异

multiset 允许元素冗余（即可以存储多个相同的值）。主要差异体现在：

• insert: 总是成功插入。
• find: 返回中序第一个匹配项。
• count: 返回该值出现的总次数。
• erase(val): 删除所有等于 val 的元素。

multiset<int> s = { 1, 4, 3, 4, 6, 4, 8, 3, 0 };
for (auto e : s) {
    cout << e << " "; // 输出：0 1 3 3 4 4 4 6 8
}

5. 实战应用：LeetCode 题目

两个数组的交集

利用 set 的去重特性，可以快速找出两个数组的公共元素。

class Solution {
public:
    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> ret;
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        while (it1 != s1.end() && it2 != s2.end()) {
            if (*it1 < *it2) {
                it1++;
            } else if (*it1 > *it2) {
                it2++;
            } else {
                ret.push_back(*it1);
                it1++; it2++;
            }
        }
        return ret;
    }
};

环形链表检测

使用 set 记录已访问节点，若再次遇到则说明有环。

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while (cur) {
            if (s.count(cur)) return cur; // 入环节点
            s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

四、Map 容器详解

1. Map 简介

std::map 按照特定的次序（key 比较）存储键值对。其特点：

• Key 唯一：key 用于排序和唯一标识元素。
• Value 可变：value 存储与 key 关联的内容，可以通过迭代器修改。
• 底层结构：红黑树，支持有序迭代。
• Pair 绑定：内部将 key 和 value 绑定为 pair<const Key, T>。

2. Pair 与 Make_pair

在 map 中，我们频繁使用 pair 来存储键值对。

• pair: 需要显式指定类型，如 pair<string, string>("a", "b")。
• make_pair: 函数模板，自动推导类型，如 make_pair("a", "b")。

推荐使用 make_pair 或初始化列表，减少类型书写负担。

3. 插入方式

map 支持多种插入场景，灵活度很高：

map<string, string> dict;
pair<string, string> kv1("sort", "排序");
dict.insert(kv1); // 使用对象
dict.insert({ "left", "左边" }); // 隐式转换
dict.insert(make_pair("right", "右边")); // make_pair

// 初始化列表构造
map<string,string> dic2 = { 
    {"string", "字符串"}, 
    {"left", "左边"} 
};

注意：dict.insert({"k", "v"}) 实际上是调用 pair 构造函数，而非 initializer_list 构造 map。

4. 迭代与修改

map 的迭代器指向 pair<const Key, T>。Key 部分不可修改，Value 部分可以修改。

auto it = dict.begin();
while (it != dict.end()) {
    // it->first += 'x'; // 错误：Key 不可改
    it->second += "y";   // 正确：Value 可改
    ++it;
}

5. operator[] 的底层逻辑

这是 map 最常用但也最容易误解的接口。operator[] 不仅支持查找，还支持插入和修改。

原理：

1. 如果 key 不存在，operator[] 会先插入 {key, mapped_type()}（默认构造的值），然后返回 value 的引用。
2. 如果 key 存在，直接返回 value 的引用。

这意味着 map[key]++ 这种写法是合法的：它会自动创建新条目并计数，或者更新旧条目。

// 统计水果出现次数
string arr[] = { "苹果", "西瓜", "苹果", "香蕉" };
map<string, int> countMap;

// 优化写法：利用 [] 的自动插入 + 引用特性
for (const auto& str : arr) {
    countMap[str]++;
}

// 对比传统写法（需先 find）
for (const auto& str : arr) {
    auto ret = countMap.find(str);
    if (ret == countMap.end()) {
        countMap.insert({str, 1});
    } else {
        ret->second++;
    }
}

6. Erase 注意事项

erase 可能会导致迭代器失效。在遍历过程中删除元素时，务必使用 erase 的返回值更新迭代器，或使用 C++11 后的 it = container.erase(it) 模式。

五、Multimap

multimap 类似于 map，但允许 key 重复。由于 key 可能不唯一，operator[] 无法确定返回哪个 value，因此 multimap 重载了 operator[] 的行为或不提供该功能（具体视编译器实现而定，标准建议避免使用）。查找时使用 equal_range 获取一个区间。

六、总结

• Set/Multiset: 用于唯一性或可重复的键值集合，底层红黑树，有序。
• Map/Multimap: 用于键值映射，key 唯一或可重复，底层红黑树，有序。
• Operator[]: 仅适用于 map，兼具查找、插入、修改功能，但需注意性能开销（涉及插入时的树调整）。
• Pair: 理解 map 内部存储结构的关键，便于手动构建键值对。

掌握这些容器的特性与底层机制，能帮助我们在算法设计和工程开发中做出更合适的选择。