C++标准模板库（STL）集合 set 关联容器

陈一男学习网站[ ChenYinan.com ] - CCF - NOI - 菜鸟教程 - 编程题库 - C++语言 - API

一. 定义与基本概念

在C++的标准模板库（STL）中，集合（set）是一种关联容器，位于<set>头文件中。用于存储唯一的元素，并且这些元素会按照特定的顺序（默认是升序）自动排列。set内部通常是基于红黑树（一种自平衡二叉搜索树）实现的，这使得它在插入、删除和查找操作上具有较高的效率。

二. 创建set对象

默认构造：可以创建一个空的set对象。

std::set<int> mySet; // 创建了一个空的、用于存储int类型元素的set

从其他容器初始化（范围构造）：可以使用另一个容器（如数组、vector等）中的元素来初始化set。

int arr[] = {3, 1, 2}; 
std::vector<int> v = {5, 4, 6}; 
std::set<int> mySet1(arr, arr + sizeof(arr)/sizeof(arr[0])); 
std::set<int> mySet2(v.begin(), v.end());

这里分别使用数组arr和vector v中的元素来初始化set对象mySet1和mySet2。在初始化过程中，重复的元素会被自动去除，因为set只存储唯一的元素。

三. set的基本操作

插入元素

insert()方法：用于向set中插入元素。

std::set<int> mySet; 
mySet.insert(3); 
mySet.insert(1); 
mySet.insert(2);

由于set会自动排序元素，插入后的set中的元素顺序为{1, 2, 3}。

查找元素

find()方法：用于在set中查找指定元素。如果找到元素，则返回指向该元素的迭代器；如果未找到，则返回set的end()迭代器。

std::set<int> mySet = {1, 2, 3}; 
auto it = mySet.find(2); 
if (it!= mySet.end()) {
    std::cout << "Element found" << std::endl; 
} else { 
    std::cout << "Element not found" << std::endl;
}

删除元素

erase()方法：可以删除set中的指定元素。可以通过元素值或者迭代器来指定要删除的元素。

std::set<int> mySet = {1, 2, 3}; 
mySet.erase(2);

这里通过元素值删除了元素2；也可以使用迭代器删除元素。

auto it = mySet.find(3); 
if (it!= mySet.end()) {
    mySet.erase(it);
}

遍历set

由于set中的元素是有序的，可以使用迭代器遍历set来获取元素。

std::set<int> mySet = {1, 3, 2}; 
for (auto it = mySet.begin(); it!= mySet.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl; //输出结果为1 2 3

获取set的大小：使用size()方法可以获取set中元素的个数。

std::set<int> mySet = {1, 2, 3}; 
std::cout << mySet.size() << std::endl;//会输出3，表示set中有3个元素

四. set的特性与注意事项

元素的唯一性：set中的元素必须是唯一的。如果尝试插入一个已经存在于set中的元素，插入操作将不会改变set的内容。

std::set<int> mySet = {1, 2}; 
mySet.insert(2);//执行插入操作后，mySet仍然为{1, 2}

排序规则：默认情况下，set按照元素的<（小于）运算符进行排序。对于自定义类型，如果要存储在set中，需要定义<运算符或者提供自定义的比较函数（在set的模板参数中指定）。

struct Person {
    std::string name;
    int age;
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};
std::set<Person> people;
Person p1 = {"Alice", 25};
Person p2 = {"Bob", 30};
people.insert(p1);
people.insert(p2);

时间复杂度：插入、删除和查找操作的平均时间复杂度都是$O(log n)$，其中n是set中的元素个数。这是因为set基于红黑树实现，红黑树的高度始终保持在$O(log n)$的范围内，从而保证了这些操作的高效性。

与其他容器的比较

与vector相比，vector是顺序容器，元素的存储顺序取决于插入顺序，并且允许元素重复。而set是关联容器，元素自动排序且唯一。

与map相比，map是键 - 值对的容器，而set只存储单个元素。虽然在实现上有相似之处（都基于红黑树），但用途不同。例如，std::map<int, std::string>用于存储键（int类型）和值（string类型）的映射关系，而std::set<int>只关注元素（int类型）本身的存储和管理。