C++ set的使用方法详解

前言

std::set是 C++ 标准库中的有序关联容器：它保存一组互不相同的元素，并按比较器维持顺序。需要"去重 + 有序 + 快速查找"时，它往往是最直接的选择。元素一旦进入容器，位置就由比较器决定，因此标准不允许通过迭代器修改键值——set的迭代器解引用得到的是 const 引用，这一点与std::vector完全不同。

初学者最常见的误解有三个：把set当成"会自动去重的数组"，却忽略了它会按operator<排序；以为insert返回void，拿不到"是否插入成功"的信息；以为遍历顺序就是插入顺序。实际上insert返回一个pair，第二个成员表示是否真的插入了；遍历顺序由比较器决定，与插入先后无关。还有人试图对set使用operator[]或at，这两个接口属于std::map，set没有。

本文按使用场景组织：先讲容器模型和基本操作，再讲插入、查找、删除的正确写法，然后讨论自定义比较器与范围查找，最后给出与其他容器的取舍建议和常见坑点。文中代码以 C++17 为基准，用到 C++20 接口时会单独注明。

一、容器模型与基本操作

std::set<T>定义在<set>中，其值类型就是T。每个值在容器中唯一，唯一性由比较器定义的等价关系判断，而不是由operator==判断。默认比较器是std::less<T>，它调用operator<。

标准只规定了操作复杂度，没有规定底层数据结构。主流实现通常采用红黑树，因此插入、删除、查找都是对数复杂度 O(log n)，遍历是 O(n)。具体实现以各标准库文档为准，但复杂度保证是可依赖的。

操作	接口	返回值	复杂度

插入

insert(value)

pair<iterator, bool>

O(log n)

就地构造

emplace(args...)

pair<iterator, bool>

O(log n)

查找

find(key)

迭代器，找不到返回end()

O(log n)

计数

count(key)

0 或 1

O(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_type

O(1)

最基本的用法：

// 适用于 C++17
#include <iostream>
#include <set>
#include <string>

int main() {
std::set<std::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为false，first指向已存在的那个元素。

insert还有几个重载需要区分：带提示的insert(hint, value)返回迭代器，提示准确时可以降低查找成本；范围插入insert(first, last)和初始化列表插入insert(ilist)返回void，不提供逐元素结果。C++17 的结构化绑定让pair的拆包更简洁，但要注意insert(ilist)不能这样拆。

二、查找、删除与遍历

查找成员用find，不要用std::find。std::find对关联容器做线性扫描，复杂度 O(n)，完全浪费了set的有序结构；set::find利用比较器做对数查找。

// 适用于 C++17
#include <iostream>
#include <set>
#include <string>

int main() {
std::set<std::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）：

// 适用于 C++17
std::set<int> values{1, 2, 3, 4, 5};
values.erase(3); // 返回 1
values.erase(99); // 返回 0

按迭代器删除返回被删除元素的下一个位置（C++11 起），因此可以安全地在遍历中删除：

// 适用于 C++17
#include <set>

int main() {
std::set<int> 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已经失效，自增是未定义行为。这是关联容器遍历删除最典型的事故。

需要修改元素键值时，不能通过迭代器直接改。C++17 提供了节点句柄接口extract：把节点从容器中取出，修改后再插回。

// 需要 C++17
#include <set>
#include <string>
#include <utility>

int main() {
std::set<std::string> names{"Alice", "Bob"};

auto node = names.extract("Bob");
if (!node.empty()) {
node.value() = "Robert"; // 节点已脱离容器，可以修改键
names.insert(std::move(node)); // 重新插入，位置按新键决定
}
}

extract的价值在于避免"删除 + 重新构造"的额外开销，同时保持节点内存。C++17 还提供merge，把另一个容器中不重复的节点搬过来：

// 需要 C++17
std::set<int> a{1, 2, 3};
std::set<int> b{2, 3, 4};
a.merge(b); // a 变为 {1,2,3,4}，b 中只剩未迁移的重复元素

merge不复制元素，而是转移节点；迁移后b中与a冲突的元素保留在b里。

三、自定义比较器与范围查找

当元素类型没有operator<，或默认顺序不符合需求时，需要提供比较器。比较器可以是函数对象，也可以是函数指针；它必须满足严格弱序（strict weak ordering）：不可自反、非对称、可传递，且等价关系可传递。写成<=会破坏非对称性，属于未定义行为。

// 适用于 C++17
#include <algorithm>
#include <cctype>
#include <iostream>
#include <set>
#include <string>

struct 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::set<std::string, CaseInsensitiveLess> names;
names.insert("Alice");
names.insert("alice"); // 与 Alice 等价，不会插入
names.insert("Bob");

std::cout << names.size() << '\n'; // 按标准语义应为 2
std::cout << names.count("ALICE") << '\n'; // 1
}

这里"Alice"与"alice"在比较器下等价（互相都不小于对方），所以第二个插入被拒绝。count("ALICE")也能找到，因为查找同样使用比较器的等价关系，而不是字符串的operator==。

对于自定义结构体，可以重载operator<后直接使用默认比较器，也可以单独写比较器：

// 适用于 C++17
#include <set>

struct 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::set<Point, PointLess> points;
points.insert({1, 2});
points.insert({1, 2}); // 等价，不插入
points.insert({1, 3});
}

范围查找依赖lower_bound与upper_bound：前者返回第一个"不小于"给定键的位置，后者返回第一个"大于"给定键的位置。两者配合可以取出一个值域：

// 适用于 C++17
#include <iostream>
#include <set>

int main() {
std::set<int> scores{45, 58, 62, 70, 88, 91, 95};

auto first = scores.lower_bound(60); // 指向 62
auto last = scores.upper_bound(90); // 指向 91

for (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存指针时，默认比较的是指针地址，不是指针指向的值：

// 适用于 C++17
#include <set>
#include <string>

int main() {
std::set<const char*> raw;
raw.insert("beta");
raw.insert("alpha"); // 按地址排序，不按字典序
}

若需要按内容排序，用std::set<std::string>，或者提供解引用后比较指针目标的自定义比较器。用const char*作为键还涉及字面量生命周期和重复内容不同地址的问题，通常不是好选择。

常见坑点

1. 
   
2. ❌ 对std::set使用operator[]或at()访问元素
3. 
   

✅ 这两个接口属于std::map；set用find或count判断成员是否存在。

1. 
   
2. ❌ 用std::find(s.begin(), s.end(), key)查找set元素
3. 
   

✅ 用成员函数s.find(key)，利用有序结构做 O(log n) 查找。

1. 
   
2. ❌ 在遍历中写s.erase(it); ++it;
3. 
   

✅ 使用it = s.erase(it);；被删除的迭代器立即失效，继续自增是未定义行为。

1. 
   
2. ❌ 通过set的迭代器修改元素值，例如*it = new_value;
3. 
   

✅ 迭代器解引用得到 const 引用；需要改键时用 C++17 的extract取出节点，修改后再插入。

1. 
   
2. ❌ 自定义比较器写成return a <= b;
3. 
   

✅ 比较器必须满足严格弱序，用<；<=会破坏非对称性，导致未定义行为。

1. 
   
2. ❌ 认为insert一定成功，或认为重复插入会覆盖旧值
3. 
   

✅ 检查返回pair的second；重复元素被拒绝，原元素保持不变。

1. 
   
2. ❌ 用std::set<const char*>存放字符串并期望按字典序排列
3. 
   

✅ 默认比较的是指针地址；改用std::set<std::string>或提供按内容比较的比较器。

1. 
   
2. ❌ 把set的遍历顺序当作插入顺序
3. 
   

✅ 遍历顺序由比较器决定；需要插入顺序时另存一个std::vector，或改用其他数据结构。

总结

要点	结论

元素唯一性

由比较器的等价关系决定，不看operator==

迭代器	指向 const 元素，不能就地修改键

插入结果	insert/emplace返回pair<iterator, bool>

删除	按迭代器删除返回下一个位置，可安全用于遍历

范围查询	lower_bound/upper_bound/equal_range

改键	C++17 用extract取出节点，修改后插回

选型	需要有序和稳定对数复杂度选set，只查成员可考虑unordered_set

std::set的用法可以归纳为三句话：插入看返回值，查找用成员函数，删除用返回的新迭代器。再叠加比较器必须严格弱序、键不可就地修改这两条约束，绝大多数误用都能避免。真正决定它是否合适的，是有序和范围查询是否属于需求；如果只需要一个去重的哈希集合，std::unordered_set往往更贴合。