前言std::set是 C 标准库中的有序关联容器它保存一组互不相同的元素并按比较器维持顺序。需要去重 有序 快速查找时它往往是最直接的选择。元素一旦进入容器位置就由比较器决定因此标准不允许通过迭代器修改键值——set的迭代器解引用得到的是 const 引用这一点与std::vector完全不同。初学者最常见的误解有三个把set当成会自动去重的数组却忽略了它会按operator排序以为insert返回void拿不到是否插入成功的信息以为遍历顺序就是插入顺序。实际上insert返回一个pair第二个成员表示是否真的插入了遍历顺序由比较器决定与插入先后无关。还有人试图对set使用operator[]或at这两个接口属于std::mapset没有。本文按使用场景组织先讲容器模型和基本操作再讲插入、查找、删除的正确写法然后讨论自定义比较器与范围查找最后给出与其他容器的取舍建议和常见坑点。文中代码以 C17 为基准用到 C20 接口时会单独注明。一、容器模型与基本操作std::setT定义在set中其值类型就是T。每个值在容器中唯一唯一性由比较器定义的等价关系判断而不是由operator判断。默认比较器是std::lessT它调用operator。标准只规定了操作复杂度没有规定底层数据结构。主流实现通常采用红黑树因此插入、删除、查找都是对数复杂度 O(log n)遍历是 O(n)。具体实现以各标准库文档为准但复杂度保证是可依赖的。操作接口返回值复杂度插入insert(value)pairiterator, boolO(log n)就地构造emplace(args...)pairiterator, boolO(log n)查找find(key)迭代器找不到返回end()O(log n)计数count(key)0 或 1O(log n)删除erase(key)被删除元素个数O(log n)范围删除erase(first, last)删除后位置的迭代器O(log n k)下界lower_bound(key)第一个不小于 key 的位置O(log n)上界upper_bound(key)第一个大于 key 的位置O(log n)判空/大小empty()/size()bool/size_typeO(1)最基本的用法// 适用于 C17#include iostream#include set#include stringint main() {std::setstd::string names;names.insert(Carol);names.insert(Alice);names.insert(Bob);names.insert(Alice); // 重复不会插入auto [it, inserted] names.insert(Dave);if (inserted) {std::cout inserted: *it \n;}for (const auto name : names) {std::cout name \n;}}按标准语义遍历顺序是Alice、Bob、Carol、Dave即字符串的字典序而不是插入顺序。第二次插入Alice时insert返回的pair中second为falsefirst指向已存在的那个元素。insert还有几个重载需要区分带提示的insert(hint, value)返回迭代器提示准确时可以降低查找成本范围插入insert(first, last)和初始化列表插入insert(ilist)返回void不提供逐元素结果。C17 的结构化绑定让pair的拆包更简洁但要注意insert(ilist)不能这样拆。二、查找、删除与遍历查找成员用find不要用std::find。std::find对关联容器做线性扫描复杂度 O(n)完全浪费了set的有序结构set::find利用比较器做对数查找。// 适用于 C17#include iostream#include set#include stringint main() {std::setstd::string names{Alice, Bob, Carol};if (names.find(Bob) ! names.end()) {std::cout found Bob\n;}if (names.count(Dave) 0) {std::cout no Dave\n;}}删除有三种常用形式。按值删除返回删除个数set中只能是 0 或 1// 适用于 C17std::setint values{1, 2, 3, 4, 5};values.erase(3); // 返回 1values.erase(99); // 返回 0按迭代器删除返回被删除元素的下一个位置C11 起因此可以安全地在遍历中删除// 适用于 C17#include setint main() {std::setint values{1, 2, 3, 4, 5, 6};for (auto it values.begin(); it ! values.end(); ) {if (*it % 2 0) {it values.erase(it); // 用返回值继续遍历} else {it;}}}如果写成values.erase(it); it;it已经失效自增是未定义行为。这是关联容器遍历删除最典型的事故。需要修改元素键值时不能通过迭代器直接改。C17 提供了节点句柄接口extract把节点从容器中取出修改后再插回。// 需要 C17#include set#include string#include utilityint main() {std::setstd::string names{Alice, Bob};auto node names.extract(Bob);if (!node.empty()) {node.value() Robert; // 节点已脱离容器可以修改键names.insert(std::move(node)); // 重新插入位置按新键决定}}extract的价值在于避免删除 重新构造的额外开销同时保持节点内存。C17 还提供merge把另一个容器中不重复的节点搬过来// 需要 C17std::setint a{1, 2, 3};std::setint b{2, 3, 4};a.merge(b); // a 变为 {1,2,3,4}b 中只剩未迁移的重复元素merge不复制元素而是转移节点迁移后b中与a冲突的元素保留在b里。三、自定义比较器与范围查找当元素类型没有operator或默认顺序不符合需求时需要提供比较器。比较器可以是函数对象也可以是函数指针它必须满足严格弱序strict weak ordering不可自反、非对称、可传递且等价关系可传递。写成会破坏非对称性属于未定义行为。// 适用于 C17#include algorithm#include cctype#include iostream#include set#include stringstruct CaseInsensitiveLess {bool operator()(const std::string a, const std::string b) const {return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),[](unsigned char x, unsigned char y) {return std::tolower(x) std::tolower(y);});}};int main() {std::setstd::string, CaseInsensitiveLess names;names.insert(Alice);names.insert(alice); // 与 Alice 等价不会插入names.insert(Bob);std::cout names.size() \n; // 按标准语义应为 2std::cout names.count(ALICE) \n; // 1}这里Alice与alice在比较器下等价互相都不小于对方所以第二个插入被拒绝。count(ALICE)也能找到因为查找同样使用比较器的等价关系而不是字符串的operator。对于自定义结构体可以重载operator后直接使用默认比较器也可以单独写比较器// 适用于 C17#include setstruct Point {int x 0;int y 0;};struct PointLess {bool operator()(const Point a, const Point b) const {if (a.x ! b.x) {return a.x b.x;}return a.y b.y;}};int main() {std::setPoint, PointLess points;points.insert({1, 2});points.insert({1, 2}); // 等价不插入points.insert({1, 3});}范围查找依赖lower_bound与upper_bound前者返回第一个不小于给定键的位置后者返回第一个大于给定键的位置。两者配合可以取出一个值域// 适用于 C17#include iostream#include setint main() {std::setint scores{45, 58, 62, 70, 88, 91, 95};auto first scores.lower_bound(60); // 指向 62auto last scores.upper_bound(90); // 指向 91for (auto it first; it ! last; it) {std::cout *it \n;}}按标准语义输出 62、70、88。若区间端点也要包含注意lower_bound与upper_bound的差别lower_bound(key)包含等于 key 的元素upper_bound(key)不包含。equal_range(key)返回这两个迭代器组成的pair适合按键的等价类处理。四、set 与其他容器的取舍选择容器时先问清楚需求是否需要有序、是否允许重复、是否频繁按值查找、是否需要按下标访问。容器有序允许重复查找复杂度典型场景std::set是否O(log n)去重并保持排序、范围查询std::multiset是是O(log n)需要保留重复计数的有序集合std::unordered_set否否平均 O(1)最坏 O(n)只做成员判断、不关心顺序std::vector 排序是是排序后二分 O(log n)批量构建后只读、内存紧凑std::map是否键O(log n)键到值的映射如果只需要去重且不关心顺序std::unordered_set的平均查找更快但它不保证遍历顺序最坏情况下的复杂度也不如set稳定。如果数据一次性构建、之后只读std::vector排序后配合std::binary_search或std::lower_bound往往更紧凑缓存局部性也更好——具体差异依赖数据规模和实现应该自行测量而不是凭感觉。set的每个元素通常单独分配节点内存开销高于连续容器。元素数量很小例如十几个时vector线性查找的实际表现可能更好这不是语言保证而是需要结合数据测的工程判断。另外std::set存指针时默认比较的是指针地址不是指针指向的值// 适用于 C17#include set#include stringint main() {std::setconst char* raw;raw.insert(beta);raw.insert(alpha); // 按地址排序不按字典序}若需要按内容排序用std::setstd::string或者提供解引用后比较指针目标的自定义比较器。用const char*作为键还涉及字面量生命周期和重复内容不同地址的问题通常不是好选择。常见坑点❌ 对std::set使用operator[]或at()访问元素✅ 这两个接口属于std::mapset用find或count判断成员是否存在。❌ 用std::find(s.begin(), s.end(), key)查找set元素✅ 用成员函数s.find(key)利用有序结构做 O(log n) 查找。❌ 在遍历中写s.erase(it); it;✅ 使用it s.erase(it);被删除的迭代器立即失效继续自增是未定义行为。❌ 通过set的迭代器修改元素值例如*it new_value;✅ 迭代器解引用得到 const 引用需要改键时用 C17 的extract取出节点修改后再插入。❌ 自定义比较器写成return a b;✅ 比较器必须满足严格弱序用会破坏非对称性导致未定义行为。❌ 认为insert一定成功或认为重复插入会覆盖旧值✅ 检查返回pair的second重复元素被拒绝原元素保持不变。❌ 用std::setconst char*存放字符串并期望按字典序排列✅ 默认比较的是指针地址改用std::setstd::string或提供按内容比较的比较器。❌ 把set的遍历顺序当作插入顺序✅ 遍历顺序由比较器决定需要插入顺序时另存一个std::vector或改用其他数据结构。总结要点结论元素唯一性由比较器的等价关系决定不看operator迭代器指向 const 元素不能就地修改键插入结果insert/emplace返回pairiterator, bool删除按迭代器删除返回下一个位置可安全用于遍历范围查询lower_bound/upper_bound/equal_range改键C17 用extract取出节点修改后插回选型需要有序和稳定对数复杂度选set只查成员可考虑unordered_setstd::set的用法可以归纳为三句话插入看返回值查找用成员函数删除用返回的新迭代器。再叠加比较器必须严格弱序、键不可就地修改这两条约束绝大多数误用都能避免。真正决定它是否合适的是有序和范围查询是否属于需求如果只需要一个去重的哈希集合std::unordered_set往往更贴合。 
长河君 · 2026/10/21 13:56:31 · 阅读 1.2k C++ set的使用方法详解
前言std::set是 C 标准库中的有序关联容器它保存一组互不相同的元素并按比较器维持顺序。需要去重 有序 快速查找时它往往是最直接的选择。元素一旦进入容器位置就由比较器决定因此标准不允许通过迭代器修改键值——set的迭代器解引用得到的是 const 引用这一点与std::vector完全不同。初学者最常见的误解有三个把set当成会自动去重的数组却忽略了它会按operator排序以为insert返回void拿不到是否插入成功的信息以为遍历顺序就是插入顺序。实际上insert返回一个pair第二个成员表示是否真的插入了遍历顺序由比较器决定与插入先后无关。还有人试图对set使用operator[]或at这两个接口属于std::mapset没有。本文按使用场景组织先讲容器模型和基本操作再讲插入、查找、删除的正确写法然后讨论自定义比较器与范围查找最后给出与其他容器的取舍建议和常见坑点。文中代码以 C17 为基准用到 C20 接口时会单独注明。一、容器模型与基本操作std::setT定义在set中其值类型就是T。每个值在容器中唯一唯一性由比较器定义的等价关系判断而不是由operator判断。默认比较器是std::lessT它调用operator。标准只规定了操作复杂度没有规定底层数据结构。主流实现通常采用红黑树因此插入、删除、查找都是对数复杂度 O(log n)遍历是 O(n)。具体实现以各标准库文档为准但复杂度保证是可依赖的。操作接口返回值复杂度插入insert(value)pairiterator, boolO(log n)就地构造emplace(args...)pairiterator, boolO(log n)查找find(key)迭代器找不到返回end()O(log n)计数count(key)0 或 1O(log n)删除erase(key)被删除元素个数O(log n)范围删除erase(first, last)删除后位置的迭代器O(log n k)下界lower_bound(key)第一个不小于 key 的位置O(log n)上界upper_bound(key)第一个大于 key 的位置O(log n)判空/大小empty()/size()bool/size_typeO(1)最基本的用法// 适用于 C17#include iostream#include set#include stringint main() {std::setstd::string names;names.insert(Carol);names.insert(Alice);names.insert(Bob);names.insert(Alice); // 重复不会插入auto [it, inserted] names.insert(Dave);if (inserted) {std::cout inserted: *it \n;}for (const auto name : names) {std::cout name \n;}}按标准语义遍历顺序是Alice、Bob、Carol、Dave即字符串的字典序而不是插入顺序。第二次插入Alice时insert返回的pair中second为falsefirst指向已存在的那个元素。insert还有几个重载需要区分带提示的insert(hint, value)返回迭代器提示准确时可以降低查找成本范围插入insert(first, last)和初始化列表插入insert(ilist)返回void不提供逐元素结果。C17 的结构化绑定让pair的拆包更简洁但要注意insert(ilist)不能这样拆。二、查找、删除与遍历查找成员用find不要用std::find。std::find对关联容器做线性扫描复杂度 O(n)完全浪费了set的有序结构set::find利用比较器做对数查找。// 适用于 C17#include iostream#include set#include stringint main() {std::setstd::string names{Alice, Bob, Carol};if (names.find(Bob) ! names.end()) {std::cout found Bob\n;}if (names.count(Dave) 0) {std::cout no Dave\n;}}删除有三种常用形式。按值删除返回删除个数set中只能是 0 或 1// 适用于 C17std::setint values{1, 2, 3, 4, 5};values.erase(3); // 返回 1values.erase(99); // 返回 0按迭代器删除返回被删除元素的下一个位置C11 起因此可以安全地在遍历中删除// 适用于 C17#include setint main() {std::setint values{1, 2, 3, 4, 5, 6};for (auto it values.begin(); it ! values.end(); ) {if (*it % 2 0) {it values.erase(it); // 用返回值继续遍历} else {it;}}}如果写成values.erase(it); it;it已经失效自增是未定义行为。这是关联容器遍历删除最典型的事故。需要修改元素键值时不能通过迭代器直接改。C17 提供了节点句柄接口extract把节点从容器中取出修改后再插回。// 需要 C17#include set#include string#include utilityint main() {std::setstd::string names{Alice, Bob};auto node names.extract(Bob);if (!node.empty()) {node.value() Robert; // 节点已脱离容器可以修改键names.insert(std::move(node)); // 重新插入位置按新键决定}}extract的价值在于避免删除 重新构造的额外开销同时保持节点内存。C17 还提供merge把另一个容器中不重复的节点搬过来// 需要 C17std::setint a{1, 2, 3};std::setint b{2, 3, 4};a.merge(b); // a 变为 {1,2,3,4}b 中只剩未迁移的重复元素merge不复制元素而是转移节点迁移后b中与a冲突的元素保留在b里。三、自定义比较器与范围查找当元素类型没有operator或默认顺序不符合需求时需要提供比较器。比较器可以是函数对象也可以是函数指针它必须满足严格弱序strict weak ordering不可自反、非对称、可传递且等价关系可传递。写成会破坏非对称性属于未定义行为。// 适用于 C17#include algorithm#include cctype#include iostream#include set#include stringstruct CaseInsensitiveLess {bool operator()(const std::string a, const std::string b) const {return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),[](unsigned char x, unsigned char y) {return std::tolower(x) std::tolower(y);});}};int main() {std::setstd::string, CaseInsensitiveLess names;names.insert(Alice);names.insert(alice); // 与 Alice 等价不会插入names.insert(Bob);std::cout names.size() \n; // 按标准语义应为 2std::cout names.count(ALICE) \n; // 1}这里Alice与alice在比较器下等价互相都不小于对方所以第二个插入被拒绝。count(ALICE)也能找到因为查找同样使用比较器的等价关系而不是字符串的operator。对于自定义结构体可以重载operator后直接使用默认比较器也可以单独写比较器// 适用于 C17#include setstruct Point {int x 0;int y 0;};struct PointLess {bool operator()(const Point a, const Point b) const {if (a.x ! b.x) {return a.x b.x;}return a.y b.y;}};int main() {std::setPoint, PointLess points;points.insert({1, 2});points.insert({1, 2}); // 等价不插入points.insert({1, 3});}范围查找依赖lower_bound与upper_bound前者返回第一个不小于给定键的位置后者返回第一个大于给定键的位置。两者配合可以取出一个值域// 适用于 C17#include iostream#include setint main() {std::setint scores{45, 58, 62, 70, 88, 91, 95};auto first scores.lower_bound(60); // 指向 62auto last scores.upper_bound(90); // 指向 91for (auto it first; it ! last; it) {std::cout *it \n;}}按标准语义输出 62、70、88。若区间端点也要包含注意lower_bound与upper_bound的差别lower_bound(key)包含等于 key 的元素upper_bound(key)不包含。equal_range(key)返回这两个迭代器组成的pair适合按键的等价类处理。四、set 与其他容器的取舍选择容器时先问清楚需求是否需要有序、是否允许重复、是否频繁按值查找、是否需要按下标访问。容器有序允许重复查找复杂度典型场景std::set是否O(log n)去重并保持排序、范围查询std::multiset是是O(log n)需要保留重复计数的有序集合std::unordered_set否否平均 O(1)最坏 O(n)只做成员判断、不关心顺序std::vector 排序是是排序后二分 O(log n)批量构建后只读、内存紧凑std::map是否键O(log n)键到值的映射如果只需要去重且不关心顺序std::unordered_set的平均查找更快但它不保证遍历顺序最坏情况下的复杂度也不如set稳定。如果数据一次性构建、之后只读std::vector排序后配合std::binary_search或std::lower_bound往往更紧凑缓存局部性也更好——具体差异依赖数据规模和实现应该自行测量而不是凭感觉。set的每个元素通常单独分配节点内存开销高于连续容器。元素数量很小例如十几个时vector线性查找的实际表现可能更好这不是语言保证而是需要结合数据测的工程判断。另外std::set存指针时默认比较的是指针地址不是指针指向的值// 适用于 C17#include set#include stringint main() {std::setconst char* raw;raw.insert(beta);raw.insert(alpha); // 按地址排序不按字典序}若需要按内容排序用std::setstd::string或者提供解引用后比较指针目标的自定义比较器。用const char*作为键还涉及字面量生命周期和重复内容不同地址的问题通常不是好选择。常见坑点❌ 对std::set使用operator[]或at()访问元素✅ 这两个接口属于std::mapset用find或count判断成员是否存在。❌ 用std::find(s.begin(), s.end(), key)查找set元素✅ 用成员函数s.find(key)利用有序结构做 O(log n) 查找。❌ 在遍历中写s.erase(it); it;✅ 使用it s.erase(it);被删除的迭代器立即失效继续自增是未定义行为。❌ 通过set的迭代器修改元素值例如*it new_value;✅ 迭代器解引用得到 const 引用需要改键时用 C17 的extract取出节点修改后再插入。❌ 自定义比较器写成return a b;✅ 比较器必须满足严格弱序用会破坏非对称性导致未定义行为。❌ 认为insert一定成功或认为重复插入会覆盖旧值✅ 检查返回pair的second重复元素被拒绝原元素保持不变。❌ 用std::setconst char*存放字符串并期望按字典序排列✅ 默认比较的是指针地址改用std::setstd::string或提供按内容比较的比较器。❌ 把set的遍历顺序当作插入顺序✅ 遍历顺序由比较器决定需要插入顺序时另存一个std::vector或改用其他数据结构。总结要点结论元素唯一性由比较器的等价关系决定不看operator迭代器指向 const 元素不能就地修改键插入结果insert/emplace返回pairiterator, bool删除按迭代器删除返回下一个位置可安全用于遍历范围查询lower_bound/upper_bound/equal_range改键C17 用extract取出节点修改后插回选型需要有序和稳定对数复杂度选set只查成员可考虑unordered_setstd::set的用法可以归纳为三句话插入看返回值查找用成员函数删除用返回的新迭代器。再叠加比较器必须严格弱序、键不可就地修改这两条约束绝大多数误用都能避免。真正决定它是否合适的是有序和范围查询是否属于需求如果只需要一个去重的哈希集合std::unordered_set往往更贴合。