C++ STL 进阶：set 与 map 容器详解

常见构造

#include<iostream>
#include<set>

// 1. 定义一个普通函数作为比较函数
bool fncomp(int lhs, int rhs) {
    return lhs < rhs;
}

// 2. 定义一个函数对象（仿函数）类
struct classcomp {
    bool operator()(const int& lhs, const int& rhs) const {
        return lhs < rhs;
    }
};

int main() {
    /*------------------使用不同的构造函数创建 set 容器------------------*/
    // 1. 使用'默认构造函数'创建一个空的 set，元素类型为 int
    std::set<int> s1;
    
    // 2. 使用'迭代器范围构造函数'创建包含 5 个元素的 set
    int myints[] = {10, 20, 30, 40, 50};
    std::set<int> s2(myints, myints + 5);
    
    // 3. 使用'拷贝构造函数'创建 set 容器
    std::set<int> s3(s2);
    
    // 4. 使用'迭代器构造函数'创建 set
    std::set<int> s4(s2.begin(), s2.end());
    
    /*------------------使用不同的方式作为 set 容器的比较器------------------*/
    // 5. 使用'自定义的函数对象'作为比较器
    std::set<int, classcomp> s5;
    
    // 6. 使用'函数指针'作为比较器
    bool (*fn_pt)(int, int) = fncomp;
    std::set<int, bool(*)(int, int)> s6(fn_pt);
    
    return 0;
}

容量操作

std::set::size

返回容器中元素的数量。

#include<iostream>
#include<set>
int main() {
    std::set<int> myints;
    std::cout << "初始状态下的 set 大小的 size 为：" << myints.size() << '\n';
    for (int i = 0; i < 10; ++i) myints.insert(i);
    std::cout << "插入 10 个元素后 set 大小的 size 为：" << myints.size() << '\n';
    myints.insert(100);
    std::cout << "插入元素 100 后 set 大小的 size 为：" << myints.size() << '\n';
    myints.erase(5);
    std::cout << "删除 5 个元素后 set 大小的 size 为：" << myints.size() << '\n';
    return 0;
}

std::set::empty

判断容器是否为空。

#include<iostream>
#include<set>
int main() {
    std::set<int> myset;
    myset.insert(20);
    myset.insert(30);
    myset.insert(10);
    std::cout << "myset 容器中的内容为:";
    while (!myset.empty()) {
        std::cout << ' ' << *myset.begin();
        myset.erase(myset.begin());
    }
    std::cout << '\n';
    return 0;
}

修改操作

std::set::clear

清空容器内容。

std::set::swap

交换两个 set 的内容。

std::set::insert

插入元素，返回 pair<iterator, bool>，表示是否插入成功及迭代器位置。

#include<iostream>
#include<set>
int main() {
    std::set<int> myset;
    std::set<int>::iterator it;
    std::pair<std::set<int>::iterator, bool> ret;

    /*--------------------插入形式一：单个元素的插入--------------------*/
    for (int i = 1; i <= 5; ++i) {
        myset.insert(i * 10);
    }
    // 尝试插入已存在的元素 20
    ret = myset.insert(20);
    if (ret.second == false) it = ret.first;

    /*--------------------插入形式二：带提示位置的插入--------------------*/
    myset.insert(it, 25);
    myset.insert(it, 24);
    myset.insert(it, 26);

    /*--------------------插入形式三：范围插入--------------------*/
    int myints[] = {5, 10, 15};
    myset.insert(myints, myints + 3);
    return 0;
}

std::set::erase

删除元素，支持按迭代器、按值、按范围删除。

#include<iostream>
#include<set>
int main() {
    std::set<int> myset;
    std::set<int>::iterator it;
    
    // 插入元素
    for (int i = 1; i < 10; i++) {
        myset.insert(i * 10);
    }
    
    // 让迭代器 it 指向第二个元素 20
    it = myset.begin(); ++it;

    /*--------------------删除形式一：迭代器位置删除--------------------*/
    myset.erase(it);

    /*--------------------删除形式二：按值删除--------------------*/
    myset.erase(40);

    /*--------------------删除形式三：迭代器范围删除--------------------*/
    it = myset.find(60);
    myset.erase(it, myset.end());
    return 0;
}

比较操作

std::set::key_comp

获取键比较函数对象。

std::set::value_comp

获取值比较函数对象。

其他操作

std::set::find

查找元素，返回迭代器，未找到返回 end()。

std::set::count

统计元素出现次数（set 中为 0 或 1）。

std::set::lower_bound / upper_bound / equal_range

二分查找相关接口，用于定位区间。

#include<iostream>
#include<set>
int main() {
    std::set<int> myset;
    std::set<int>::iterator itlow, itup;
    for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 ... 90
    
    itlow = myset.lower_bound(30); // ^
    itup = myset.upper_bound(60);  // ^
    myset.erase(itlow, itup);      // 10 20 70 80 90
    return 0;
}

使用示例

代码示例 1：基础特性与遍历

#include<iostream>
#include<set>
using namespace std;
int main() {
    set<int> s;
    // 插入元素：重复元素会被自动过滤
    s.insert(5); s.insert(2); s.insert(7); s.insert(5);
    
    // 迭代器遍历：set 的迭代器是常量迭代器
    auto it = s.begin();
    while (it != s.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
    // 批量插入
    s.insert({2, 8, 3, 9});
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    // 字符串 set：按字典序排序
    set<string> strset = {"sort", "insert", "add"};
    for (auto& e : strset) {
        cout << e << " ";
    }
    return 0;
}

代码示例 2：查找与删除

#include<iostream>
#include<set>
using namespace std;
int main() {
    set<int> s = {4, 2, 7, 2, 8, 5, 9}; // 去重后升序：{2, 4, 5, 7, 8, 9}
    
    // 迭代器位置删除
    s.erase(s.begin());
    
    // 按值删除
    int x; cin >> x;
    int num = s.erase(x);
    if (num == 0) cout << x << " 不存在！" << endl;
    else cout << x << " 存在！" << endl;
    
    // 先查找再删除
    cin >> x;
    auto pos = s.find(x);
    if (pos != s.end()) s.erase(pos);
    
    // 利用 count 间接判断
    cin >> x;
    if (s.count(x)) cout << x << " 在！" << endl;
    else cout << x << " 不存在！" << endl;
    return 0;
}

multiset 容器

介绍

std::multiset 允许元素重复，底层同样由红黑树实现，元素自动排序。

区别

• set：自动去重，元素唯一。
• multiset：允许元素重复，侧重按序存储重复数据。

#include<iostream>
#include<set>
using namespace std;
int main() {
    // multiset 保留所有重复值
    multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
    
    // 遍历输出排序后的所有元素
    auto it = s.begin();
    while (it != s.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
    // find 特性：仅返回第一个匹配的元素迭代器
    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 特性：按值删除时，删除所有匹配的元素
    cin >> x;
    s.erase(x);
    return 0;
}

pair 类模板

介绍

std::pair 用于将两个不同类型的数据组合成一个逻辑单元，位于 <utility> 头文件。

语法：std::pair<Type1, Type2> pairName(value1, value2);

特性

1. 元素访问：通过 first 和 second 成员变量访问。
2. 构造与赋值：支持默认构造、拷贝构造、赋值操作。
3. 比较操作：支持按字典序比较（先比 first，若相等再比 second）。

使用

在 map 中，键值对的类型是 pair<const Key, T>。

#include<utility>
// 辅助函数 make_pair
template<class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y) {
    return pair<T1, T2>(x, y);
}

map 容器

介绍

std::map 是关联式容器，存储键值对 (Key, 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;

• 键类型（Key）：用于索引和排序的关键字类型。
• 映射值类型（T）：与键关联的具体数据类型。
• 比较器（Compare）：定义键之间的排序规则。

常见构造

#include<iostream>
#include<map>
int main() {
    // 1. 默认构造函数
    std::map<char, int> m1;
    m1['a'] = 10; m1['b'] = 30;
    
    // 2. 范围构造函数
    std::map<char, int> m2(m1.begin(), m1.end());
    
    // 3. 拷贝构造函数
    std::map<char, int> m3(m2);
    
    return 0;
}

容量操作

• std::map::size：返回元素数量。
• std::map::empty：判断是否为空。

访问操作

std::map::operator[]

多功能接口，支持修改已存在的键值对、插入新数据或查找数据（键不存在时自动插入默认值）。

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
    map<string, string> dict;
    
    // 插入功能
    dict["insert"];
    
    // 插入 + 修改
    dict["left"] = "左边";
    
    // 修改功能
    dict["left"] = "左边、剩余";
    
    // 查找功能
    cout << dict["left"] << endl;
    return 0;
}

修改操作

• std::map::clear：清空容器。
• std::map::swap：交换内容。
• std::map::insert：插入键值对。
• std::map::erase：删除元素。

其他操作

• std::map::find：查找键。
• std::map::count：统计键出现次数（map 中为 0 或 1）。
• std::map::lower_bound / upper_bound / equal_range：区间查找。

使用示例

代码示例 1：构造与遍历

#include<iostream>
#include<map>
using namespace std;
int main() {
    map<string, string> dict = {{"left", "左边"}, {"right", "右边"}};
    
    // 迭代器遍历
    auto it = dict.begin();
    while (it != dict.end()) {
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
    
    // insert 插入
    dict.insert(make_pair("sort", "排序"));
    
    // find 查找
    string str;
    while (cin >> str) {
        auto ret = dict.find(str);
        if (ret != dict.end()) {
            cout << "=> " << ret->second << endl;
        } else {
            cout << "无此单词" << endl;
        }
    }
    return 0;
}

代码示例 2：统计频率

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果"};
    map<string, int> countMap;
    
    // 用 operator[] 简化统计逻辑
    for (const auto& str : arr) {
        countMap[str]++;
    }
    
    for (const auto& e : countMap) {
        cout << e.first << ":" << e.second << endl;
    }
    return 0;
}

multimap 容器

介绍

std::multimap 允许键冗余，适合存'一对多'的映射关系。

区别

• map：键唯一，每个键对应唯一的映射关系。
• multimap：键可重复，同一个键能记多个解释。

注意：multimap 不支持 operator[]，因为键可冗余的场景下无法明确指定修改哪一个键对应的值。

OJ 练习

set 应用

349. 两个数组的交集

思路：利用 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;
    }
};

142. 环形链表 II

思路：使用 set 存储访问过的节点，若插入失败则说明有环。

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

map 应用

138. 随机链表的复制

思路：使用 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 == nullptr) {
                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 == nullptr) {
                copy->random = nullptr;
            } else {
                copy->random = m[curr->random];
            }
            curr = curr->next;
            copy = copy->next;
        }
        return copyHead;
    }
};

692. 前 K 个高频单词

方法一：基于 stable_sort 排序

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
            return x.second > y.second;
        }
    };
    
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        for (auto& e : words) {
            m[e]++;
        }
        vector<pair<string, int>> v(m.begin(), m.end());
        stable_sort(v.begin(), v.end(), Compare());
        vector<string> ret;
        for (int i = 0; i < k; i++) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

方法二：基于 sort 排序

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
            return x.second > y.second || (x.second == y.second && x.first < y.first);
        }
    };
    
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        for (auto& e : words) {
            m[e]++;
        }
        vector<pair<string, int>> v(m.begin(), m.end());
        sort(v.begin(), v.end(), Compare());
        vector<string> ret;
        for (int i = 0; i < k; i++) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

方法三：基于 priority_queue 大顶堆

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
            return x.second < y.second || (x.second == y.second && x.first > y.first);
        }
    };
    
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        for (auto& e : words) {
            m[e]++;
        }
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(m.begin(), m.end());
        vector<string> ret;
        for (int i = 0; i < k; i++) {
            ret.push_back(p.top().first);
            p.pop();
        }
        return ret;
    }
};