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

C++ std::set的用法

news 2025/6/20 11:56:48

std::set 是 C++ 标准模板库（STL）中的关联容器，用于存储唯一元素并按特定排序规则自动排序（默认升序）。其底层通常基于红黑树实现，因此插入、删除和查找操作的时间复杂度均为 O(log n)。以下是其核心用法详解：

🔍 一、基本特性

唯一性
元素值唯一，重复插入无效。

std::set<int> s;
s.insert(10);
s.insert(10);  // 无效，集合仍为 {10}

有序性
元素默认按升序排列，支持自定义排序规则。
```
std::set<int> s = {3, 1, 2};
// 输出：1 2 3
```
不可直接修改元素
需先删除旧元素，再插入新值。
高性能操作
插入 (insert)、删除 (erase)、查找 (find) 的时间复杂度为 O(log n)。

⚙️ 二、基本操作

1. 初始化与定义

#include <set>
std::set<int> s1;                     // 空集合
std::set<int> s2 = {1, 2, 3};         // 初始化列表
std::set<int> s3(s2.begin(), s2.end()); // 通过迭代器初始化[2,5](@ref)

2. 插入元素

s1.insert(4);                   // 插入单个元素
s1.insert({5, 6});              // 插入多个元素
s1.insert(s2.begin(), s2.end()); // 插入另一容器的元素[3,4](@ref)

3. 删除元素

s1.erase(4);                    // 删除值为4的元素
auto it = s1.find(5);
if (it != s1.end()) s1.erase(it); // 通过迭代器删除
s1.erase(s1.begin(), s1.end());   // 删除所有元素（等价于 `clear()`）[3,4](@ref)

4. 查找元素

auto it = s1.find(3);           // 返回迭代器，未找到则返回 `end()`
if (it != s1.end()) {std::cout << "Found: " << *it << std::endl;
}
if (s1.count(3) > 0) {          // 返回元素是否存在（0或1）std::cout << "Element exists" << std::endl;
}

5. 遍历元素

// 迭代器遍历
for (auto it = s1.begin(); it != s1.end(); ++it) {std::cout << *it << " ";
}// 范围for循环（推荐）
for (const auto& elem : s1) {std::cout << elem << " ";
}

6. 其他操作

方法	功能	示例
`size()`	返回元素数量	`s1.size()`
`empty()`	检查集合是否为空	`s1.empty()`
`clear()`	清空所有元素	`s1.clear()`
`lower_bound()`	返回第一个 ≥ 值的迭代器	`s1.lower_bound(2)`
`upper_bound()`	返回第一个 > 值的迭代器	`s1.upper_bound(2)`

🔄 三、自定义排序规则

通过函数对象或 Lambda 表达式定义排序逻辑：

// 降序排序
struct Compare {bool operator()(int a, int b) const {return a > b;}
};
std::set<int, Compare> s = {1, 3, 2};  // 输出：3 2 1// Lambda 表达式
auto comp = [](int a, int b) { return a > b; };
std::set<int, decltype(comp)> s2(comp);

🎯 四、应用场景

去重与排序
快速去除重复元素并排序（如统计唯一单词）。
高效查找
频繁检查元素是否存在（如黑名单过滤）。
有序数据维护
需动态维护有序集合的场景（如排行榜）。

⚠️ 五、注意事项

内存占用较高
红黑树实现导致内存开销大于 std::unordered_set。
元素不可修改
修改元素需先删除再插入。
迭代器失效
删除元素时，指向该元素的迭代器失效，但其他迭代器仍有效。

📊 六、与其他容器对比

特性	`std::set`	`std::unordered_set`	`std::vector`
元素唯一性	✅	✅	❌
自动排序	✅	❌	❌
查找复杂度	O(log n)	O(1)	O(n)
内存开销	较高（红黑树）	中等（哈希表）	低（动态数组）
适用场景	需有序唯一元素	需快速查找且无序	随机访问频繁