c++数据结构9——set结构详解

一、set以二叉查找树为基础

二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树结构，具有以下特点：

1. 左子树所有节点值小于根节点值

2. 右子树所有节点值大于根节点值

3. 左右子树也都是二叉查找树

图例：

       8
     /   \
    3     10
   / \      \
  1   6      14
     / \    /
    4   7  13

重要特性：二叉查找树的中序遍历结果是一个有序序列（升序排列）

二、STL中的set容器

1.set基本概念

• set是C++标准模板库(STL)中的关联容器

• 基于红黑树（自平衡二叉查找树）实现

• 三大特性：

  1. 自动排序（默认升序）

  2. 元素唯一（自动去重）

  3. 高效操作（查找、插入、删除时间复杂度O(log n)）

2.set的定义与初始化

#include <set>  // 必须包含的头文件

// 定义set的基本语法
set<数据类型> 集合名称;

// 示例：定义一个整型set
set<int> mySet;

3.set的常用成员函数

三、set迭代器的使用

1.迭代器基本概念

• 迭代器类似于指针，用于遍历容器元素

• set迭代器是双向迭代器（支持++和--操作）

• 不支持随机访问（不能使用+/-操作符）

2.迭代器定义语法

set<数据类型>::iterator 迭代器名称;

3.遍历set的三种方法

1. 传统迭代器遍历

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的适用场景

适用场景

1. 需要维护有序集合

2. 需要频繁查询元素是否存在

3. 需要自动去重的场景

4. 需要按顺序遍历元素的场景