C++ STL 中 map 与 set 容器的核心用法与实战

2.2 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和find是日常最常用的接口。count可以用来判断元素是否存在，返回值为 0 或 1。

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 配合 erase 完成。

int main() {
    set<int> myset;
    for(int i = 1; i < 10; i++) {
        myset.insert(i * 10); // 10 20 30 ... 90
    }
    
    // 实现查找到的 [itlow, itup] 包含 [30, 60] 区间
    auto itlow = myset.lower_bound(30); // 返回 >=30
    auto itup = myset.upper_bound(60);  // 返回 >60
    
    // 删除这段区间的值
    myset.erase(itlow, itup);
    
    for(auto e : myset) {
        cout << e << " ";
    }
    return 0;
}

2.5 multiset 和 set 的差异

multiset和set基本完全相似，主要的区别点在于 multiset支持键值冗余。那么 insert/find/count/erase都围绕着支持键值冗余有所差异。

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;
    
    // 相比较 set 不同的是，x 可能会存在多个，find 查找的是中序的第一个
    int x; cin >> x;
    auto pos = s.find(x);
    while(pos != s.end() && *pos == x) {
        cout << *pos << " ";
        ++pos;
    }
    cout << endl;
    
    // count 会返回 x 的实际个数
    cout << s.count(x) << endl;
    
    // erase 会删掉里面的所有的 x
    s.erase(x);
    for(auto e : s) {
        cout << e << " ";
    }
    return 0;
}

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

利用 set 的特性可以快速去重并排序，非常适合处理这类问题。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 这里用 set 实现了对数组的排序 + 去重
        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; // 等于 1 即为入口点
            else s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

3. map 系列的使用

3.1 map 类的介绍

map底层使用红黑树实现的，增删查改的效率是 O(log n)。Key 的值是有序的。声明如下，Key 就是 map 底层关键字的类型，T 是 map 底层 Value 的类型。

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<Key,T>存储键值对数据。pair是一个类模板，里面有两个成员变量，一个是 first,一个是 second。

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

// make_pair 辅助构造
inline pair<T1, T2> make_pair(T1 x, T2 y) {
    return pair<T1, T2>(x, y);
}

3.3 map 的构造与遍历

map支持正向迭代器遍历和反向迭代器遍历，遍历默认按 Key 的升序。支持 value数据的修改，但不支持 Key的修改。修改关键字的数据破坏了底层搜索树的结构。

#include <map>
int main() {
    // initializer_list 构造以及迭代遍历
    map<string, string> dict = {{"left","左边"},{"right","右边"},{"insert","插入"}};
    
    // 原生写法
    map<string, string>::iterator it = dict.begin();
    while(it != dict.end()) {
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
    
    // 范围 for 遍历
    for(auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    
    // C++17 结构化绑定
    // for (const auto& [k,v] : dict)
    //     cout << k << ":" << v << endl;
    
    return 0;
}

3.4 map 的增删查改

map的增接口，插入的是 pair 的键值对数据。查和删的接口只用关键字 Key。find返回的是 iterator,不仅仅可以找到 Key 在不在，还能找到映射的 Value，同时通过迭代还能修改 Value。

// insert 返回 pair<iterator, bool>
pair<iterator, bool> insert(const value_type& val);
// 查找 k，返回 k 所在的迭代器
iterator find(const key_type& k);
// 删除 k，k 存在返回 1
size_type erase(const key_type& k);

3.5 map 的数据修改

map 第一个支持修改的方式是通过迭代器，迭代器遍历时或者 find 返回 Key 所在的 iterator 修改。map 还有一个非常重要的修改接口 operator[]，但是 operator[]不仅仅支持数据的修改，还支持插入数据和查找数据，所以它是一个多功能复合接口。

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

注意：operator[]在查找不到时会隐式插入一个默认值的元素，这在某些场景下可能不是预期的行为，此时应优先使用 find。

3.6 实战案例：统计水果出现次数

#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++;
        }
    }
    
    // 方法二：直接用 [] (注意它会隐式创建)
    // for(const auto& str : arr) countMap[str]++;
    
    for(const auto& e : countMap) {
        cout << e.first << ":" << e.second << endl;
    }
    return 0;
}

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

利用 map统计频率后，放入 vector排序即可。注意题目要求的特殊排序规则（频率高在前，频率相同字典序小在前）。

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> strV;
        for(int i = 0; i < k; ++i) {
            strV.push_back(v[i].first);
        }
        return strV;
    }
};

4. 总结

set和map都是基于红黑树实现的关联式容器，提供了高效的查找能力。set用于去重和有序存储，map用于建立键值映射。在实际开发中，要注意 map的 operator[]会隐式插入元素，而 multiset/multimap允许重复键。理解这些细节，能帮你写出更健壮、高效的 C++ 代码。