STL——集合 set

stl的容器较多，开始学习的时候主要聚焦于常用的，最近发现set其实也有很多实用的方法
set 家族主要有set, multiset, unordered_set, unordered_multiset

前置通用知识

1. 关联式容器：不以 “下标” 访问元素，而是通过 “元素值” 建立映射，核心操作是按值查找、插入、删除；
2. 元素可修改性：所有 set 家族容器的元素都不可直接修改！因为有序容器依赖值维护红黑树结构，无序容器依赖值维护哈希表，直接修改会破坏底层结构，修改元素的唯一方式是先删除旧值，再插入新值；

一、set（有序，唯一）

核心特性

1. 元素严格唯一：插入重复元素时，容器会自动忽略，无报错、无新增；
2. 自动升序排列：默认使用less<T>比较器，也可自定义降序 / 自定义排序规则；
3. 底层红黑树：操作时间复杂度稳定O (logn)，迭代器遍历为有序序列；
4. 元素不可直接修改：需 “删旧插新”。

常用函数

set<int>s;// 默认升序set<int,greater<int>>s;// 降序// 插入：insert()s.insert(val)// 返回值是pair<iterator, bool>// 能直接判断是否插入成功（是否为重复元素），这是和multiset的核心区别之一。// 删除：erase()s.erase(2);// 按值删s.erase(it);// 用法按迭代器删s.erase(s.begin(),s.end());// 删区间[it1, it2)// 查找：find(val)：找到返回迭代器，无则返回s.end()it=s.find(3);// 指向3it=s.find(4);// 无4，返回s.end()// 统计：count(val)：返回0/1（因元素唯一，仅表示是否存在）intcnt=s.count(3);// 1（存在）cnt=s.count(4);// 0（不存在）// 查找：lower_bound/upper_bound（有序容器通用）s.insert({1,2,3});it=s.lower_bound(2);// 第一个≥2的迭代器 → 指向2it=s.upper_bound(2);// 第一个>2的迭代器 → 指向3// 基础操作s.empty();// 判断是否为空s.size();// 元素个数s.clear();// 清空容器s.begin();// 首元素迭代器s.end();// 末尾迭代器（最后一个元素下一位）s.rbegin();// 反向首元素（降序第一个）s.rend();// 反向末尾

二、multiset（有序, 可重复）

核心特性

1. 元素可重复：支持插入多个相同值的元素，重复元素会相邻存放；
2. 自动升序排列：和set一致，默认less<T>，可自定义比较器；
3. 底层红黑树：操作时间复杂度稳定O (logn)，遍历为有序序列；
4. 元素不可直接修改：需 “删旧插新”；
5. 与set的唯一差异：允许重复元素，因此插入 / 删除 / 查找 / 统计的函数行为略有调整（无其他新函数）。

常用函数

multiset<int>ms;ms.insert({2,1,2,2,3});// 升序可重复：{1,2,2,2,3}// 插入：insert(val) → 仅返回迭代器（无bool值，因重复插入也成功）autoit=ms.insert(2);// 指向新插入的2// 删除：erase() 三种用法（与set的唯一区别）ms.erase(2);// 用法1：按值删：删除所有的2ms.insert({2,2,2});// 恢复：{1,2,2,2,3}it=ms.find(2);ms.erase(it);// 用法2：按迭代器删：仅删除单个2，ms={1,2,2,3}ms.erase(ms.find(2),ms.end());// 用法3：删区间 → 删从第一个2到末尾，ms={1}// 3. 统计：count(val) → 返回重复元素的个数（O(logn + k)，k为重复数）ms.insert({2,2,2,3});intcnt=ms.count(2);// 3（有3个2）cnt=ms.count(4);// 0// 4. 查找：find(val) → 返回第一个等于val的迭代器（其余同set）it=ms.find(2);// 指向第一个2// 5. 边界查找：lower_bound/upper_bound → 同set，用于获取重复元素的区间it=ms.lower_bound(2);// 第一个≥2 → 第一个2it=ms.upper_bound(2);// 第一个>2 → 3// 结合两者遍历所有2：[lower_bound(2), upper_bound(2))for(autoi=ms.lower_bound(2);i!=ms.upper_bound(2);++i){cout<<*i<<" ";// 输出：2 2 2}// 基础操作（empty/size/clear等）与set完全一致

set 与 multiset 差异

仅因 “元素是否可重复” 导致的 4 点差异，其余完全一致：

前置知识

无序 set 系列的unordered_set和unordered_multiset底层均基于哈希表实现，因此无自动排序特性，元素按哈希值散列存储（遍历顺序不可预测）, 但插入、删除、查找的平均时间复杂度为 O (1)，最坏时间复杂度 O (n)。

三、unordered_set（无序, 唯一）

核心特性

1. 元素严格唯一：插入重复元素自动忽略，无报错；
2. 无序存储：按哈希值散列，遍历顺序与插入顺序无关，不可预测；
3. 底层哈希表：平均 O (1) 操作，最坏 O (n)；无反向迭代器（仅前向迭代器）；
4. 元素不可直接修改：需 “删旧插新”；
5. 不支持自定义排序：因底层无排序结构，仅能通过哈希值散列。

注意：无序 set 无第二个模板参数（无比较器），因为不需要排序，仅需哈希函数和 == 判断。

常用函数

函数名和用法几乎与 set 完全一致，差异仅在于：无反向迭代器（无 rbegin/rend）、遍历无序，因元素唯一，count/erase/find行为与 set 一致：

unordered_set<int>us;us.insert({3,1,2,2});// 去重，无序：如{1,3,2}（遍历顺序不可预测）// 1. 插入：insert(val) → 返回pair<迭代器, bool>（同set，标记是否插入成功）autores=us.insert(2);// false，重复// 2. 删除：erase(val)/erase(迭代器)/erase(区间) → 同set（因元素唯一）us.erase(2);// 删唯一的2，us={1,3}// 3. 查找：find(val) → 同set，找到返回迭代器，无则返回end()autoit=us.find(3);// 4. 统计：count(val) → 返回0/1（同set）intcnt=us.count(1);// 1// 5. 基础操作：empty/size/clear/begin/end 均有，无rbegin/rend// 遍历：范围for（无序）for(intx:us)cout<<x<<" ";// 如1 3（顺序不可预测）

关键差异：无lower_bound/upper_bound函数！因为无序容器没有 “顺序”，区间边界查找无意义，这是有序和无序 set 系列的核心函数差异。

四、unordered_multiset（无序，元素可重复）

核心特性

1. 元素可重复：支持插入多个相同值的元素，重复元素散列到同一个哈希桶；
2. 无序存储：按哈希值散列，遍历顺序不可预测，重复元素通常相邻；
3. 底层哈希表：平均 O (1) 操作，最坏 O (n)；仅前向迭代器，无反向迭代器；
4. 元素不可直接修改：需 “删旧插新”；
5. 无自定义排序，无lower_bound/upper_bound函数。

unordered_set 与 unordered_multiset 差异

与有序系列的差异逻辑完全一致，仅因 “元素是否可重复” 导致 3 点差异：

典型适用场景

1. set：有序去重场景（如去重并排序的成绩、唯一的 ID 集合）；
2. multiset：有序可重复场景（如允许同分的成绩排名、统计元素频率）；
3. unordered_set：高效无序去重场景（如快速判断元素是否存在、缓存唯一键）；
4. unordered_multiset：高效无序可重复场景（如快速统计元素出现次数、无需排序的重复数据存储）。

使用特点

核心坑点

1. 直接修改元素：所有 set 家族的元素均不可直接修改，强行修改会导致底层结构破坏，程序崩溃 / 逻辑错误；正确方式是先删除旧值，再插入新值；

2. multiset/umultiset 的 erase (val)：按值删除会删掉所有重复元素，仅删单个必须用erase(迭代器)；

3. 无序 set 的排序误区：unordered_* 系列无法排序，若需先高效操作再排序，可将元素拷贝到 vector 后用sort排序；

4. 迭代器失效 ：

   • 有序 set（红黑树）：删除元素仅导致被删元素的迭代器失效，其余迭代器均有效；
   • 无序 set（哈希表）：插入 / 删除元素可能导致哈希表扩容 / 重散列，所有迭代器失效（需重新查找）。

使用技巧

1. 统计元素频率：优先用multiset/unordered_multiset的count(val)，替代map<T, int>（无需手动维护计数）；
2. 有序区间查询：用set/multiset的lower_bound/upper_bound快速获取 [L, R) 区间的元素；
3. 高效去重：无需排序时用unordered_setO (1)，需要排序时用setO (logn)，均比vector+sort+unique更适合动态增删的场景；
4. 避免频繁遍历无序 set：遍历顺序不可预测，若需遍历后排序，建议拷贝到 vector 再处理。

总结

C++ STL 的 set 家族四大类型围绕“有序 / 无序”和“唯一 / 可重复”两个维度划分，底层对应红黑树和哈希表两种经典数据结构，核心要点可归纳为 3 句话：

1. 有序选红黑树（set/multiset），稳定 O (logn)，支持排序和区间查询，自定义类型仅需重载 <；
2. 无序选哈希表（unordered_*），平均 O (1)，效率更高，自定义类型需重载 ==+ 哈希函数；
3. 唯一选不带 multi 的，可重复选带 multi 的，multi 的核心坑是erase(val)删所有重复元素。

本篇主要内容由AI总结，在此基础上我进行了修改。主要有些f i n d findfind、c o u n t countcount、e r a s e eraseerase等函数在特定场景下的效率较高，优于v e c t o r vectorvector。