C++ 中 set
的用法
set
是 C++ 标准模板库(STL)中的关联容器,基于红黑树实现,具有元素唯一和自动排序的特性,插入、删除、查找操作的平均时间复杂度为 O(log n)。
一、核心特性
- 元素唯一性:自动去重,不会存储重复元素。
- 自动排序:默认按升序排列,支持自定义排序规则。
- 不可直接修改元素:元素为常量,需先删除再插入新值。
二、基本用法(需包含头文件 <set>
)
1. 定义与初始化
#include <iostream>
#include <set>
using namespace std;int main() {// 1. 空 set(默认升序)set<int> s1;// 2. 初始化时插入元素(自动去重+排序)set<int> s2 = {3, 1, 4, 1, 5}; // 结果:{1, 3, 4, 5}// 3. 自定义排序(降序)set<int, greater<int>> s3 = {3, 1, 4}; // 结果:{4, 3, 1}return 0;
}
2. 插入元素(insert()
)
set<int> s;
s.insert(5); // 插入单个元素
s.insert({3, 1, 4}); // 插入多个元素(C++11+)
// 结果:s = {1, 3, 4, 5}(自动排序+去重)
3. 删除元素(erase()
)
set<int> s = {1, 3, 4, 5};// ① 删除指定值的元素(返回删除个数:0 或 1)
s.erase(3); // s 变为 {1, 4, 5}// ② 删除迭代器指向的元素
auto it = s.find(4);
if (it != s.end()) {s.erase(it); // s 变为 {1, 5}
}// ③ 清空所有元素
s.clear(); // s 为空
4. 查找元素(find()
)
set<int> s = {1, 3, 4, 5};
auto it = s.find(3); // 查找值为 3 的元素if (it != s.end()) {cout << "找到元素:" << *it << endl; // 输出:找到元素:3
} else {cout << "未找到元素" << endl;
}
5. 其他常用操作
set<int> s = {1, 3, 4, 5};cout << s.size() << endl; // 元素个数:4
cout << s.empty() << endl; // 是否为空:0(false)
cout << *s.begin() << endl; // 第一个元素(最小):1
cout << *s.rbegin() << endl; // 最后一个元素(最大):5// 升序遍历
for (auto it = s.begin(); it != s.end(); ++it) {cout << *it << " "; // 输出:1 3 4 5
}// 降序遍历(反向迭代器)
for (auto it = s.rbegin(); it != s.rend(); ++it) {cout << *it << " "; // 输出:5 4 3 1
}
三、自定义排序规则
默认按 less<T>
(升序)排序,可通过自定义比较器修改规则(如结构体排序)。
#include <iostream>
#include <set>
#include <string>
using namespace std;// 结构体
struct Person {string name;int age;
};// 自定义比较器(按年龄升序,同年龄按姓名升序)
struct ComparePerson {bool operator()(const Person& a, const Person& b) const {if (a.age != b.age) return a.age < b.age;else return a.name < b.name;}
};int main() {set<Person, ComparePerson> people;people.insert({"Alice", 25});people.insert({"Bob", 20});people.insert({"Charlie", 25});// 遍历输出:Bob (20), Alice (25), Charlie (25)for (const auto& p : people) {cout << p.name << " (" << p.age << "), ";}return 0;
}
四、set
与 unordered_set
的区别
特性 | set |
unordered_set |
---|---|---|
底层实现 | 红黑树 | 哈希表 |
排序 | 自动排序(可自定义) | 无序 |
查找效率 | O(log n) | 平均 O(1),最坏 O(n) |
适用场景 | 有序遍历/范围查询 | 快速去重/查找 |
五、常见应用场景
- 去重:统计数组中不同元素(如
{1,1,3}
→ 去重后{1,3}
)。 - 有序存储:维护排序的数据集(如排行榜)。
- 范围查询:结合
lower_bound()
/upper_bound()
查找区间元素。
set
是处理“有序+唯一”元素的高效工具,灵活应用可简化代码逻辑。