C++ STL 容器 set 与 map 使用详解

3. 常用操作

容量操作

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

std::set<int> myset;
myset.insert(10);
std::cout << "Size: " << myset.size() << '\n';
if (myset.empty()) {
    std::cout << "Empty" << '\n';
} else {
    std::cout << "Not Empty" << '\n';
}

修改操作

• clear()：清空容器。
• swap()：交换两个容器的内容。
• insert()：插入元素。
• erase()：删除元素。

// 插入
myset.insert(20);
auto ret = myset.insert(30); // 返回 pair<iterator, bool>

// 删除
myset.erase(20); // 按值删除
myset.erase(it); // 按迭代器删除
myset.erase(it1, it2); // 按范围删除

查找操作

• find()：查找元素。
• count()：统计元素出现次数（set 中为 0 或 1）。
• lower_bound() / upper_bound()：二分查找边界。
• equal_range()：返回指定元素的上下界范围。

auto it = myset.find(20);
if (it != myset.end()) {
    std::cout << *it << '\n';
}

auto range = myset.equal_range(20);
// range.first -> lower_bound
// range.second -> upper_bound

4. 使用示例

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

int main() {
    // 去重 + 排序
    set<int> s = {5, 2, 7, 2, 8}; 
    // 输出：2 5 7 8

    // 降序排序
    set<int, greater<int>> s_desc;
    s_desc.insert(10);
    s_desc.insert(5);
    // 输出：10 5

    // 遍历
    for (auto e : s) {
        cout << e << " ";
    }
    return 0;
}

multiset 容器

1. 介绍

std::multiset 与 set 类似，但允许重复元素。

2. 区别

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

int main() {
    multiset<int> ms = {4, 2, 4, 8, 4};
    // 输出：2 4 4 4 8
    cout << ms.count(4) << endl; // 输出 3
    ms.erase(4); // 删除所有 4
    return 0;
}

pair 类模板

1. 介绍

std::pair 将两个不同类型的数据组合成一个逻辑单元。

#include <utility>
std::pair<int, string> p(1, "hello");
// 访问
p.first = 2;
p.second = "world";

2. 使用

常用于 map 的键值对存储。

typedef pair<const Key, T> value_type;
// 辅助函数 make_pair
auto p = make_pair(1, "test");

map 容器

1. 介绍

std::map 存储键值对（Key-Value），按键排序，键唯一。

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

2. 常用操作

• operator[]：访问或插入键值对。
• find()：查找键。
• insert()：插入键值对。
• erase()：删除元素。

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

int main() {
    map<string, int> m;
    m["apple"] = 5;      // 插入/修改
    m["banana"] = 3;     // 插入

    if (m.count("apple")) {
        cout << "Found apple" << endl;
    }

    auto it = m.find("banana");
    if (it != m.end()) {
        it->second = 10; // 修改值
    }

    return 0;
}

3. 使用示例

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

int main() {
    // 统计词频
    string arr[] = {"apple", "banana", "apple"};
    map<string, int> countMap;

    for (const auto& str : arr) {
        countMap[str]++; // 自动处理存在与否
    }

    for (const auto& e : countMap) {
        cout << e.first << ": " << e.second << endl;
    }
    return 0;
}

multimap 容器

1. 介绍

std::multimap 允许键重复，适用于一对多映射关系。

2. 区别

• map：键唯一，不支持 operator[] 的多值场景。
• 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) {
            if (!visited.insert(cur).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) {
            if (curr->random) {
                copy->random = m[curr->random];
            }
            curr = curr->next;
            copy = copy->next;
        }
        return copyHead;
    }
};

4. 前 K 个高频单词

题目描述：找出出现频率最高的前 K 个单词。

思路：利用 map 统计频率，结合 sort 或 priority_queue 排序。

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        for (const auto& w : words) {
            m[w]++;
        }

        vector<pair<string, int>> v(m.begin(), m.end());
        sort(v.begin(), v.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
            if (a.second != b.second) return a.second > b.second;
            return a.first < b.first;
        });

        vector<string> ret;
        for (int i = 0; i < k; ++i) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};