std::set 是 C++ STL 中的有序关联容器,底层通常由红黑树实现。它存储唯一元素,并在插入时自动排序,插入、删除、查找的时间复杂度均为 O(log N)。
std::set 的模板声明为:
cpp编辑
1template<class T, class Compare = std::less<T>,
2 class Alloc = std::allocator<T>>
3class set;其中 T 是元素类型,Compare 是排序规则,默认为 std::less<T>,即升序。
常见初始化方式包括:
默认构造:std::set<int> s;
列表初始化:std::set<int> s{3, 1, 4, 1, 5};,重复元素自动去重。
范围构造:std::set<int> s(v.begin(), v.end());
拷贝构造:std::set<int> s2(s1);
需要注意的是,set 的迭代器本质上是 const_iterator,不能通过迭代器修改元素值,否则会破坏红黑树的有序结构。
set 的核心操作围绕插入、删除、查找和状态查询展开:
insert(val):插入元素,若已存在则插入失败,返回 pair<iterator, bool>。
erase(val):按值删除,返回删除个数(set 中为 0 或 1)。也可通过迭代器或迭代器区间删除。
find(key):查找元素,存在则返回对应迭代器,否则返回 end()。
count(key):统计出现次数,set 中只能返回 0 或 1,常用于判断存在性。
lower_bound(val) / upper_bound(val):分别返回第一个 ≥ val 和第一个 > val 的迭代器,时间复杂度 O(log N)。
size() / empty() / clear():查询大小、判空、清空容器。
set 遍历有多种方式:
正向迭代器:
for (auto it = s.begin(); it != s.end(); ++it)
cout << *it << " ";范围 for 循环:
for (const auto& e : s) cout << e << " ";反向迭代器(降序输出):
for (auto it = s.rbegin(); it != s.rend(); ++it)
cout << *it << " ";区间删除遍历:结合 lower_bound 和 upper_bound 定位区间后,用 s.erase(it1, it2) 高效删除。
set 默认排序为升序,可通过以下三种方式自定义排序:
使用 std::greater<T> 实现降序:
std::set<int, std::greater<int>> s{3, 1, 4, 2};
// 输出:4 3 2 1自定义仿函数:定义结构体重载 operator(),适用于复杂逻辑或多级排序。
struct AbsCmp {
bool operator()(int a, int b) const {
return std::abs(a) < std::abs(b);
}
};
std::set<int, AbsCmp> s{-5, 3, -1, 4};
// 按绝对值升序:-1 3 4 -5使用 Lambda(配合 decltype):
auto cmp = [](int a, int b) { return a > b; };
std::set<int, decltype(cmp)> s(cmp);Lambda 不能直接作为模板参数,必须通过 decltype 推导类型并在构造时传入实例。
自定义比较器必须满足严格弱序(Strict Weak Ordering),即自反性、反对称性和传递性,否则会导致未定义行为。
![]()
std::set 的核心价值在于自动去重与有序存储,适合需要快速查找、范围查询和去重排序的场景。使用时需牢记:元素不可通过迭代器修改,排序规则在构造时确定且不可变更,自定义比较器必须满足严格弱序。对于允许重复元素的场景,可改用 std::multiset;对于需要键值对映射的场景,则应选择 std::map。
声明:所有来源为“聚合数据”的内容信息,未经本网许可,不得转载!如对内容有异议或投诉,请与我们联系。邮箱:marketing@think-land.com
包含研学创作(大纲)和研学创作(全文)
通过请求综述题目、指定文献ID集合、生成模式及学科名称,以流式方式返回生成的调研综述全文及引用的参考文献信息。
通过请求问题内容、学科名称及选题目的,返回包含中英文题目、推荐理由、多维度评分及相似文献的智能选题推荐结果。
通过自然语言请求,选择以流式或非流式方式返回模型生成的对话回复及相关的参考文献引用信息。
包含会议文献和会议文献详情