C++ STL中的set，你真的会用吗？
C++ STL中的set，你真的会用吗？
在C++标准模板库（STL）中，set是一个非常实用的关联容器，它不仅能够自动排序，还能去除重复元素，非常适合处理需要去重但不方便开数组的情况。本文将详细介绍set的定义、如何通过迭代器访问元素以及常用的函数如insert()、find()、erase()等，并分享一些实际应用的小技巧。无论你是初学者还是有经验的开发者，都能从中学到新的知识或找到灵感。
Set的基本概念与特性
set是C++ STL中的一种关联容器，用于存储唯一元素并自动排序。其底层实现基于红黑树，这是一种自平衡的二叉搜索树，能够保证在最坏情况下也能保持对数时间复杂度的插入、删除和查找操作。
set的主要特性包括：
- 唯一性：
set中的元素是唯一的，不允许重复。如果尝试插入重复元素，插入操作会失败。 - 有序性：元素会根据其排序规则（通常是
<运算符）自动排序。默认是升序排序，但可以通过提供自定义的比较函数来改变排序方式。 - 高效操作：由于底层使用了平衡二叉树，
set提供了高效的查找、插入和删除操作，时间复杂度为O(log n)。
Set的基本用法
定义与初始化
#include <set>
std::set<int> s; // 创建一个空的set
s.insert(10); // 插入元素10
s.insert(5); // 插入元素5
s.insert(20); // 插入元素20
s.insert(10); // 插入重复元素10，不会生效
// 输出set中的所有元素
for (const auto& elem : s) {
std::cout << elem << " "; // 输出 "5 10 20"
}
std::cout << std::endl;
常用成员函数
- 插入元素：使用
insert()函数插入元素。如果元素已存在，则不会插入。
s.insert(15); // 插入元素15
- 查找元素：使用
find()函数查找元素。如果找到，返回指向该元素的迭代器；否则返回end()。
auto it = s.find(10);
if (it != s.end()) {
std::cout << "Found: " << *it << std::endl; // 输出 "Found: 10"
}
- 删除元素：使用
erase()函数删除元素。
s.erase(10); // 删除元素10
- 获取大小：使用
size()函数获取set中元素的数量。
std::cout << "Size: " << s.size() << std::endl;
- 清空set：使用
clear()函数清空set中的所有元素。
s.clear();
std::cout << "Size after clear: " << s.size() << std::endl;
迭代器的使用
set提供了高效的迭代器，支持从最小到最大的顺序遍历。
for (auto it = s.begin(); it != s.end(); ++it) {
std::cout << *it << " "; // 按照升序输出所有元素
}
也可以使用范围for循环：
for (const auto& elem : s) {
std::cout << elem << " "; // 按照升序输出所有元素
}
Set与其他容器的比较
特性/容器 | set | map | unordered_set | unordered_map | vector |
|---|---|---|---|---|---|
底层数据结构 | 红黑树 | 红黑树 | 哈希表 | 哈希表 | 动态数组 |
元素顺序 | 有序 | 有序 | 无序 | 无序 | 插入顺序 |
查找效率 | O(log n) | O(log n) | 平均O(1)，最坏O(n) | 平均O(1)，最坏O(n) | O(n) |
插入效率 | O(log n) | O(log n) | 平均O(1)，最坏O(n) | 平均O(1)，最坏O(n) | 平均O(1)，最坏O(n) |
元素唯一性 | 是 | 键是，值否 | 是 | 键是，值否 | 否 |
元素类型 | 单一值 | 键值对 | 单一值 | 键值对 | 单一值 |
支持随机访问 | 否 | 否 | 否 | 否 | 是 |
从上表可以看出：
set：当需要存储不重复的元素，并且对元素的顺序有要求时，set是一个好选择。map：当你需要键值对的映射，并且希望按照键来排序时，map是更适合的选择。unordered_set和unordered_map：如果不需要保持元素顺序，但需要更快的访问速度，可以考虑使用哈希表实现的容器。vector：适用于需要随机访问的场景，但插入和删除效率较低。
实际应用场景
set在实际开发中有很多应用场景：
去重：当需要去除重复元素时，
set是一个理想的选择。例如，在处理用户ID列表时，可以使用set来确保每个ID都是唯一的。有序集合管理：在需要保持数据有序的情况下，如书籍ISBN号集合、文档中不同单词的统计等，
set能够提供高效的解决方案。快速查找：由于
set提供了O(log n)的查找效率，它非常适合用于需要快速查找的场景。
使用技巧与注意事项
- 自定义比较函数：如果需要改变默认的排序方式，可以提供自定义的比较函数。
struct Greater {
bool operator()(int a, int b) const {
return a > b;
}
};
std::set<int, Greater> s;
s.insert(10);
s.insert(5);
s.insert(20);
// 输出 "20 10 5"
for (const auto& elem : s) {
std::cout << elem << " ";
}
std::cout << std::endl;
元素不可修改：
set中的元素是常量，不能直接修改。如果需要修改元素，需要先删除再插入。性能考虑：虽然
set提供了高效的查找和插入操作，但在大量数据的情况下，哈希表实现的容器可能提供更好的性能。
通过深入理解set的基本概念、特性、使用方法以及与其他容器的区别，我们不仅能够更有效地利用这一工具，还能在编程实践中体会到数据结构设计背后的深刻哲学和心理学原理。正如C++之父Bjarne Stroustrup所说：“掌握C++是一场旅程，它不仅仅是学习一种编程语言，更是在学习如何更优雅地表达思想。”探索set容器，正是这场旅程中的一部分。