核心内容摘要
红桃国际：链接世界，共筑非凡
stl的容器较多开始学习的时候主要聚焦于常用的最近发现set其实也有很多实用的方法set 家族主要有set, multiset, unordered_set, unordered_multiset前置通用知识关联式容器不以 “下标” 访问元素而是通过 “元素值” 建立映射核心操作是按值查找、插入、删除元素可修改性所有 set 家族容器的元素都不可直接修改因为有序容器依赖值维护红黑树结构无序容器依赖值维护哈希表直接修改会破坏底层结构修改元素的唯一方式是先删除旧值再插入新值
set有序唯一核心特性元素严格唯一插入重复元素时容器会自动忽略无报错、无新增自动升序排列默认使用lessT比较器也可自定义降序 / 自定义排序规则底层红黑树操作时间复杂度稳定O (logn)迭代器遍历为有序序列元素不可直接修改需 “删旧插新”。
常用函数setints;// 默认升序setint,greaterints;// 降序// 插入insert()s.insert(val)// 返回值是pairiterator, bool// 能直接判断是否插入成功是否为重复元素这是和multiset的核心区别之一。
// 删除erase()s.erase(
;// 按值删s.erase(it);// 用法按迭代器删s.erase(s.begin(),s.end());// 删区间[it1, it
// 查找find(val)找到返回迭代器无则返回s.end()its.find(
;// 指向3its.find(
;// 无4返回s.end()// 统计count(val)返回0/1因元素唯一仅表示是否存在intcnts.count(
;// 1存在cnts.count(
;// 0不存在// 查找lower_bound/upper_bound有序容器通用s.insert({1,2,3});its.lower_bound(
;// 第一个≥2的迭代器 → 指向2its.upper_bound(
;// 第一个2的迭代器 → 指向3// 基础操作s.empty();// 判断是否为空s.size();// 元素个数s.clear();// 清空容器s.begin();// 首元素迭代器s.end();// 末尾迭代器最后一个元素下一位s.rbegin();// 反向首元素降序第一个s.rend();// 反向末尾
multiset有序, 可重复核心特性元素可重复支持插入多个相同值的元素重复元素会相邻存放自动升序排列和set一致默认lessT可自定义比较器底层红黑树操作时间复杂度稳定O (logn)遍历为有序序列元素不可直接修改需 “删旧插新”与set的唯一差异允许重复元素因此插入 / 删除 / 查找 / 统计的函数行为略有调整无其他新函数。
常用函数multisetintms;ms.insert({2,1,2,2,3});// 升序可重复{1,2,2,2,3}// 插入insert(val) → 仅返回迭代器无bool值因重复插入也成功autoitms.insert(
;// 指向新插入的2// 删除erase() 三种用法与set的唯一区别ms.erase(
;// 用法1按值删删除所有的2ms.insert({2,2,2});// 恢复{1,2,2,2,3}itms.find(
;ms.erase(it);// 用法2按迭代器删仅删除单个2ms{1,2,2,3}ms.erase(ms.find(
,ms.end());// 用法3删区间 → 删从第一个2到末尾ms{1}//
统计count(val) → 返回重复元素的个数O(logn k)k为重复数ms.insert({2,2,2,3});intcntms.count(
;// 3有3个2cntms.count(
;// 0//
查找find(val) → 返回第一个等于val的迭代器其余同setitms.find(
;// 指向第一个2//
边界查找lower_bound/upper_bound → 同set用于获取重复元素的区间itms.lower_bound(
;// 第一个≥2 → 第一个2itms.upper_bound(
;// 第一个2 → 3// 结合两者遍历所有2[lower_bound(
, upper_bound(
)for(autoims.lower_bound(
;i!ms.upper_bound(
;i){cout*i ;// 输出2 2 2}// 基础操作empty/size/clear等与set完全一致set 与 multiset 差异仅因 “元素是否可重复” 导致的 4 点差异其余完全一致操作 / 特性set有序唯一multiset有序可重复insert 返回值pair 迭代器bool标记是否成功仅迭代器重复插入也成功erase(val)删唯一元素效果同 erase (迭代器)删除所有重复元素count(val)返回 0/1仅表示是否存在返回重复元素的个数重复元素处理插入重复元素自动忽略插入重复元素正常新增前置知识无序 set 系列的unordered_set和unordered_multiset底层均基于哈希表实现因此无自动排序特性元素按哈希值散列存储遍历顺序不可预测, 但插入、删除、查找的平均时间复杂度为 O (
最坏时间复杂度 O (n)。
unordered_set无序, 唯一核心特性元素严格唯一插入重复元素自动忽略无报错无序存储按哈希值散列遍历顺序与插入顺序无关不可预测底层哈希表平均 O (
操作最坏 O (n)无反向迭代器仅前向迭代器元素不可直接修改需 “删旧插新”不支持自定义排序因底层无排序结构仅能通过哈希值散列。
注意无序 set 无第二个模板参数无比较器因为不需要排序仅需哈希函数和 判断。
常用函数函数名和用法几乎与 set 完全一致差异仅在于无反向迭代器无 rbegin/rend、遍历无序因元素唯一count/erase/find行为与 set 一致unordered_setintus;us.insert({3,1,2,2});// 去重无序如{1,3,2}遍历顺序不可预测//
插入insert(val) → 返回pair迭代器, bool同set标记是否插入成功autoresus.insert(
;// false重复//
删除erase(val)/erase(迭代器)/erase(区间) → 同set因元素唯一us.erase(
;// 删唯一的2us{1,3}//
查找find(val) → 同set找到返回迭代器无则返回end()autoitus.find(
;//
统计count(val) → 返回0/1同setintcntus.count(
;// 1//
基础操作empty/size/clear/begin/end 均有无rbegin/rend// 遍历范围for无序for(intx:us)coutx ;// 如1 3顺序不可预测关键差异无lower_bound/upper_bound函数因为无序容器没有 “顺序”区间边界查找无意义这是有序和无序 set 系列的核心函数差异。
unordered_multiset无序元素可重复核心特性元素可重复支持插入多个相同值的元素重复元素散列到同一个哈希桶无序存储按哈希值散列遍历顺序不可预测重复元素通常相邻底层哈希表平均 O (
操作最坏 O (n)仅前向迭代器无反向迭代器元素不可直接修改需 “删旧插新”无自定义排序无lower_bound/upper_bound函数。
unordered_set 与 unordered_multiset 差异与有序系列的差异逻辑完全一致仅因 “元素是否可重复” 导致 3 点差异操作 / 特性unordered_set无序唯一unordered_multiset无序可重复insert 返回值pair 迭代器bool仅迭代器erase(val)删唯一元素删除所有重复元素count(val)返回 0/1返回重复元素的个数典型适用场景set有序去重场景如去重并排序的成绩、唯一的 ID 集合multiset有序可重复场景如允许同分的成绩排名、统计元素频率unordered_set高效无序去重场景如快速判断元素是否存在、缓存唯一键unordered_multiset高效无序可重复场景如快速统计元素出现次数、无需排序的重复数据存储。
使用特点核心坑点直接修改元素所有 set 家族的元素均不可直接修改强行修改会导致底层结构破坏程序崩溃 / 逻辑错误正确方式是先删除旧值再插入新值multiset/umultiset 的 erase (val)按值删除会删掉所有重复元素仅删单个必须用erase(迭代器)无序 set 的排序误区unordered_* 系列无法排序若需先高效操作再排序可将元素拷贝到 vector 后用sort排序迭代器失效 有序 set红黑树删除元素仅导致被删元素的迭代器失效其余迭代器均有效无序 set哈希表插入 / 删除元素可能导致哈希表扩容 / 重散列所有迭代器失效需重新查找。
使用技巧统计元素频率优先用multiset/unordered_multiset的count(val)替代mapT, int无需手动维护计数有序区间查询用set/multiset的lower_bound/upper_bound快速获取 [L, R) 区间的元素高效去重无需排序时用unordered_setO (
需要排序时用setO (logn)均比vectorsortunique更适合动态增删的场景避免频繁遍历无序 set遍历顺序不可预测若需遍历后排序建议拷贝到 vector 再处理。
总结C STL 的 set 家族四大类型围绕“有序 / 无序”和“唯一 / 可重复”两个维度划分底层对应红黑树和哈希表两种经典数据结构核心要点可归纳为 3 句话有序选红黑树set/multiset稳定 O (logn)支持排序和区间查询自定义类型仅需重载 无序选哈希表unordered_*平均 O (
效率更高自定义类型需重载 哈希函数唯一选不带 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。