一、set以二叉查找树为基础
二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树结构，具有以下特点：
-
左子树所有节点值小于根节点值
-
右子树所有节点值大于根节点值
-
左右子树也都是二叉查找树
图例：
8/ \3 10/ \ \1 6 14/ \ /4 7 13
重要特性：二叉查找树的中序遍历结果是一个有序序列（升序排列）
二、STL中的set容器
1.set基本概念
-
set是C++标准模板库(STL)中的关联容器 -
基于红黑树（自平衡二叉查找树）实现
-
三大特性：
-
自动排序（默认升序）
-
元素唯一（自动去重）
-
高效操作（查找、插入、删除时间复杂度O(log n)）
-
2.set的定义与初始化
#include <set> // 必须包含的头文件// 定义set的基本语法 set<数据类型> 集合名称;// 示例：定义一个整型set set<int> mySet;
3.set的常用成员函数
| 函数 | 功能描述 | 时间复杂度 |
|---|---|---|
insert(value) | 插入元素 | O(log n) |
erase(value) | 删除元素 | O(log n) |
find(value) | 查找元素 | O(log n) |
size() | 返回元素个数 | O(1) |
empty() | 判断是否为空 | O(1) |
clear() | 清空集合 | O(n) |
begin() | 返回起始迭代器 | O(1) |
end() | 返回结束迭代器 | O(1) |
三、set迭代器的使用
1.迭代器基本概念
-
迭代器类似于指针，用于遍历容器元素
-
set迭代器是双向迭代器（支持++和--操作）
-
不支持随机访问（不能使用+/-操作符）
2.迭代器定义语法
set<数据类型>::iterator 迭代器名称;
3.遍历set的三种方法
-
传统迭代器遍历
set<int> s = {3, 1, 4, 1, 5, 9};for(set<int>::iterator it = s.begin(); it != s.end(); it++) {cout << *it << " "; // 输出: 1 3 4 5 9
}
2.C++11范围for循环
for(auto num : s) {cout << num << " "; // 输出: 1 3 4 5 9
}
3.反向迭代器遍历
for(set<int>::reverse_iterator rit = s.rbegin(); rit != s.rend(); rit++) {cout << *rit << " "; // 输出: 9 5 4 3 1
}
四、set操作详解与示例
1. 插入元素
set<int> s;
s.insert(5); // 插入单个元素
s.insert({2, 8, 3, 5}); // 插入多个元素(重复元素5会被忽略)// 输出: 2 3 5 8
for(int num : s) {cout << num << " ";
}
2. 查找元素
set<int> s = {1, 3, 5, 7, 9};// 使用find函数查找元素
auto it = s.find(5);
if(it != s.end()) {cout << "找到元素: " << *it << endl;
} else {cout << "未找到元素" << endl;
}// 使用count函数检查存在性
if(s.count(4)) {cout << "元素4存在" << endl;
} else {cout << "元素4不存在" << endl;
}
3. 删除元素
set<int> s = {1, 2, 3, 4, 5, 6};// 删除指定值
s.erase(3); // 删除迭代器指向的元素
auto it = s.find(5);
if(it != s.end()) {s.erase(it);
}// 删除范围元素
s.erase(s.begin(), next(s.begin(), 2)); // 删除前两个元素// 输出剩余元素: 4 6
for(int num : s) {cout << num << " ";
}
五、应用实例：统计不同数字个数
问题描述
输入n个整数，输出其中不同数字的个数
输入样例
5 1 3 1 99999999 3
输出结果
3
解法代码
#include <iostream>
#include <set>
using namespace std;int main() {int n;cin >> n;set<long long> uniqueNumbers; // 使用long long防止溢出for(int i = 0; i < n; i++) {long long num;cin >> num;uniqueNumbers.insert(num); // 自动去重}cout << uniqueNumbers.size() << endl;return 0;
}
六、set的进阶用法
1. 自定义排序规则
// 定义降序排列的set
struct Descending {bool operator()(int a, int b) const {return a > b;}
};set<int, Descending> descendingSet = {3, 1, 4, 2};// 输出: 4 3 2 1
for(int num : descendingSet) {cout << num << " ";
}
2. 存储自定义类型
struct Point {int x, y;// 必须定义比较运算符bool operator<(const Point& p) const {return (x == p.x) ? (y < p.y) : (x < p.x);}
};set<Point> pointSet;
pointSet.insert({1, 2});
pointSet.insert({3, 4});
pointSet.insert({1, 2}); // 重复元素，不会被插入cout << "点的数量: " << pointSet.size(); // 输出: 2
七、set的适用场景
适用场景
-
需要维护有序集合
-
需要频繁查询元素是否存在
-
需要自动去重的场景
-
需要按顺序遍历元素的场景
