C++STL容器之set

1.介绍

set容器是C++标准模板库（STL）中的一个关联容器，用于存储唯一的元素。set中的元素是自动排序的，不允许重复。set通常基于红黑树（一种自平衡二叉查找树）实现，因此插入、删除和查找操作的时间复杂度都为O(log n)。

2.set用法

（1）定义和初始化

set的定义和初始化可以通过以下方式完成：

std::set<ElementType> mySet;

例如，定义一个int类型的set：

std::set<int> mySet;

//定义时初始化
std::set<int> mySet = {1, 2, 3, 4, 5};

（2）插入元素

mySet.insert(6);
mySet.insert(7);

（3）删除元素

mySet.erase(3);  // 删除值为 3 的元素

（4）查找元素

auto it = mySet.find(2);
if (it != mySet.end()) {
    std::cout << "Found: " << *it << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

（5）遍历元素

for (auto it = mySet.begin(); it != mySet.end(); ++it) {
    std::cout << *it << std::endl;
}

for (const auto& element : mySet) {
    std::cout << element << std::endl;
}

（7）其他常用操作

size()：返回 set 中元素的数量。
empty()：检查 set 是否为空。
clear()：清空 set 中的所有元素。
count()：返回 set 中特定元素的数量（对于 set，结果只能是 0 或 1）。

3.与unordered_set的区别

特性	set	unordered_set
底层实现	红黑树（平衡二叉搜索树）	哈希表
元素顺序	有序（默认升序）	无序
查找时间复杂度	O(log n)	平均O(1)，最坏O(n)
插入/删除时间复杂度	O(log n)	平均O(1)，最坏O(n)
内存占用	较低	较高（哈希表需要额外内存）