C++ STL 关联容器实战：set、map 与 multiset 详解

2. 容量操作

• size(): 返回元素个数。
• empty(): 判断容器是否为空。

std::set<int> myset;
myset.insert(10);
if (!myset.empty()) {
    std::cout << "Size: " << myset.size() << std::endl;
}

3. 修改操作

• clear(): 清空所有元素。
• swap(): 交换两个容器的内容。
• insert(): 插入元素，若已存在则不插入。
• erase(): 支持按迭代器、按值或按范围删除。

std::set<int> s;
s.insert(1); s.insert(2); s.insert(3);

// 按值删除
s.erase(2);

// 按迭代器删除
auto it = s.find(1);
if (it != s.end()) s.erase(it);

// 范围删除
auto low = s.lower_bound(2);
auto high = s.upper_bound(4);
s.erase(low, high);

4. 查找与遍历

• find(key): 返回指向元素的迭代器，未找到返回 end()。
• count(key): 集合中元素唯一，返回 0 或 1。
• lower_bound/upper_bound: 二分查找边界。

std::set<int> s = {10, 20, 30};

// 查找
auto it = s.find(20);
if (it != s.end()) {
    std::cout << *it << std::endl;
}

// 区间查找
auto range = s.equal_range(20);
// range.first 指向第一个 >= 20 的元素
// range.second 指向第一个 > 20 的元素

5. 实战示例

#include <iostream>
#include <set>
#include <string>

int main() {
    // 去重并排序
    std::set<int> nums = {5, 2, 9, 2, 5};
    for (const auto& n : nums) {
        std::cout << n << " "; // 输出：2 5 9
    }
    
    // 字符串集合并按字典序排序
    std::set<std::string> words = {"banana", "apple", "cherry"};
    for (const auto& w : words) {
        std::cout << w << " "; // 输出：apple banana cherry
    }
    
    return 0;
}

multiset 容器

std::multiset 允许存储重复元素，同样保持有序。其接口与 set 高度相似，主要区别在于 count() 可返回大于 1 的值，erase(key) 会删除所有匹配项。

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

pair 结构体

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

#include <utility>

std::pair<int, std::string> p(1, "hello");
std::cout << p.first << ": " << p.second << std::endl;

// 辅助函数 make_pair
auto p2 = std::make_pair(1, "world");

map 容器详解

std::map 存储键值对（key-value），键唯一且有序，值可修改。

1. 构造与访问

std::map<std::string, int> scores;
scores["Alice"] = 90; // 自动插入
scores["Bob"] = 85;

// 安全访问
if (scores.count("Alice")) {
    std::cout << scores["Alice"] << std::endl;
}

2. 核心接口对比

• operator[]: 便捷但可能隐式插入新键。若键不存在，会创建默认值。
• find(): 推荐用于查找，避免意外插入。
• insert(): 显式插入，返回 pair<iterator, bool> 指示是否成功。

std::map<int, int> m;
m.insert({1, 10});
m.insert({1, 20}); // 失败，因为 key=1 已存在

auto ret = m.find(1);
if (ret != m.end()) {
    ret->second = 99; // 修改值
}

3. 统计词频示例

#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> words = {"apple", "banana", "apple"};
    std::map<std::string, int> freq;
    
    for (const auto& w : words) {
        freq[w]++; // 简化写法：查找 + 插入 + 计数
    }
    
    for (const auto& [k, v] : freq) {
        std::cout << k << ": " << v << std::endl;
    }
    return 0;
}

multimap 容器

std::multimap 允许键重复，适用于一对多映射关系。不支持 operator[]，需使用 insert 和 equal_range 处理多个相同键。

OJ 实战演练

1. 两个数组的交集 (LeetCode 349)

利用 set 的去重特性快速求解。

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

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> result;
        
        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 {
                result.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return result;
    }
};

2. 环形链表 II (LeetCode 142)

利用 set 检测节点是否重复访问。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> visited;
        ListNode* cur = head;
        while (cur) {
            if (!visited.insert(cur).second) {
                return cur; // 插入失败说明已存在，即环入口
            }
            cur = cur->next;
        }
        return nullptr;
    }
};

3. 前 K 个高频单词 (LeetCode 692)

结合 map 统计频率与 priority_queue 排序。

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.first > y.first; // 字典序大优先级低
            return x.second < y.second; // 频率小优先级低
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> freq;
        for (const auto& w : words) freq[w]++;
        
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> pq(freq.begin(), freq.end());
        
        vector<string> res;
        for (int i = 0; i < k; ++i) {
            res.push_back(pq.top().first);
            pq.pop();
        }
        return res;
    }
};

总结

STL 关联容器是 C++ 开发中的利器。set 和 map 适合需要唯一键和有序性的场景，multiset 和 multimap 则处理允许重复的情况。掌握它们的底层机制（如红黑树）、接口细节（如 insert 返回值含义）以及与其他容器的配合使用，能显著提升代码效率与可读性。在实际刷题或工程中，建议优先使用 find 而非 operator[] 以避免不必要的内存分配，并根据具体需求选择合适的数据结构。