set 有序集合

读完能做什么

• 能创建 set，用 insert 加入元素，并说出为什么重复插入不会改变容器。
• 能遍历 set，并解释输出为什么总是从小到大，和插入的先后无关。
• 能用 find、count 查询元素（查询不会往容器里添加数据），用 erase 删除元素，并分清按值删除和按迭代器删除的区别。
• 能说出 multiset 和 set 的差别，判断什么时候该用哪一个。

为什么需要它

有三个常见的需求，用数组处理都很别扭。

需求一：快速判断“某个值之前出现过吗”。 用数组保存见过的数，每次判断都得从头扫一遍，数据一多就慢。

需求二：保存一组“不重复的数”，还要能从小到大输出。 用数组得先读进来，再 sort 排序，再用 unique 去重、erase 收缩——三步都要自己写（见 unique 去重）。

需求三：一边加入新数据，一边保持有序且不重复。 用数组每插一个数都可能要搬动一大片元素。

我们希望有一个容器，加进去的时候顺手去重、顺手排好序，查询、删除都快。这就是 set。

它是什么

一句话：set 是标准库提供的关联容器，它保存一组不重复的元素，并按比较规则自动保持有序。

关联容器与键。 关联容器用**键（key）**来组织数据，而不是像 vector 那样用连续的下标。set 的元素本身就是键：一个值要么在集合里，要么不在。

比较规则决定顺序。 默认的比较规则是 <（写作 less<T>），所以 set<int> 的元素按从小到大排列，set<string> 按字典序排列。想换顺序可以在创建时传入别的规则，见比较规则与函数对象。

有序不等于插入顺序。 这是最容易误解的一点：set 的顺序由比较规则决定，不是你插入的先后。依次插入 3、1、2，遍历出来是 1 2 3，不是 3 1 2。

自动去重。 一个值在 set 里最多出现一次。对已经存在的值再 insert 一次，容器内容不变。

元素是常量。 set 里的元素不能直接改写。因为元素的位置由它自己的值决定，改了值就可能破坏有序性。要“改”一个元素，只能先删掉旧的、再插入新的。

复杂度 O(log n)。 插入、删除、查询都是 O(log n)，n 是元素个数。这意味着数据量翻倍，比较次数只多一次左右，比数组的线性扫描（O(n)）快很多。

适用场景：需要“快速判断某个值是否存在”“保存一组去重且有序的数据”。使用时要 #include <set>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

选读。 set 内部通常用平衡二叉搜索树（红黑树）实现，这正是它能“边插入边有序、查找还很快”的原因。不了解树的结构也能正常使用 set。

最小可运行示例

下面的数据写在代码里，不需要输入。依次插入 3、1、3、2，其中 3 插了两次：

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(3);            // 3 已经在集合里，这次插入不会改变容器
    s.insert(2);

    cout << "size = " << s.size() << '\n';
    cout << "遍历：";
    for (int x : s) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

size = 3
遍历：1 2 3 

逐行看：

• set<int> s; 创建一个空的 set<int>，尖括号里的 <int> 表示每个元素是整数。
• 四次 insert 一共插入了 4 次，但第二次插入 3 时它已经在里面了，所以 size() 是 3，不是 4。
• for (int x : s) 是范围 for，从前往后取出每个元素。输出是 1 2 3，说明元素被自动排成了升序，而且重复的 3 只保留了一个。

一步步看变化

沿同一组数据 3 1 3 2 走一遍，每一步都打印容器内容和大小：

#include <bits/stdc++.h>
using namespace std;

void show(const set<int>& s) {
    cout << "size = " << s.size() << "，内容：";
    for (int x : s) cout << x << ' ';
    cout << '\n';
}

int main() {
    set<int> s;
    cout << "初始：";           show(s);
    s.insert(3); cout << "insert(3)："; show(s);
    s.insert(1); cout << "insert(1)："; show(s);
    s.insert(3); cout << "insert(3)："; show(s);
    s.insert(2); cout << "insert(2)："; show(s);
    return 0;
}

输出：

初始：size = 0，内容：
insert(3)：size = 1，内容：3 
insert(1)：size = 2，内容：1 3 
insert(3)：size = 2，内容：1 3 
insert(2)：size = 3，内容：1 2 3 

把每一步和输出对应起来：

• 第 2 步插入 1 之后，输出是 1 3 而不是 3 1：1 比 3 小，被放到了前面。
• 第 3 步再插一次 3，输出和上一步完全一样，size() 也没变——这就是去重。
• 第 4 步插入 2，它落在 1 和 3 中间，输出变成 1 2 3。

逐项扩展核心操作

查询：find 与 count

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s = {3, 1, 2};     // 用列表初始化：元素会自动排序并去重

    cout << "查 3：count = " << s.count(3)
         << "，find 命中 = " << (s.find(3) != s.end()) << '\n';
    cout << "查 5：count = " << s.count(5)
         << "，find 命中 = " << (s.find(5) != s.end()) << '\n';
    cout << "两次查询后 size = " << s.size() << '\n';
    return 0;
}

输出：

查 3：count = 1，find 命中 = 1
查 5：count = 0，find 命中 = 0
两次查询后 size = 3

• s = {3, 1, 2} 用列表初始化，结果同样是排好序的 1 2 3。
• 查 3 时 count 是 1，find(3) != s.end() 是 1（真），说明找到了。
• 查 5 时 count 是 0，find 返回 s.end()，所以比较结果是 0（假）。
• 关键：两次查询之后 size() 还是 3。 查询只是“看一眼”，不会把查的值加进容器——这一点和 map 的下标很不一样（见 map 键值映射）。

要取出找到的元素，用 *it；对 set 来说，这个值就是查询的键本身：

auto it = s.find(3);        // 片段：找到 3 的位置
if (it != s.end()) cout << *it;   // 输出 3

删除：erase

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s = {3, 1, 2};
    cout << "删除前：";
    for (int x : s) cout << x << ' ';
    cout << "size = " << s.size() << '\n';

    s.erase(2);                 // 按键删除
    cout << "erase(2) 后：";
    for (int x : s) cout << x << ' ';
    cout << "size = " << s.size() << '\n';

    auto it = s.find(3);        // 先找到位置
    s.erase(it);                // 再按迭代器删除
    cout << "erase(find(3)) 后：";
    for (int x : s) cout << x << ' ';
    cout << "size = " << s.size() << '\n';
    return 0;
}

输出：

删除前：1 2 3 size = 3
erase(2) 后：1 3 size = 2
erase(find(3)) 后：1 size = 1

erase 有两个版本，作用范围不同：

在 set 里每个值只有一个，两种写法删的都是同一个元素。但在 multiset 里差别很大，下面马上会看到。

对比 multiset：允许重复

multiset 是“允许重复的 set”，同样自动排序，但同一个值可以出现多次：

#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> ms;
    ms.insert(3);
    ms.insert(1);
    ms.insert(3);
    ms.insert(2);

    cout << "multiset 遍历：";
    for (int x : ms) cout << x << ' ';
    cout << "size = " << ms.size() << '\n';
    cout << "count(3) = " << ms.count(3) << '\n';

    ms.erase(3);                // 按键删除：删掉该键的全部元素
    cout << "erase(3) 后：";
    for (int x : ms) cout << x << ' ';
    cout << "size = " << ms.size() << '\n';

    ms.insert(3);
    ms.insert(3);
    cout << "重新插入两个 3 后：";
    for (int x : ms) cout << x << ' ';
    cout << "size = " << ms.size() << '\n';

    auto it = ms.find(3);       // 只删一个 3
    ms.erase(it);
    cout << "按迭代器删一个 3 后：";
    for (int x : ms) cout << x << ' ';
    cout << "size = " << ms.size() << '\n';
    return 0;
}

输出：

multiset 遍历：1 2 3 3 size = 4
count(3) = 2
erase(3) 后：1 2 size = 2
重新插入两个 3 后：1 2 3 3 size = 4
按迭代器删一个 3 后：1 2 3 size = 3

• 插入 3 1 3 2 后遍历是 1 2 3 3：重复的 3 都保留了，而且紧挨着。
• count(3) 是 2，说明 multiset 的计数是有意义的。
• 调用 erase(3) 之后只剩 1 2，size() 从 4 掉到 2——按键删除会删掉该键的全部记录。
• 想只删一个，就要像最后一步那样先用 find(3) 定位，再 erase(it)。

综合：用 set 保存排除词

set 最典型的用途是“快速判断某个东西在不在集合里”。下面读入若干要排除的词，再读入正文，统计不在排除集合里的词有多少个：

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<string> excluded;
    string word;
    while (cin >> word && word != "stop") {   // 先读入要排除的词，stop 结束
        excluded.insert(word);
    }

    int kept = 0;
    while (cin >> word) {                     // 再读入正文
        if (excluded.count(word) == 0) {      // 不在排除集合里才算数
            kept++;
        }
    }
    cout << "未被排除的词数 = " << kept << '\n';
    return 0;
}

输入：

the a stop
the apple a banana apple

输出：

未被排除的词数 = 3

第一段读到 stop 为止，把 the、a 放进排除集合；第二段依次读入 the apple a banana apple，其中 the、a 命中排除集合被跳过，apple、banana、apple 三次没有命中，所以结果是 3。这里用固定词 stop 结束输入，不依赖终端的结束快捷键。

什么时候选它、哪里容易错

有序不等于插入顺序。 set 的顺序完全由比较规则决定。想让数据保持你插入的先后，应该用 vector；想自动排序去重，才用 set。

查询不会增添数据。 find、count 只读不写，查一个不存在的值不会把它加进去。这一点和 map 的 operator[] 相反——map["new"] 会插入一个新键（见 map 键值映射）。

erase 的两个版本要分清。 erase(x) 按键删除，在 multiset 上会删掉全部同键元素；erase(it) 按迭代器删除，只删一个。要“只删一个重复值”，必须先用 find 拿到迭代器。

元素是常量，不能改。 set 里的元素不能直接赋值修改。要修改就 erase 旧的、insert 新的。这也解释了为什么 set<int>::iterator 解引用出来的是只读的值。

复杂度 O(log n)。 插入、删除、查询都是 O(log n)，比数组线性扫描快，但比 vector 尾部操作、unordered_set（哈希表，选读）的平均 O(1) 慢。数据量不大时三者的差别可以忽略。

选读。 set 保持有序靠的是平衡二叉搜索树：每个节点比较一次就能决定往左还是往右走，所以查找只需 O(log n) 次比较。底层细节不影响日常使用。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对。注意有两次重复插入：

set<int> s;
s.insert(2);
s.insert(5);
s.insert(2);            // 重复插入
s.insert(5);            // 重复插入
s.insert(1);

cout << "size = " << s.size() << "，内容：";
for (int x : s) cout << x << ' ';
cout << '\n';

第 2 题：修改代码

下面这段片段用 multiset 保存 3 1 3 2，但 erase(3) 把两个 3 都删掉了。请改成只删一个 3，让输出变成 size = 3，内容：1 2 3 ：

multiset<int> ms = {3, 1, 3, 2};
ms.erase(3);                 // 这句会把两个 3 都删掉，请改成只删一个

cout << "size = " << ms.size() << "，内容：";
for (int x : ms) cout << x << ' ';
cout << '\n';

验证条件：先说出 erase(3) 和只删一个元素的结果分别是多少，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;
    s.insert(2);
    s.insert(5);
    s.insert(2);            // 重复插入
    s.insert(5);            // 重复插入
    s.insert(1);

    cout << "size = " << s.size() << "，内容：";
    for (int x : s) cout << x << ' ';
    cout << '\n';
    return 0;
}

size = 3，内容：1 2 5 

#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> ms = {3, 1, 3, 2};
    ms.erase(ms.find(3));   // 只删一个 3

    cout << "size = " << ms.size() << "，内容：";
    for (int x : ms) cout << x << ' ';
    cout << '\n';
    return 0;
}

size = 3，内容：1 2 3 

立即练习

两道题都只需要数组、循环和本页讲过的 set 操作。做完后请说明：这里为什么用 set 比用数组更省事？