C++ map 与 set 容器详解：从原理到实战

构造时通常只需关注无参、区间拷贝及初始化列表三种方式。迭代器为双向迭代器，支持正向与反向遍历。

// 无参构造
explicit set(const key_compare& comp = key_compare(), 
             const allocator_type& alloc = allocator_type());

// 区间构造
template<class InputIterator>
set(InputIterator first, InputIterator last,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

// 初始化列表构造
set(initializer_list<value_type> il,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

// 迭代器
iterator begin(); iterator end();
reverse_iterator rbegin(); reverse_iterator rend();

2.3 增删查示例

这里展示基础的插入、遍历及去重效果。注意 set 中的元素不可修改，因为会破坏红黑树结构。

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

int main() {
    // 去重 + 升序排序
    set<int> s;
    s.insert(2);
    s.insert(1);
    s.insert(5);
    s.insert(6);

    auto it = s.begin();
    while (it != s.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 插入 initializer_list，已存在则失败
    s.insert({1, 5, 3, 2, 7, 9});
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    // string 类对象比较按 ASCII 码
    set<string> strset = {"sort", "add", "insert"};
    for (auto &e : strset) {
        cout << e << " ";
    }
    return 0;
}

2.4 find 和 erase 的使用

erase 返回被删除元素的个数，find 返回迭代器。利用 count 可以快速判断元素是否存在。

int main() {
    set<int> s = {2, 7, 4, 3, 1, 9, 5, 0};
    
    // 删除最小值
    s.erase(s.begin());
    
    int x;
    cin >> x;
    // 删除指定值，返回删除个数
    int num = s.erase(x);
    if (num == 0) {
        cout << x << "不存在!" << endl;
    }
    
    // 查找后删除
    auto pos = s.find(x);
    if (pos != s.end()) {
        s.erase(pos);
    }
    
    // count 判断存在性
    if (s.count(x)) {
        cout << x << "在!" << endl;
    } else {
        cout << x << "不存在!" << endl;
    }
    return 0;
}

删除区间值

利用 lower_bound 和 upper_bound 可以高效删除一段范围内的元素。

int main() {
    set<int> myset;
    for (int i = 1; i < 10; i++) {
        myset.insert(i * 10); // 10 20 ... 90
    }
    
    // 查找 [30, 60] 区间
    auto itlow = myset.lower_bound(30); // >=30
    auto itup = myset.upper_bound(60);  // >60
    
    // 删除该区间
    myset.erase(itlow, itup);
    return 0;
}

2.5 multiset 和 set 的差异

主要区别在于 multiset 允许键值冗余。find 返回第一个匹配项，count 返回总个数，erase(key) 会删除所有匹配项。

int main() {
    multiset<int> s = {4, 6, 4, 3, 6, 7, 8, 9, 2, 5, 3, 7, 8, 9};
    
    int x;
    cin >> x;
    auto pos = s.find(x);
    while (pos != s.end() && *pos == x) {
        cout << *pos << " ";
        ++pos;
    }
    cout << endl;
    
    // count 返回实际个数
    cout << s.count(x) << endl;
    
    // erase 删除所有 x
    s.erase(x);
    return 0;
}

2.6 实战案例：两个数组的交集

利用 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.7 实战案例：环形链表 II

遍历链表时将节点存入 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;
    }
};

3. map 系列的使用

3.1 map 类的介绍

map 存储键值对，底层同样是红黑树。Key 必须唯一且可比较，Value 可修改。遍历顺序按 Key 升序。

template <class Key,           // key_type
            class T,            // mapped_type
            class Compare = less<Key>, // key_compare
            class Alloc = allocator<pair<const Key, T>>> // allocator_type
class map;

3.2 pair 类型介绍

map 内部节点存储的是 pair<const Key, T>。pair 包含 first 和 second 成员。

template <class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    // 构造函数略
};

// 辅助工厂函数
template<class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y);

3.3 map 的构造与遍历

支持多种构造方式，包括初始化列表。Key 不可修改，Value 可修改。

// 初始化列表构造
map<string, string> dict = {
    {"left", "左边"},
    {"right", "右边"},
    {"insert", "插入"}
};

// 迭代遍历
for (auto& e : dict) {
    cout << e.first << ":" << e.second << endl;
}

3.4 map 的增删查改

insert 返回 pair<iterator, bool>，指示是否插入成功。operator[] 功能强大，兼具查找、插入和修改功能，但需注意它会在 Key 不存在时隐式创建默认 Value。

// insert 返回值说明
// first: 指向 key 所在节点的迭代器
// second: true 表示新插入，false 表示已存在
pair<iterator, bool> insert(const value_type& val);

// operator[] 内部逻辑示意
mapped_type& operator[](const key_type& k) {
    pair<iterator, bool> ret = insert({k, mapped_type()});
    return ret.first->second;
}

3.5 统计单词出现次数

这是 map 最经典的用法之一。推荐使用 operator[] 简化代码，或者用 find 避免不必要的默认构造开销。

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

int main() {
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果"};
    map<string, int> countMap;

    // 方法一：使用 find
    for (const auto& str : arr) {
        auto ret = countMap.find(str);
        if (ret == countMap.end()) {
            countMap.insert({str, 1});
        } else {
            ret->second++;
        }
    }

    // 方法二：直接使用 [] (更简洁)
    // for (const auto& str : arr) countMap[str]++;

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

3.6 multimap 和 map 的差异

multimap 支持 Key 冗余，因此不支持 operator[]（无法确定修改哪一个 Value），仅支持 insert 等接口。

3.7 实战案例：随机链表的复制

利用 map 建立原节点与拷贝节点的映射关系，解决 random 指针指向问题。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodeMap;
        Node* copyhead = nullptr, *copytail = nullptr;
        Node* cur = head;

        // 1. 复制节点并建立映射
        while (cur) {
            if (!copytail) {
                copyhead = copytail = new Node(cur->val);
            } else {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            nodeMap[cur] = copytail;
            cur = cur->next;
        }

        // 2. 处理 random 指针
        cur = head;
        Node* copy = copyhead;
        while (cur) {
            copy->random = cur->random ? nodeMap[cur->random] : nullptr;
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

3.8 实战案例：前 K 个高频单词

统计频率后，将 map 转为 vector 进行排序。注意稳定性要求，可使用 stable_sort 或自定义比较器配合 priority_queue。

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) {
            // 次数多在前，次数相同字典序小在前
            return kv1.second > kv2.second || 
                   (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for (auto& str : words) {
            countMap[str]++;
        }

        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        stable_sort(v.begin(), v.end(), [](const auto& a, const auto& b){
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        });

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

掌握这些容器的底层原理与 API 细节，能让你在处理复杂数据结构问题时游刃有余。在实际开发中，根据是否需要排序、是否允许重复来选择正确的容器，是编写高性能 C++ 代码的关键。