C++之SET容器

set 是 C++ STL (Standard Template Library) 中的一个关联容器。它存储唯一的元素，并且这些元素是自动排序的（默认情况下为升序）。set 内部通常实现为红黑树，这是一种自平衡二叉搜索树。

主要特点

1. 唯一性：set 容器不允许有重复的元素。
2. 排序：所有元素都是按照一定的顺序排列的，默认为升序。
3. 高效查找：由于内部使用了平衡二叉搜索树，所以插入、删除和查找操作的时间复杂度都为 O(log n)。
4. 双向迭代器：可以使用双向迭代器来遍历 set 容器中的元素。

常用操作

定义和初始化

#include <set>std::set<int> s; // 创建一个空的 set 容器
std::set<int> s = {1, 2, 3}; // 初始化 set 容器

插入元素

s.insert(5); // 插入单个元素
s.insert({6, 7}); // 插入多个元素

删除元素

s.erase(5); // 删除值为 5 的元素
s.erase(s.begin()); // 删除第一个元素

查找元素

auto it = s.find(3); // 查找值为 3 的元素，返回指向该元素的迭代器，如果找不到则返回 end()
if (it != s.end()) {std::cout << "Found " << *it << std::endl;
} else {std::cout << "Not found" << std::endl;
}

检查元素是否存在

if (s.count(3)) {std::cout << "3 is in the set." << std::endl;
} else {std::cout << "3 is not in the set." << std::endl;
}

获取元素数量

std::cout << "The set has " << s.size() << " elements." << std::endl;

清空集合

s.clear(); // 清空 set 容器

遍历集合

for (const auto& elem : s) {std::cout << elem << " ";
}
// 或者使用迭代器
for (auto it = s.begin(); it != s.end(); ++it) {std::cout << *it << " ";
}

自定义比较函数

如果你想改变 set 中元素的排序方式，可以提供一个自定义的比较函数或对象。例如，如果你想要创建一个降序的 set，你可以这样做：

#include <set>
#include <functional>std::set<int, std::greater<int>> descendingSet; // 创建一个降序的 set

或者使用自定义的比较类：

struct CustomCompare {bool operator()(int a, int b) const {return a > b; // 降序排序}
};std::set<int, CustomCompare> customSet;

总结

set 是一个非常有用的数据结构，当你需要存储唯一且有序的元素时，它是一个很好的选择。由于它的内部实现，它提供了高效的插入、删除和查找操作。