1. set容器概述
set是C++标准模板库(STL)中的关联式容器，它存储唯一元素并自动排序。底层通常采用红黑树实现，这使得它的插入、删除和查找操作都能保持O(logN)的时间复杂度。与vector和list等序列式容器不同，set的特点是：
- 元素自动排序（默认升序）
- 元素值唯一（multiset允许重复）
- 高效的查找性能（对数时间复杂度）
cpp复制#include <set>
using namespace std;
set<int> mySet; // 声明一个整型set
set的模板参数有三个：
cpp复制template <class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
class set;
- Key：存储元素的类型
- Compare：比较函数对象类型，默认是
less<Key> - Allocator：内存分配器类型，默认是
allocator<Key>
2. set的核心接口详解
2.1 构造函数
set提供多种构造函数：
cpp复制set<int> s1; // 空set
set<int> s2 = {1, 3, 5, 7}; // 初始化列表构造
set<int> s3(s2.begin(), s2.end()); // 迭代器范围构造
set<int, greater<int>> s4; // 降序set
注意：构造时传入的比较函数对象会影响元素的排序方式。默认
less<Key>产生升序，greater<Key>产生降序。
2.2 迭代器操作
set提供双向迭代器，支持正向和反向遍历：
cpp复制set<int> s = {2, 4, 6, 8};
// 正向遍历
for(auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " ";
}
// 反向遍历
for(auto rit = s.rbegin(); rit != s.rend(); ++rit) {
cout << *rit << " ";
}
// 范围for循环
for(int num : s) {
cout << num << " ";
}
重要特性：set的迭代器是const迭代器，不能通过迭代器修改元素值，因为这可能破坏内部的红黑树结构。
2.3 插入操作
set提供多种插入方式：
cpp复制set<int> s;
// 插入单个值
s.insert(10);
auto ret = s.insert(20); // 返回pair<iterator, bool>
// 插入初始化列表
s.insert({5, 15, 25});
// 使用emplace直接构造元素
s.emplace(30);
insert返回值是一个pair：
- first：指向插入元素的迭代器
- second：是否插入成功（false表示元素已存在）
2.4 查找操作
set提供高效的查找方法：
cpp复制set<int> s = {10, 20, 30, 40};
// find查找元素
auto it = s.find(20);
if(it != s.end()) {
cout << "Found: " << *it << endl;
}
// count统计元素出现次数（set中只能是0或1）
if(s.count(30)) {
cout << "30 exists" << endl;
}
// lower_bound和upper_bound
auto lb = s.lower_bound(25); // 第一个>=25的元素
auto ub = s.upper_bound(35); // 第一个>35的元素
2.5 删除操作
set提供多种删除方式：
cpp复制set<int> s = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 通过值删除
size_t n = s.erase(5); // 返回删除的元素个数
// 通过迭代器删除
auto it = s.find(3);
if(it != s.end()) {
s.erase(it);
}
// 删除一个区间
auto first = s.lower_bound(2);
auto last = s.upper_bound(7);
s.erase(first, last);
注意：删除元素后，指向该元素的迭代器会失效，但其他迭代器不受影响。
3. multiset的特殊性
multiset允许存储重复元素，接口与set类似但有重要区别：
cpp复制multiset<int> ms = {1, 2, 2, 3, 3, 3};
// 插入允许重复
ms.insert(2);
// count返回实际出现次数
cout << ms.count(2); // 输出3
// find返回第一个匹配元素的迭代器
auto it = ms.find(3);
while(it != ms.end() && *it == 3) {
cout << *it++ << " ";
}
// erase会删除所有匹配值
ms.erase(3); // 删除所有3
4. 实际应用案例
4.1 求数组交集
cpp复制vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
vector<int> result;
// 双指针遍历
auto it1 = s1.begin(), it2 = s2.begin();
while(it1 != s1.end() && it2 != s2.end()) {
if(*it1 == *it2) {
result.push_back(*it1);
++it1; ++it2;
}
else if(*it1 < *it2) ++it1;
else ++it2;
}
return result;
}
4.2 检测链表环
cpp复制ListNode *detectCycle(ListNode *head) {
set<ListNode*> visited;
while(head) {
if(visited.count(head)) return head;
visited.insert(head);
head = head->next;
}
return nullptr;
}
5. 性能分析与使用建议
-
时间复杂度：
- 插入：O(logN)
- 删除：O(logN)
- 查找：O(logN)
- 遍历：O(N)
-
内存使用：
- 每个元素需要额外存储左右子节点指针和颜色标记（红黑树实现）
- 相比vector占用更多内存
-
使用场景建议：
- 需要维护有序唯一元素的集合
- 需要频繁查找的场景
- 不需要随机访问元素的情况
-
替代方案考虑：
- 如果只需要判断存在性，unordered_set提供O(1)查找
- 如果需要保持插入顺序，可以考虑vector+sort+unique组合
6. 常见问题与解决方案
- 自定义类型排序：
对于自定义类型，需要提供比较函数或重载<运算符：
cpp复制struct Person {
string name;
int age;
bool operator<(const Person& other) const {
return age < other.age;
}
};
set<Person> people; // 按年龄排序
- 迭代器失效问题：
- 删除元素会使指向该元素的迭代器失效
- 其他迭代器仍然有效
- 安全做法是先获取下一个迭代器再删除
cpp复制set<int> s = {1, 2, 3, 4, 5};
for(auto it = s.begin(); it != s.end(); ) {
if(*it % 2 == 0) {
it = s.erase(it); // erase返回下一个有效迭代器
}
else {
++it;
}
}
- 性能优化技巧：
- 批量插入时使用范围插入而非单个插入
- 预先分配足够空间（如果可能知道元素数量）
- 考虑使用emplace代替insert避免临时对象构造
cpp复制set<string> s;
// 低效方式
s.insert(string("hello"));
s.insert(string("world"));
// 高效方式
s.emplace("hello");
s.emplace("world");
在实际开发中，set和multiset是非常有用的工具，特别是在需要维护有序唯一元素的场景。理解它们的内部实现原理和接口特性，能够帮助我们更高效地解决实际问题。