C++中set用法详解
在C++中，set 是一个关联容器，定义在 <set> 头文件中，属于 C++ 标准模板库（STL）。它用于存储唯一元素的集合，元素会按照特定的顺序（默认升序）自动排序。set 基于平衡二叉搜索树（通常是红黑树）实现，具有高效的查找、插入和删除操作（时间复杂度为 O(log n)）。以下是对 set 用法的详细讲解。
1. set 的特点
- 唯一性：
set中的元素是唯一的，重复元素会被自动忽略。 - 自动排序：元素按照指定的比较函数（默认升序）排序。
- 不可修改：
set中的元素插入后不能直接修改，只能删除后重新插入。 - 高效性：基于平衡二叉搜索树，支持快速查找、插入和删除。
- 无下标访问：
set不支持通过下标（如s[0]）访问元素，只能通过迭代器或查找操作访问。
2. set 的基本操作
头文件
#include <set>定义 set
#include <iostream>
#include <set>
using namespace std;
set<int> s; // 定义一个存储 int 类型的 set，默认升序
set<int, greater<int>> s_desc; // 定义降序 setset<T>：默认使用<运算符进行升序排序。set<T, greater<T>>：使用greater<T>比较器进行降序排序。- 自定义比较器：可以传入自定义比较函数或结构体。
常用成员函数
以下是 set 的常用成员函数及其功能：
| 函数 | 功能 | 返回值 | 时间复杂度 |
|---|---|---|---|
insert(x) | 插入元素 x，若已存在则忽略 | pair<iterator, bool>（迭代器和插入成功标志） | O(log n) |
erase(x) | 删除值为 x 的元素 | 删除的元素个数 | O(log n) |
erase(iterator) | 删除迭代器指向的元素 | 无 | O(log n) |
find(x) | 查找值为 x 的元素 | 迭代器（若未找到，返回 end()） | O(log n) |
count(x) | 返回值为 x 的元素个数（0 或 1） | 整数 | O(log n) |
size() | 返回集合中元素个数 | 整数 | O(1) |
empty() | 检查集合是否为空 | 布尔值 | O(1) |
clear() | 清空集合 | 无 | O(n) |
begin() | 返回指向首元素的迭代器 | 迭代器 | O(1) |
end() | 返回指向末尾的迭代器 | 迭代器 | O(1) |
lower_bound(x) | 返回第一个不小于 x 的元素的迭代器 | 迭代器 | O(log n) |
upper_bound(x) | 返回第一个大于 x 的元素的迭代器 | 迭代器 | O(log n) |
3. set 的用法示例
基本操作示例
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
// 插入元素
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(1); // 重复元素会被忽略
// 遍历 set
cout << "Elements in set: ";
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " "; // 输出：1 2 3
}
cout << endl;
// 查找元素
if (s.find(2) != s.end()) {
cout << "Found 2 in set" << endl;
}
// 删除元素
s.erase(2);
cout << "After erasing 2: ";
for (auto x : s) {
cout << x << " "; // 输出：1 3
}
cout << endl;
// 检查大小和是否为空
cout << "Size: " << s.size() << endl; // 输出：2
cout << "Is empty: " << (s.empty() ? "Yes" : "No") << endl; // 输出：No
// 清空 set
s.clear();
cout << "After clear, is empty: " << (s.empty() ? "Yes" : "No") << endl; // 输出：Yes
return 0;
}降序 set 示例
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int, greater<int>> s;
s.insert(3);
s.insert(1);
s.insert(2);
cout << "Elements in descending set: ";
for (auto x : s) {
cout << x << " "; // 输出：3 2 1
}
cout << endl;
return 0;
}自定义比较器示例
如果需要自定义排序规则，可以通过函数对象或结构体实现。例如，定义一个按绝对值升序排序的 set：
#include <iostream>
#include <set>
using namespace std;
struct Compare {
bool operator()(int a, int b) const {
return abs(a) < abs(b); // 按绝对值升序排序
}
};
int main() {
set<int, Compare> s;
s.insert(3);
s.insert(-2);
s.insert(-4);
s.insert(1);
cout << "Elements sorted by absolute value: ";
for (auto x : s) {
cout << x << " "; // 输出：1 -2 3 -4（或类似顺序，取决于实现）
}
cout << endl;
return 0;
}lower_bound 和 upper_bound 示例
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {1, 3, 5, 7};
auto it1 = s.lower_bound(3); // 指向 3
auto it2 = s.upper_bound(3); // 指向 5
cout << "lower_bound(3): " << *it1 << endl; // 输出：3
cout << "upper_bound(3): " << *it2 << endl; // 输出：5
return 0;
}4. set 与 multiset 的区别
set：元素唯一，重复元素会被忽略。multiset：允许重复元素，定义在<set>中，使用方式类似set，但insert不会忽略重复值，count(x)可能返回大于 1 的值。
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms;
ms.insert(1);
ms.insert(1);
ms.insert(2);
cout << "Multiset elements: ";
for (auto x : ms) {
cout << x << " "; // 输出：1 1 2
}
cout << endl;
cout << "Count of 1: " << ms.count(1) << endl; // 输出：2
return 0;
}5. 注意事项
- 不可修改元素：
set的元素是只读的，不能通过迭代器直接修改（*it = value会报错）。需删除后重新插入。 - 性能：查找、插入、删除操作的时间复杂度为 O(log n)，适合需要频繁查找和保持排序的场景。
- 空间开销：由于底层是平衡二叉树，
set比普通数组或vector占用更多内存。 - 迭代器失效：
set的插入操作不会使现有迭代器失效，但删除操作可能导致被删除元素的迭代器失效。
6. 适用场景
- 需要唯一性：如去重、存储唯一 ID。
- 需要自动排序：如排行榜、优先级队列。
- 高效查找：如快速检查元素是否存在。
- 区间查询：结合
lower_bound和upper_bound获取某个范围的元素。
7. 与 unordered_set 的对比
unordered_set（定义在<unordered_set>中）基于哈希表实现：- 优点：查找、插入、删除的平均时间复杂度为 O(1)。
- 缺点：元素无序，不支持
lower_bound和upper_bound。 set适合需要排序的场景，unordered_set适合追求极致查找性能的场景。
总结
C++ 中的 set 是一个功能强大且高效的容器，适合需要自动排序和唯一性约束的场景。通过灵活使用其成员函数（如 insert、erase、find、lower_bound 等）和自定义比较器，可以满足各种复杂需求。如果需要允许重复元素，可以使用 multiset；如果不需要排序但追求更高性能，可以考虑 unordered_set。
如果有更具体的 set 使用场景或问题，欢迎进一步提问！