当前位置：首页 > news >正文

C++ STL入门：set 集合容器

news 2025/5/9 6:15:04

C++ STL入门：set 集合容器

一、核心特性与适用场景

set 是 C++ STL 提供的关联式容器，基于红黑树实现，具有两大核心特性：

特性	表现形式	底层原理
元素唯一性	重复值自动去重	插入时进行二叉树键比对
自动排序	元素默认升序排列	红黑树中序遍历特性

典型应用场景：

数学集合运算（并集/交集）
数据去重（如日志分析）
自动排序维护（优先队列基础）
快速查找（O(log n)时间复杂度）

二、基础操作与代码演示

1. 容器初始化

#include <iostream>
#include <set>
using namespace std;int main() {set<int> s; // 创建空集合

2. 元素操作全流程

    // 插入操作s.insert(1); s.insert(2); s.insert(3); // 重复插入无效：s.insert(2); // 不会改变容器// 迭代器遍历（正序）for(auto it = s.begin(); it != s.end(); ++it){cout << *it << " "; // 输出：1 2 3}cout << endl;// 查找操作cout << boolalpha; // 显示布尔值为true/falsecout << (s.find(2) != s.end()) << endl; // truecout << (s.find(5) != s.end()) << endl; // false// 删除操作s.erase(2); cout << (s.find(2) != s.end()) << endl; // falsereturn 0;
}

三、操作时间复杂度分析

操作类型	时间复杂度	特性说明
insert()	O(log n)	需要平衡树结构调整
erase()	O(log n)	同样涉及树重构
find()	O(log n)	二分查找特性
遍历	O(n)	中序遍历完整红黑树
count(key)	O(log n)	因为元素唯一，实际返回0/1

四、高级特性与技巧

1. 自定义排序规则

// 创建降序集合
set<int, greater<int>> s;
s.insert(3); s.insert(1); s.insert(2);
for(int x : s) cout << x << " "; // 输出：3 2 1

2. 迭代器进阶操作

auto it = s.find(3);
if(it != s.end()) {cout << *it << endl; // 访问找到的元素if(next(it) != s.end()) { // 使用std::nextcout << *next(it) << endl; // 访问下一个元素}
}

3. 批量操作优化

// 使用初始化列表批量插入
set<int> s{5,3,7,3,1}; // 最终存储{1,3,5,7}// 范围删除
auto start = s.lower_bound(2); // >=2的第一个元素
auto end = s.upper_bound(6);   // >6的第一个元素
s.erase(start, end); // 删除区间[2,6]的元素

五、易错点与解决方案

错误类型	典型表现	解决方案
非唯一访问	重复插入未检查返回值	使用insert返回值判断
迭代器失效	修改容器时使用旧迭代器	操作后重新获取迭代器
排序规则混淆	降序集合未指定比较器	显式声明greater<>参数
查找逻辑错误	忽略find返回值验证	始终用!= end()判断结果

插入操作返回值处理示例：

auto result = s.insert(4);
if(result.second) {cout << "插入成功，位置：" << distance(s.begin(), result.first) << endl;
} else {cout << "元素已存在，位置：" << distance(s.begin(), result.first) << endl;
}

六、性能优化技巧

空间预分配（C++11新增）

s.max_size(); // 查询最大容量
// 通过swap实现容量收缩
set<int>(s).swap(s);

合并操作优化

set<int> s1{1,2}, s2{2,3};
// 合并到s1（O(n log n)）
s1.merge(s2);

节点控制访问

// C++17 提取节点进行修改
auto nh = s.extract(3); // 取出元素3
nh.value() = 4;         // 修改值
s.insert(move(nh));     // 重新插入

七、知识延伸与对比

容器类型	排序特性	查找效率	适用场景
set	自动排序	O(log n)	唯一有序数据存储
unordered_set	无序	O(1)平均	快速查找无需排序
multiset	允许重复	O(log n)	频率统计等场景
vector	插入顺序保持	O(n)	需频繁随机访问的场景