第5章 set 系列容器详解

set系列容器是STL关联式容器的核心分支，以"元素值"为关键字，核心作用是实现高效的查找、去重，部分类型支持重复元素存储，底层实现决定了其有序/无序特性和效率，是日常开发和算法题中的高频工具。

---

🎯 本章学习目标

学完本章，你将能够：

1. 说出 set 系列四种容器的名称与核心区别
2. 理解有序（红黑树）与无序（哈希表）的底层差异
3. 掌握 set、unordered_set 的基本增删改查操作
4. 掌握 multiset、unordered_multiset 的重复元素处理
5. 理解 multiset 中 erase(值) 与 erase(迭代器) 的区别
6. 掌握四种容器的选型方法（一句话选型）
7. 理解 set 元素不可修改的原因
8. 熟练使用 set 解决去重、查找、集合类问题

---

🗺️ 本章知识图谱

set 系列容器
├── 四大容器
│   ├── set（有序、去重、红黑树）
│   ├── unordered_set（无序、去重、哈希表）
│   ├── multiset（有序、可重复、红黑树）
│   └── unordered_multiset（无序、可重复、哈希表）
├── 核心操作
│   ├── insert（插入）
│   ├── erase（删除）
│   ├── find（查找）
│   ├── count（计数）
│   └── 遍历
├── 两个维度
│   ├── 有序 vs 无序
│   └── 去重 vs 可重复
├── 底层实现
│   ├── 红黑树（set/multiset）
│   └── 哈希表（unordered_*）
├── 注意事项
│   ├── 元素不可修改
│   ├── multiset erase 坑
│   └── 头文件区分
└── 选型与场景

---

🍎 生活比喻：set 系列容器就像书架上的书——set 是按编号严格排序、每种书只有一本的书架（有序+去重）；unordered_set 是书随便放、但找起来特别快的书架（无序+去重，靠索引卡片找）；multiset 是按编号排序、同一种书可以有多本的书架（有序+可重复）；unordered_multiset 是随便放、同一种书可以有多本的书架（无序+可重复）。

在C++ STL（标准模板库）中，set系列容器是高频使用的集合类工具，核心作用是存储数据、实现快速查找与去重（部分类型支持重复）。初学者容易混淆 set、unordered_set、multiset、unordered_multiset 这四种容器。本章从定义、特性、常用操作、适用场景四个维度讲清它们的区别与用法，并配合代码示例，学完即可上手。

一、四种set容器核心特性对比

容器类型	是否有序	是否允许重复	底层实现	核心效率（插入/查找/删除）	核心优势
set	✅ 是（默认升序）	❌ 否	红黑树（平衡二叉搜索树）	O(log n)（稳定）	有序+去重，支持快速取最值
unordered_set	❌ 否	❌ 否	哈希表	O(1)（平均），最坏O(n)	查找速度极快，适合纯去重、快速查询
multiset	✅ 是（默认升序）	✅ 是	红黑树	O(log n)（稳定）	有序+允许重复，支持统计重复元素个数
unordered_multiset	❌ 否	✅ 是	哈希表	O(1)（平均），最坏O(n)	快速统计重复元素，无需排序

二、逐一详解：定义与基础用法

所有set容器的使用，需包含对应头文件，核心操作高度统一，仅细节有差异，以下代码均包含完整头文件和命名空间，可直接复制运行。

1. set：有序、不可重复集合（最基础）

set是最常用的set容器，核心作用是「有序去重」，数据插入后会自动按升序排列，且同一个元素只能存储一次。

#include <iostream>
#include <set>  // set的头文件
using namespace std;

int main() {
    // 1. 定义：默认升序，存储int类型
    set<int> s;
    
    // 2. 插入元素（重复插入会自动忽略）
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(1);  // 重复元素，插入无效
    
    // 3. 遍历（自动升序）
    cout << "set遍历（升序）：";
    for (auto x : s) {  // 范围for遍历（C++11及以上）
        cout << x << " ";
    }
    cout << endl;  // 输出：1 2 3
    
    // 4. 查找元素
    if (s.count(2)) {  // count()：存在返回1，不存在返回0
        cout << "元素2存在" << endl;
    }
    
    // 5. 取最值（利用有序特性）
    cout << "set最小值：" << *s.begin() << endl;  // begin()指向最小元素
    cout << "set最大值：" << *s.rbegin() << endl; // rbegin()指向最大元素
    
    // 6. 删除元素
    s.erase(2);  // 删除值为2的元素
    cout << "删除2后遍历：";
    for (auto x : s) {
        cout << x << " ";
    }
    cout << endl;  // 输出：1 3
    
    // 7. 其他常用操作
    cout << "元素个数：" << s.size() << endl;  // 输出：2
    if (s.empty()) {
        cout << "集合为空" << endl;
    } else {
        cout << "集合非空" << endl;
    }
    s.clear();  // 清空集合
    return 0;
}

补充：降序排列

若需要「降序排列」，定义时可指定排序规则：

set<int, greater<int>> s;  // 降序排列
s.insert(3);
s.insert(1);
s.insert(2);
// 遍历输出：3 2 1

2. unordered_set：无序、不可重复集合（最快查找）

unordered_set与set的最直观（核心）的区别是「无序」（底层基于哈希表实现，查找、插入、删除的平均效率远高于 set）；但二者差异不止于有序性——unordered_set 是前向迭代器（set 是双向迭代器，故前者不支持 --/逆序遍历）、无 lower_bound/upper_bound 等范围查询接口、rehash 会使迭代器失效、内存开销与最坏复杂度也不同。

#include<iostream>
#include <unordered_set>  // unordered_set的头文件
using namespace std;

int main() {
    // 1. 定义：无序，存储string类型
    unordered_set<string> us;
    
    // 2. 插入元素（重复无效）
    us.insert("apple");
    us.insert("banana");
    us.insert("orange");
    us.insert("apple");  // 重复插入，无效
    
    // 3. 遍历（无序，每次运行顺序可能不同）
    cout << "unordered_set遍历（无序）：";
    for (auto str : us) {
        cout << str << " ";
    }
    cout << endl;  // 示例输出：banana apple orange（顺序不固定）
    
    // 4. 查找元素（效率比set高）
    if (us.find("orange") != us.end()) {  // find()返回迭代器，找不到返回end()
        cout << "元素orange存在" << endl;
    }
    
    // 5. 删除元素
    us.erase("banana");  // 删除值为banana的元素
    
    // 6. 其他常用操作（与set一致）
    cout << "元素个数：" << us.size() << endl;  // 输出：2
    us.clear();  // 清空
    return 0;
}

关键提醒

unordered_set不支持排序相关操作（如取最值），因为其元素是无序的，若需要排序，需先将元素存入vector再排序。

3. multiset：有序、可重复集合（统计重复）

multiset与set的核心区别是「允许重复元素」，底层同样是红黑树，插入后自动排序，支持统计重复元素的个数，是算法题中常用的“有序可重复”容器（可替代优先队列的部分场景）。

#include <iostream>
#include <set>  // multiset与set共用头文件
using namespace std;

int main() {
    // 1. 定义：有序，允许重复，存储int类型
    multiset<int> ms;
    
    // 2. 插入元素（允许重复）
    ms.insert(5);
    ms.insert(5);
    ms.insert(3);
    ms.insert(5);
    ms.insert(2);
    
    // 3. 遍历（自动升序，保留重复元素）
    cout << "multiset遍历：";
    for (auto x : ms) {
        cout << x << " ";
    }
    cout << endl;  // 输出：2 3 5 5 5
    
    // 4. 统计重复元素个数
    cout << "元素5的重复次数：" << ms.count(5) << endl;  // 输出：3
    
    // 5. 删除元素（重点！容易踩坑）
    ms.erase(5);  // 注意：删除所有值为5的元素
    cout << "删除所有5后遍历：";
    for (auto x : ms) {
        cout << x << " ";
    }
    cout << endl;  // 输出：2 3
    
    // 重新插入5，演示“只删除一个5”
    ms.insert(5);
    ms.insert(5);
    ms.erase(ms.find(5));  // 用迭代器删除，只删一个5
    cout << "只删除一个5后遍历：";
    for (auto x : ms) {
        cout << x << " ";
    }
    cout << endl;  // 输出：2 3 5
    
    // 6. 取最值（与set一致，利用有序特性）
    cout << "multiset最小值：" << *ms.begin() << endl;  // 输出：2
    return 0;
}

踩坑提醒

multiset的erase()有两种用法——删除值时，会删除所有该值的元素；删除迭代器时，只删除迭代器指向的那一个元素，这是最容易出错的点。

4. unordered_multiset：无序、可重复集合（快速统计）

unordered_multiset与multiset的区别是「无序」，底层基于哈希表实现，允许重复元素，查找、插入的平均效率极高，适合不需要排序、只需要快速统计重复元素的场景。

#include <iostream>
#include <unordered_set>  // 与unordered_set共用头文件
using namespace std;

int main() {
    // 1. 定义：无序，允许重复，存储int类型
    unordered_multiset<int> ums;
    
    // 2. 插入元素（允许重复）
    ums.insert(2);
    ums.insert(2);
    ums.insert(7);
    ums.insert(2);
    ums.insert(9);
    
    // 3. 遍历（无序，保留重复元素）
    cout << "unordered_multiset遍历：";
    for (auto x : ums) {
        cout << x << " ";
    }
    cout << endl;  // 示例输出：2 2 2 7 9（顺序不固定）
    
    // 4. 统计重复元素个数（与multiset一致）
    cout << "元素2的重复次数：" << ums.count(2) << endl;  // 输出：3
    
    // 5. 删除元素（与multiset一致，注意坑点）
    ums.erase(2);  // 删除所有值为2的元素
    cout << "删除所有2后遍历：";
    for (auto x : ums) {
        cout << x << " ";
    }
    cout << endl;  // 输出：7 9
    
    // 6. 其他常用操作（与unordered_set一致）
    cout << "元素个数：" << ums.size() << endl;  // 输出：2
    ums.clear();  // 清空
    return 0;
}

三、常用操作汇总（四种容器通用+差异）

四种set容器的常用操作高度统一，以下汇总核心操作，重点标注差异点，方便快速查阅。

3.1 通用操作（四种容器都支持）

操作	语法	说明
插入	insert(元素)	插入一个元素，set/unordered_set重复插入无效；multiset/ums允许重复插入
删除（按值）	erase(元素)	删除所有值为该元素的节点（multiset/ums需注意，会删全部）
删除（按迭代器）	erase(迭代器)	删除迭代器指向的单个元素，四种容器均适用
查找	find(元素)	返回指向该元素的迭代器，找不到返回end()
统计个数	count(元素)	返回该元素的个数，set/unordered_set只能返回0或1
清空	clear()	清空所有元素，容器变为空
判空	empty()	为空返回true，否则返回false
获取大小	size()	返回容器中元素的个数

3.2 差异操作（仅部分容器支持）

• 「取最值」：仅set、multiset支持（因为有序），用 *(begin()) 取最小值，*(rbegin()) 取最大值；unordered_set、unordered_multiset不支持。
• 「排序」：仅set、multiset支持自动排序，unordered系列容器无序，无法直接排序。
• 「自定义排序」：仅set、multiset支持，定义时指定排序规则（如降序）；unordered系列容器不支持。

四、适用场景总结（一句话选型）

很多初学者纠结“该用哪种set”，记住以下4句话，直接选型，无需犹豫：

1. 需要「有序+去重」→ 用 set（比如需要排序的去重场景、取最值场景）；
2. 需要「快速查找+去重」，不在乎顺序 → 用 unordered_set（比如查重、快速判断元素是否存在，效率最优）；
3. 需要「有序+允许重复」→ 用 multiset（比如统计重复元素、需要有序遍历重复数据，算法题高频）；
4. 需要「快速统计重复元素」，不在乎顺序 → 用 unordered_multiset（比如统计一个数组中每个元素的出现次数，效率比multiset高）。

五、常见误区与注意事项

5.1 误区1：混淆erase()的用法

对于multiset和unordered_multiset，erase(元素) 会删除所有该值的元素，而不是一个！如果只想删除一个，必须用迭代器（如 erase(find(元素))）。

5.2 误区2：认为unordered系列容器效率一定更高

unordered系列的平均效率是O(1)，但最坏情况（哈希冲突严重）会退化到O(n)；而set、multiset的效率稳定在O(log n)，适合数据量较大、哈希冲突可能严重的场景。

5.3 误区3：试图修改set容器中的元素

所有set容器的元素都是「不可修改」的！因为修改元素会破坏其底层排序（红黑树）或哈希结构（哈希表）。如果需要修改元素，只能先删除旧元素，再插入新元素。

5.4 注意事项：头文件区分

• set、multiset：包含 <set> 头文件；
• unordered_set、unordered_multiset：包含 <unordered_set> 头文件。

六、实战案例：四种容器对比演示

以下代码将四种容器放在一起，插入相同的元素，演示它们的遍历顺序、重复处理、查找效率差异，帮助你直观感受区别（可直接复制运行）。

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

int main() {
    // 定义四种容器
    set<int> s;
    unordered_set<int> us;
    multiset<int> ms;
    unordered_multiset<int> ums;
    
    // 插入相同的元素
    int arr[] = {3, 1, 2, 3, 4, 1, 5};
    for (int x : arr) {
        s.insert(x);
        us.insert(x);
        ms.insert(x);
        ums.insert(x);
    }
    
    // 遍历对比
    cout << "1. set遍历（有序、去重）：";
    for (auto x : s) cout << x << " ";
    cout << endl;
    
    cout << "2. unordered_set遍历（无序、去重）：";
    for (auto x : us) cout << x << " ";
    cout << endl;
    
    cout << "3. multiset遍历（有序、可重复）：";
    for (auto x : ms) cout << x << " ";
    cout << endl;
    
    cout << "4. unordered_multiset遍历（无序、可重复）：";
    for (auto x : ums) cout << x << " ";
    cout << endl;
    
    // 查找对比（以元素3为例）
    cout << "\n元素3的个数：" << endl;
    cout << "set：" << s.count(3) << endl;
    cout << "unordered_set：" << us.count(3) << endl;
    cout << "multiset：" << ms.count(3) << endl;
    cout << "unordered_multiset：" << ums.count(3) << endl;
    
    return 0;
}

运行结果示例：

1. set遍历（有序、去重）：1 2 3 4 5 
2. unordered_set遍历（无序、去重）：3 1 2 4 5 
3. multiset遍历（有序、可重复）：1 1 2 3 3 4 5 
4. unordered_multiset遍历（无序、可重复）：3 3 1 1 2 4 5 

元素3的个数：
set：1
unordered_set：1
multiset：2
unordered_multiset：2

七、🔖 本章小结

set系列容器的核心价值的是「高效的查找、去重、排序」，四种容器的差异本质是「有序与否」和「允许重复与否」，底层实现决定了它们的效率和适用场景。

掌握它们的关键的是：记住特性对比表，明确自己的需求（是否需要有序、是否允许重复、是否追求极致查找效率），再对应选型。日常开发中，set和unordered_set使用频率最高；算法题中，multiset是高频工具，常用于处理有序重复数据。

掌握本章内容，即可彻底分清四种 set 容器，摆脱选型困惑，在编程中灵活运用。

---

八、📝 实战练习

练习题 1（选择题）

题目： set 的底层数据结构是？

A. 哈希表 B. 红黑树 C. 双向链表 D. 二叉堆

🔑 点击查看答案与解析

答案： B

**解析：**set 和 multiset 底层都是红黑树（一种平衡二叉搜索树），所以元素是有序的，插入查找删除都是 O(log n)。A 是 unordered_set 的底层结构，C 是 list 的底层结构，D 是 priority_queue 的底层结构。

---

练习题 2（判断题）

题目： unordered_set 中的元素是按升序排列的（ ）

🔑 点击查看答案与解析

答案： 错误

**解析：**unordered_set 底层是哈希表，元素是无序的，遍历顺序不固定。set 和 multiset 才是有序的（底层红黑树）。

---

练习题 3（选择题）

题目： 以下哪种容器允许存储重复的元素？

A. set B. unordered_set C. multiset D. 以上都不允许

🔑 点击查看答案与解析

答案： C

**解析：**set 和 unordered_set 都是去重的，不允许重复元素。multiset 和 unordered_multiset 允许重复元素。

---

练习题 4（选择题）

题目： 关于 multiset 的 erase 操作，以下说法正确的是？

A. ms.erase(5) 只删除一个值为 5 的元素 B. ms.erase(5) 删除所有值为 5 的元素 C. ms.erase(ms.find(5)) 删除所有值为 5 的元素 D. multiset 不支持 erase 操作

🔑 点击查看答案与解析

答案： B

**解析：**这是 multiset 最容易踩的坑！

• erase(值) 会删除所有等于该值的元素
• erase(迭代器) 只删除迭代器指向的一个元素

所以如果只想删除一个 5，应该用 ms.erase(ms.find(5))。

---

练习题 5（判断题）

题目： set 中的元素可以直接通过迭代器修改（ ）

🔑 点击查看答案与解析

答案： 错误

**解析：**set 的元素是 const 的，不能直接修改。因为元素值就是排序的依据（key），修改元素会破坏红黑树的结构。如果需要修改，只能先删除旧元素，再插入新元素。

---

练习题 6（程序阅读题）

题目： 阅读以下代码，写出输出结果：

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

int main() {
    set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(1);
    s.insert(5);
    s.insert(9);
    s.erase(3);
    
    cout << s.size() << " " << *s.begin() << " " << *s.rbegin() << endl;
    return 0;
}

🔑 点击查看答案与解析

答案： 4 1 9

解析：

• insert(3) →
• insert(1) →
• insert(4) →
• insert(1) → {1, 3, 4}（重复，忽略）
• insert(5) →
• insert(9) →
• erase(3) →

size() = 4，*begin() = 1，*rbegin() = 9

---

练习题 7（编程题）

题目： 输入 n 个整数，统计其中不同数字的个数（去重计数）。

**输入格式：**第一行一个整数 n，第二行 n 个整数 **输出格式：**一个整数，表示不同数字的个数

样例输入：

7
1 2 3 2 1 4 3

样例输出：

4

🔑 点击查看答案与解析

参考代码：

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

int main() {
    int n;
    cin >> n;
    set<int> s;
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);  // set 自动去重
    }
    
    cout << s.size() << endl;  // size 就是不同元素的个数
    return 0;
}

**解析：**这是 set 最经典的应用——去重计数。利用 set 自动去重的特性，把所有元素插入 set 后，size() 就是不同元素的个数。代码非常简洁。

也可以用 unordered_set 来做，平均效率更高（O(1) 插入），但最坏情况是 O(n)。一般情况下 set 就够用了。

---

练习题 8（编程题）

题目： 输入 n 个整数，使用 multiset 统计每个数字出现的次数，然后按从小到大的顺序输出每个数字及其出现次数。

**输入格式：**第一行一个整数 n，第二行 n 个整数 **输出格式：**多行，每行一个数字和它的出现次数，按数字升序排列

样例输入：

8
1 3 2 3 1 3 2 1

样例输出：

1 3
2 2
3 3

🔑 点击查看答案与解析

参考代码（方法一：用 multiset + count）：

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

int main() {
    int n;
    cin >> n;
    multiset<int> ms;
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ms.insert(x);
    }
    
    // 遍历输出，注意去重输出 key
    int prev = 0;
    bool first = true;
    for (int x : ms) {
        if (first || x != prev) {
            if (!first) cout << endl;
            cout << x << " " << ms.count(x);
            prev = x;
            first = false;
        }
    }
    cout << endl;
    
    return 0;
}

参考代码（方法二：用 set 存 key + multiset 统计，更高效）：

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

int main() {
    int n;
    cin >> n;
    set<int> s;       // 存不同的 key
    multiset<int> ms; // 存所有元素用于计数
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
        ms.insert(x);
    }
    
    // 用 set 遍历 key，用 multiset 统计次数
    for (int x : s) {
        cout << x << " " << ms.count(x) << endl;
    }
    
    return 0;
}

解析：

• 方法一：只用一个 multiset，遍历时遇到新的 key 就输出 count。缺点是重复的 key 会多次调用 count，效率稍低。
• 方法二：用 set 存所有不同的 key（去重），用 multiset 存所有元素，然后遍历 set 的 key，在 multiset 中 count。逻辑更清晰。

注意：multiset 的 count 是 O(k + log n) 的（k 是该元素出现次数），因为要在红黑树中找到第一个再往后数。

这道题其实用 map 做更合适（key 是数字，value 是次数），但这里练习 multiset 的用法。

---

九、📊 考点总结表

知识点	重要程度	出题形式	易错点
set 底层是红黑树	⭐⭐⭐⭐⭐	选择题、判断题	与哈希表混淆
unordered_set 底层是哈希表	⭐⭐⭐⭐	选择题	与红黑树混淆
set 元素有序、自动去重	⭐⭐⭐⭐⭐	选择题、判断题	以为无序或可重复
multiset 允许重复	⭐⭐⭐⭐	选择题	与 set 混淆
multiset erase(值) 删全部	⭐⭐⭐⭐⭐	选择题、编程题	以为只删一个
元素不可修改	⭐⭐⭐⭐	选择题、判断题	以为可以改
四种容器选型	⭐⭐⭐⭐⭐	选择题、简答题	四种区别记不清
头文件区分（set vs unordered_set）	⭐⭐⭐	选择题、判断题	头文件记错
插入查找删除 O(log n) / O(1)	⭐⭐⭐⭐	选择题	时间复杂度记混
begin() 最小、rbegin() 最大	⭐⭐⭐⭐	选择题、编程题	搞反最值

---

⭐ 必背速记卡

┌──────────────────────────────────────┐
│  set 系列必背速记卡                   │
├──────────────────────────────────────┤
│  1. set/multiset 底层红黑树，有序     │
│  2. unordered_* 底层哈希表，无序     │
│  3. set/unordered_set 自动去重       │
│  4. multiset/ums 允许重复元素        │
│  5. 插入查找删除：树 O(log n)、哈希 O(1)│
│  6. 元素不可修改，只能删了再插         │
│  7. multiset erase(值) 删全部！       │
│  8. 删一个要用 erase(find(值))        │
│  9. begin 最小 rbegin 最大（有序版）   │
│  10. 头文件：<set> 和 <unordered_set> │
└──────────────────────────────────────┘