C++ STL 容器详解：set 与 map 的使用及实战

修改操作

• insert: 插入元素，返回 pair<iterator, bool>，若元素已存在则插入失败。
• erase: 支持按值删除、按迭代器删除、按范围删除。
• clear: 清空容器。
• swap: 交换两个容器的内容。

// insert 示例
set<int> s;
s.insert(10); // 成功
auto ret = s.insert(10); // 失败，ret.second 为 false

// erase 示例
s.erase(10);        // 按值删除
auto it = s.find(20);
s.erase(it);        // 按迭代器删除
s.erase(it, s.end()); // 按范围删除

查找与遍历

• find(key): 返回指向元素的迭代器，未找到返回 end()。
• count(key): 在 set 中只能返回 0 或 1。
• lower_bound(key): 返回第一个不小于 key 的元素迭代器。
• upper_bound(key): 返回第一个大于 key 的元素迭代器。
• equal_range(key): 同时返回 lower_bound 和 upper_bound。

// 查找与区间删除示例
set<int> myset;
for(int i=1; i<10; ++i) myset.insert(i*10); // 10, 20...90

auto itlow = myset.lower_bound(30); // 指向 30
auto itup = myset.upper_bound(60);  // 指向 70
myset.erase(itlow, itup);           // 删除 [30, 60] 区间

set 实战技巧

1. 去重与排序: set 天然去重且有序，适合处理需要唯一性数据的场景。
2. 常量迭代器: set 的迭代器是常量迭代器，不能通过迭代器修改元素值，否则会破坏红黑树结构。
3. 字符串字典序: set<string> 默认按 ASCII 码字典序排序。

multiset 容器

multiset 与 set 类似，但允许元素重复。适用于需要保留所有重复数据的场景。

• 区别: set 元素唯一，multiset 允许重复。
• 操作差异: erase(key) 会删除所有匹配的元素；count(key) 返回实际重复次数；find(key) 仅返回第一个匹配项。

multiset<int> ms = {4, 2, 7, 2, 4};
// 输出：2 2 4 4 7
// count(4) 返回 2
// erase(4) 删除所有 4

pair 类模板

std::pair 用于将两个不同类型的数据组合成一个逻辑单元，常用于 map 的键值对存储。

#include <utility>
std::pair<int, string> p(1, "hello");
p.first = 2;      // 修改第一个元素
p.second = "world"; // 修改第二个元素

map 容器详解

std::map 存储键值对 (pair<const Key, T>)，按键排序，键必须唯一。

模板参数

template<class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key, T>>>
class map;

• Key: 键类型，决定排序和查找依据。
• T: 映射值类型。
• Compare: 键的比较规则。

核心接口

1. operator[]: 多功能接口。若键不存在，自动插入默认值并返回引用；若存在，返回引用。注意：此操作可能隐式插入数据。
2. find: 高效查找，返回迭代器。
3. insert: 显式插入键值对，返回插入状态。

map<string, int> scores;
scores["Alice"] = 90; // 隐式插入
scores["Bob"]++;      // 隐式插入并自增

// 推荐：避免隐式插入时使用 find
if(scores.count("Charlie") == 0) {
    scores.insert({"Charlie", 80});
}

map 与 multimap 对比

• map: 键唯一，像严格的字典。
• multimap: 键可重复，像宽松的便签本，适合一对多映射。
• 注意: multimap 不支持 operator[]，因为无法明确指定修改哪一个重复键对应的值。

OJ 实战案例

1. 两个数组的交集

利用 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;
    }
};

2. 环形链表 II

利用 set 存储访问过的节点指针，若插入失败说明遇到环。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> visited;
        ListNode* cur = head;
        while(cur) {
            auto ret = visited.insert(cur);
            if(!ret.second) return cur; // 插入失败，发现环
            cur = cur->next;
        }
        return nullptr;
    }
};

3. 随机链表的复制

利用 map 建立原节点与拷贝节点的映射关系，分两步完成深拷贝。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> m;
        Node* copyHead = nullptr;
        Node* copyTail = nullptr;
        Node* curr = head;
        
        // 第一步：复制 next 指针
        while(curr) {
            if(!copyTail) {
                copyHead = copyTail = new Node(curr->val);
            } else {
                copyTail->next = new Node(curr->val);
                copyTail = copyTail->next;
            }
            m[curr] = copyTail;
            curr = curr->next;
        }
        
        // 第二步：处理 random 指针
        curr = head;
        Node* copy = copyHead;
        while(curr) {
            copy->random = m[curr->random];
            curr = curr->next;
            copy = copy->next;
        }
        return copyHead;
    }
};

4. 前 K 个高频单词

统计词频后，根据频率和字典序排序。可使用 sort、stable_sort 或优先队列。

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
            if(x.second != y.second)
                return x.second > y.second; // 频率高优先
            return x.first < y.first;       // 字典序小优先
        }
    };
    
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        for(auto& w : words) m[w]++;
        
        vector<pair<string, int>> v(m.begin(), m.end());
        sort(v.begin(), v.end(), Compare());
        
        vector<string> ret;
        for(int i=0; i<k; ++i) ret.push_back(v[i].first);
        return ret;
    }
};