STL——set-育师

1. 核心概念：什么是 set？

std::set是C++标准模板库(STL)中的一种关联式容器。它的核心特性可以概括为以下三点：

唯一性：容器内的所有元素都是唯一的，不允许重复。
有序性：元素在容器中总是按照特定的严格弱序规则进行排序（默认是升序<）。
关键特性：元素的value就是key。你无法直接修改set中的元素，因为这可能破坏其有序性。

2. 底层实现：红黑树

这是理解set所有特性的关键。set通常被实现为一颗红黑树，这是一种高效的自平衡二叉搜索树。

二叉搜索树：保证了元素的有序存储，使得查找、插入、删除的平均时间复杂度可以达到O(log n)。
自平衡（红黑树）：防止在最坏情况下（例如插入有序序列）退化成链表（操作复杂度O(n)），通过旋转和变色规则保持树的相对平衡，保证了最坏情况下的操作复杂度也是O(log n)。

3. 基本用法与代码示例

cpp

#include <iostream> #include <set> using namespace std; int main() { // 1. 初始化 set<int> mySet = {5, 2, 8, 2, 1}; // 重复的2只会保留一个 // 此时 mySet 内容为: {1, 2, 5, 8} (已排序) // 2. 插入元素 mySet.insert(3); // 插入 3 auto ret = mySet.insert(5); // 再次尝试插入5 if (!ret.second) { cout << "Insertion failed. Element 5 already exists." << endl; } // 3. 遍历（总是有序输出） cout << "Set elements: "; for (int num : mySet) { cout << num << " "; // 输出: 1 2 3 5 8 } cout << endl; // 4. 查找与计数 auto it = mySet.find(3); if (it != mySet.end()) { cout << "Found: " << *it << endl; } cout << "Count of 2: " << mySet.count(2) << endl; // 输出1 (存在) cout << "Count of 9: " << mySet.count(9) << endl; // 输出0 (不存在) // 5. 删除元素 mySet.erase(2); // 通过值删除 auto it_to_erase = mySet.find(5); if (it_to_erase != mySet.end()) { mySet.erase(it_to_erase); // 通过迭代器删除 } // 6. 常用操作 cout << "Size: " << mySet.size() << endl; cout << "Is empty? " << (mySet.empty() ? "Yes" : "No") << endl; mySet.clear(); // 清空所有元素 return 0; }

4. 进阶特性与重要成员

自定义排序规则

你可以通过提供自定义的比较函数或函数对象来改变元素的排序方式。

cpp

// 示例1：使用greater<int>使set降序排列 set<int, greater<int>> descendingSet = {5, 2, 8, 1}; // 内容为: {8, 5, 2, 1} // 示例2：自定义结构体排序 struct Person { string name; int age; }; // 定义比较仿函数：按年龄升序排序 struct CompareByAge { bool operator()(const Person& a, const Person& b) const { return a.age < b.age; } }; set<Person, CompareByAge> personSet;

关键迭代器与方法

除了begin()和end()，set提供了一些特有的迭代器方法，这对于有序数据的操作非常高效：

lower_bound(key)：返回第一个 >= key的元素的迭代器。
upper_bound(key)：返回第一个 > key的元素的迭代器。
equal_range(key)：返回一个pair，表示等于key的元素范围（对于set，这个范围最多包含一个元素）。

cpp

set<int> s = {10, 20, 30, 40, 50}; auto low = s.lower_bound(25); // 指向30 (第一个 >=25 的元素) auto up = s.upper_bound(35); // 指向40 (第一个 >35 的元素) s.erase(low, up); // 删除区间 [30, 40)，即删除30 // 此时 s = {10, 20, 40, 50}

5. 核心特点总结与对比

特性	`std::set`	`std::vector`	`std::unordered_set`
元素顺序	严格有序（根据比较规则）	插入顺序	无序（根据哈希值）
重复元素	不允许	允许	不允许
底层实现	红黑树（平衡BST）	动态数组	哈希表
平均时间复杂度	查找/插入/删除:O(log n)	查找: O(n)，尾部插入: O(1)	查找/插入/删除:O(1)
关键用途	需要自动排序且去重的场景	随机访问、尾部操作频繁	仅需快速查找去重，不关心顺序