C++ 标准库：map 与 set 容器详解与实战

构造时通常只需关注无参、区间拷贝及初始化列表构造。迭代器为双向迭代器。

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

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

// copy (3) 拷贝构造
set(const set& x);

// initializer list (5) 初始化列表构造
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 的增删查

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 << " ";
    }
    cout << endl;
    return 0;
}

2.4 find 和 erase 的使用样例

删除操作需注意返回值。erase(key) 返回删除的元素个数，find 返回迭代器。

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;
    }
    
    // 利用迭代器删除
    cin >> x;
    auto pos = s.find(x);
    if(pos != s.end()) {
        s.erase(pos);
    } else {
        cout << x << "不存在" << endl;
    }
    
    // count 判断是否存在
    cin >> x;
    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};
    
    auto it = s.begin();
    while(it != s.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
    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;
    }
};

环形链表 II

使用 set 记录访问过的节点，若再次遇到则为环入口。

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

3. map 系列的使用

3.1 map 类的介绍

map 存储键值对，底层同样是红黑树。Key 必须唯一且有序，Value 可修改但 Key 不可变。

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

3.2 pair 类型介绍

map 内部节点存储 pair<const Key, T>。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 数据可修改，但 Key 不可修改。

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

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

// 拷贝构造
map(const map& x);

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

3.4 map 的增删查

插入的是 pair 键值对。find 返回迭代器，可直接修改 Value。

// 单个数据插入，如果 key 存在则插入失败
pair<iterator, bool> insert(const value_type& val);

// 列表插入
void insert(initializer_list<value_type> il);

// 查找 k，返回迭代器
iterator find(const key_type& k);

// 查找 k，返回个数
size_type count(const key_type& k) const;

// 删除一个迭代器位置的值
iterator erase(const_iterator position);

// 删除 k，存在返回 1
size_type erase(const key_type& k);

// 删除区间
iterator erase(const_iterator first, const_iterator last);

3.5 map 的数据修改

除了通过迭代器修改，operator[] 是一个多功能接口。它既能查找也能插入，还能修改。

// operator[] 的内部逻辑示意
mapped_type& operator[](const key_type& k) {
    // 1. 如果 k 不在，insert 插入默认值并返回引用
    // 2. 如果 k 在，insert 失败但返回指向该节点的迭代器，进而返回引用
    pair<iterator, bool> ret = insert({k, mapped_type()});
    iterator it = ret.first;
    return it->second;
}

注意：insert 返回的 pair<bool> 中的 bool 表示是否新插入成功，而 map 节点本身存的是 pair<Key, T>，不要混淆。

3.6 构造遍历以及增删查改样例

#include <map>
int main() {
    // initializer_list 构造
    map<string, string> dict = {
        {"left", "左边"},
        {"right", "右边"},
        {"insert", "插入"},
        {"erase", "删除"}
    };
    
    // 迭代遍历
    for(auto it = dict.begin(); it != dict.end(); ++it) {
        cout << it->first << ":" << it->second << endl;
    }
    
    // 插入方式对比
    dict.insert(make_pair("sort", "排序"));
    dict.insert({"auto", "自动的"});
    
    // 范围 for 遍历
    for(auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    
    // 查找与修改
    string str;
    while(cin >> str) {
        auto ret = dict.find(str);
        if(ret != dict.end()) {
            cout << "->" << ret->second << endl;
        } else {
            cout << "无此单词" << endl;
        }
    }
    return 0;
}

3.7 统计频率实战

统计水果出现次数，演示 [] 运算符的隐式插入功能。

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

int main() {
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
    map<string, int> countMap;
    
    for(const auto& str : arr) {
        // 方法一：先查找再决定
        auto ret = countMap.find(str);
        if(ret == countMap.end()) {
            countMap.insert({str, 1});
        } else {
            ret->second++;
        }
        
        // 方法二：直接使用 []，会自动创建默认值
        // countMap[str]++;
    }
    
    for(const auto& e : countMap) {
        cout << e.first << ":" << e.second << endl;
    }
    return 0;
}

3.8 multimap 和 map 的差异

multimap 支持 Key 冗余，因此不支持 [] 运算符（无法确定修改哪一个），仅支持 insert 等基础操作。

3.9 力扣实战示例

随机链表的复制

利用 map 建立原节点与拷贝节点的映射关系。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodeMap;
        Node* copyhead = nullptr, *copytail = nullptr;
        Node* cur = head;
        
        while(cur) {
            if(copytail == nullptr) {
                copyhead = copytail = new Node(cur->val);
            } else {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            nodeMap[cur] = copytail;
            cur = cur->next;
        }
        
        cur = head;
        Node* copy = copyhead;
        while(cur) {
            if(cur->random == nullptr) {
                copy->random = nullptr;
            } else {
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

前 K 个高频单词

结合 map 统计词频，再用 vector 配合自定义排序获取 Top K。

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());
        sort(v.begin(), v.end(), Compare());
        
        vector<string> retv;
        for(size_t i = 0; i < k; ++i) {
            retv.push_back(v[i].first);
        }
        return retv;
    }
};

也可使用优先队列（大堆）优化空间复杂度，原理类似，注意堆顶元素的比较规则。