105 std::set (关联容器)
作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58
1. 基本概念
1.1 定义与特性
std::set是 C++ STL 中的关联容器- 基于红黑树（一种平衡二叉搜索树）实现
- 特性：
- 元素自动排序（默认升序）
- 元素唯一（不允许重复）
- 不可直接修改元素（需先删除再插入）
- 提供高效的查找、插入和删除操作（O(log n)）
1.2 头文件
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <set>
2. 模板参数
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
template<
2
class Key,
3
class Compare = std::less<Key>,
4
class Allocator = std::allocator<Key>
5
> class set;
- Key：存储的元素类型
- Compare：比较函数对象类型（默认
std::less<Key>） - Allocator：内存分配器类型（通常使用默认）
3. 构造函数与初始化
3.1 常用构造方式
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::set<int> s1; // 空set
2
std::set<int> s2 = {1, 2, 3, 4}; // 初始化列表
3
std::set<int> s3(s2); // 拷贝构造
4
std::set<int> s4(s2.begin(), s2.end()); // 范围构造
3.2 自定义比较函数
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
struct MyCompare {
2
bool operator()(const int& a, const int& b) const {
3
return a > b; // 降序排列
4
}
5
};
6
7
std::set<int, MyCompare> s; // 使用自定义比较函数
4. 常用操作
4.1 容量相关
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
s.empty(); // 判断是否为空
2
s.size(); // 返回元素数量
3
s.max_size(); // 返回可能的最大元素数量
4.2 修改操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
s.insert(5); // 插入元素
2
s.emplace(5); // 原地构造元素
3
s.erase(5); // 删除值为5的元素
4
s.erase(s.begin()); // 删除迭代器指向的元素
5
s.clear(); // 清空所有元素
4.3 查找操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
s.find(5); // 返回指向5的迭代器，未找到则返回end()
2
s.count(5); // 返回元素数量（0或1，因为元素唯一）
3
s.lower_bound(3); // 返回第一个不小于3的元素的迭代器
4
s.upper_bound(3); // 返回第一个大于3的元素的迭代器
5
s.equal_range(3); // 返回等于3的元素范围（pair<iterator, iterator>）
4.4 迭代器
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
for(auto it = s.begin(); it != s.end(); ++it) {...} // 正向迭代
2
for(auto rit = s.rbegin(); rit != s.rend(); ++rit) {...} // 反向迭代
5. 特殊操作
5.1 元素访问
- 没有
operator[]或at()方法 - 只能通过迭代器访问元素
5.2 合并集合
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::set<int> s1 = {1, 2, 3};
2
std::set<int> s2 = {3, 4, 5};
3
s1.merge(s2); // s1 = {1, 2, 3, 4, 5}, s2 = {3}
5.3 节点操作（C++17起）
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
auto node = s.extract(3); // 提取节点
2
s.insert(std::move(node)); // 插入节点
6. 性能分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| insert() | O(log n) | 插入元素 |
| erase() | O(log n) | 删除元素 |
| find() | O(log n) | 查找元素 |
| lower_bound() | O(log n) | 下界查找 |
| begin() | O(1) | 获取首元素迭代器 |
| size() | O(1) | 获取元素数量 |
7. 应用场景
- 需要维护有序且唯一的数据集合
- 需要频繁进行查找操作
- 需要快速判断元素是否存在
- 需要按顺序遍历元素
8. 相关容器比较
| 特性 | std::set | std::unordered_set | std::multiset |
|---|---|---|---|
| 有序 | 是 | 否 | 是 |
| 唯一元素 | 是 | 是 | 否 |
| 实现方式 | 红黑树 | 哈希表 | 红黑树 |
| 查找复杂度 | O(log n) | 平均O(1) | O(log n) |
| 插入复杂度 | O(log n) | 平均O(1) | O(log n) |
9. 示例代码
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <set>
3
4
int main() {
5
// 创建并初始化set
6
std::set<int> numbers = {5, 2, 8, 1, 3};
7
8
// 自动排序
9
for(int n : numbers) {
10
std::cout << n << " "; // 输出: 1 2 3 5 8
11
}
12
std::cout << "\n";
13
14
// 插入元素
15
numbers.insert(4);
16
17
// 查找元素
18
if(numbers.find(3) != numbers.end()) {
19
std::cout << "3 found in set\n";
20
}
21
22
// 删除元素
23
numbers.erase(2);
24
25
// 使用自定义比较函数
26
std::set<int, std::greater<int>> descending = {5, 2, 8, 1, 3};
27
for(int n : descending) {
28
std::cout << n << " "; // 输出: 8 5 3 2 1
29
}
30
31
return 0;
32
}
10. 注意事项
- 插入和删除操作不会使迭代器失效（除了被删除元素的迭代器）
- 元素类型必须支持严格弱序比较（或提供自定义比较函数）
- 对于复杂类型，考虑使用
std::set<std::shared_ptr<T>>或自定义比较函数 - 在C++20中新增了
contains()方法作为count()的替代
std::set 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
| insert | 插入元素 | pair<iterator, bool> insert(const value_type& val); | std::set<int> s; auto ret = s.insert(42); | 返回一个 pair，first 是迭代器，second 表示是否插入成功（元素唯一）。 |
| emplace | 直接构造元素（避免拷贝） | pair<iterator, bool> emplace(Args&&... args); | s.emplace(42); | 性能优于 insert 当元素构造开销大时。 |
| erase | 删除元素 | size_type erase(const key_type& val); | s.erase(42); | 返回删除的元素数量（0 或 1）。 |
| find | 查找元素 | iterator find(const key_type& val) const; | auto it = s.find(42); if (it != s.end()) { /* 找到 */ } | 未找到时返回 end()。 |
| count | 统计元素出现次数 | size_type count(const key_type& val) const; | if (s.count(42)) { /* 存在 */ } | 返回 0 或 1（set 元素唯一）。 |
| lower_bound | 返回第一个不小于 val 的迭代器 | iterator lower_bound(const key_type& val) const; | auto it = s.lower_bound(42); | 用于范围查询或有序插入。 |
| upper_bound | 返回第一个大于 val 的迭代器 | iterator upper_bound(const key_type& val) const; | auto it = s.upper_bound(42); | 结合 lower_bound 实现范围删除/查询。 |
| equal_range | 返回匹配元素的迭代器范围 | pair<iterator, iterator> equal_range(const key_type& val) const; | auto [first, last] = s.equal_range(42); | 返回 pair，范围是 [first, last)（未找到时两者均为 end()）。 |
| clear | 清空所有元素 | void clear() noexcept; | s.clear(); | 容器大小变为 0。 |
| size | 返回元素数量 | size_type size() const noexcept; | size_t num = s.size(); | 时间复杂度：O(1)。 |
| empty | 检查容器是否为空 | bool empty() const noexcept; | if (s.empty()) { /* 空 */ } | 等价于 size() == 0。 |
| begin/end | 返回迭代器 | iterator begin() noexcept;iterator end() noexcept; | for (auto it = s.begin(); it != s.end(); ++it) { ... } | 用于遍历，end() 是尾后迭代器。 |
| rbegin/rend | 反向迭代器 | reverse_iterator rbegin() noexcept;reverse_iterator rend() noexcept; | for (auto it = s.rbegin(); it != s.rend(); ++it) { ... } | 逆序遍历。 |
示例代码（完整演示）
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <set>
3
4
int main() {
5
std::set<int> s = {10, 20, 30};
6
7
// 插入
8
s.insert(40);
9
auto [it, success] = s.emplace(50); // C++17 结构化绑定
10
11
// 查找
12
if (s.find(20) != s.end()) {
13
std::cout << "20 found\n";
14
}
15
16
// 删除
17
s.erase(10);
18
19
// 遍历
20
for (int x : s) {
21
std::cout << x << " "; // 输出: 20 30 40 50
22
}
23
24
return 0;
25
}
关键特性注释
- 自动排序：元素按
operator<或自定义比较函数排序。 - 唯一性：插入重复元素会被忽略（
insert.second为false）。 - 复杂度：查找/插入/删除操作平均 O(log n)，基于红黑树实现。
- 线程安全：需手动加锁（如
std::mutex）实现多线程安全。
文章目录