C++——STL标准模板库——容器详解——set

一、基本概念

set容器是一种具备自动排序功能的集合，默认递增排序；元素无法直接修改，且不能重复；另一个版本叫做multiset，允许存在重复元素，其他功能和性质一样。

set容器底层结构一般为自平衡二叉搜索树，能够保证在O(logn)时间复杂度内完成删除、搜索、插入等操作。

set容器提供常量双向迭代器，不支持随机访问，不允许修改现有元素

二、构造函数

1、set<T>s;? ? ? ? ? ? ? ? ????????????????????????????????默认构造函数

2、set<T>s={initializer _list}? ? ? ? ? ? ? ? ? ? ? ?初始化列表构造

3、set<T>s(set<T>& other);? ? ? ????????????????复制构造函数

4、set<T>s(set<T>&& other);? ? ? ? ? ? ? ? ? ? 移动构造函数

5、set<T>s(iterator first,iterator last);? ? ? ? 迭代器范围构造

6、set<T,Key_Compare>s(set<T>::key_comp& Par)? ? ? ? 指定排序方式的构造函数，当构造自定义类型的容器时，必须指定排序方式。Key_Compare是一个指定排序方式的自定义类型，一般为类或者结构体，封装了定义排序方式的仿函数。例如指定递减排序：

class MyCompare {
public:
	bool operator()(const int&a, const int&b)const {
		return a > b;
	}
};

set<int,MyCompare> s;        //对象后面参数省略
set<int,Mycompare> s1(s.key_comp());

在例子中模板参数列表中显式指定排序类型时，实例化对象参数可省略。?

set容器和前面其他容器一样，都重载了多种构造方式，可根据实际情况有选择使用。

三、成员函数

（一）迭代器函数

set<T>::iterator begin();? ? ? ? ? ? ? ? ? ? ? ? 返回指向容器首元素的迭代器

set<T>::iterator end();? ? ? ? ? ? ? ? ? ? ? ? ? ?返回指向容器尾元素后面一个未知的迭代器

set容器提供的迭代器是双向迭代器，不支持随机访问。当然set也包括反向版本rbegin()、rend()，常量迭代器cbegin()、cend()等。

set容器提供的迭代器本质上都是常量迭代器，所以set容器不允许修改当前元素。

（二）大小相关函数

bool set<T>::empty();? ? ? ? ? ? ? ? ? ? ? ? 判断容器是否为空

size_t set<T>::size();? ? ? ? ? ? ? ? ? ? ? ? ?返回容器当前元素个数

size_t set<T>::max_size();? ? ? ? ? ? ? ? 返回set容器能够容纳元素的最大值

set容器没有容量的概念

（三）插入函数

STL源码中存在两种返回值的insert()函数，例：

1、iterator insert(T&value);?

2、Pair insert(T&value);

第二个版本的返回类型Pair为一个组合类型，包含<iterator,bool>两个结果，这种组合类型叫做对组；bool类型判断是否插入成功，iterator类型指向插入位置的迭代器，如果插入不成功指向end()。STL中通过条件编译实现了：set容器调用版本2，multiset容器调用版本1，从而实现了set容器元素唯一，multiset容器元素可重复。

insert();函数重载了以下几种插入方式。

insert(iterator pos,T&value);? ? ? ? ? ? ? ? 迭代器指定插入位置，复制插入元素

insert(iterator pos,T&&value);? ? ? ? ? ? ?迭代器指定插入位置，移动插入元素

insert(iterator first,iterator last);? ? ? ? ? ?插入区间内的元素

insert(initializer _list);? ? ? ? ? ? ? ? ? ? ? ? ? ?插入初始化列表

（四）删除函数

size_t erase(const T&value);? ? ? ? ? ? ? ? 删除指定值，set返回1，multiset返回删除个数；

iterator erase(iterator pos);? ? ? ? ? ? ? ? ? ?删除指定位置的值，返回指向该位置迭代器

iterator erase(iterator first,iterator last);删除指定区间，返回last；

四、使用注意事项

优势：

1. 自动排序：std::set?中的元素自动根据其值进行排序。你不需要像使用数组或链表那样手动排序。
2. 唯一性：std::set?只存储唯一的元素，这样可以确保数据的一致性，不会出现重复的数据。
3. 高效的查找操作：由于?std::set?实现为红黑树，其查找、插入和删除操作的平均时间复杂度为 O(log n)。
4. 标准容器：std::set?是 C++ 标准库的一部分，因此与其它标准库组件有良好的兼容性。

劣势：

1. 值的不可变性：一旦将一个元素插入到?std::set?中，你就不能更改该元素的值。如果你需要修改一个元素的值，你需要先删除旧的元素，然后插入新的元素。
2. 内存使用：由于?std::set?需要为每个元素分配内存并维护一棵红黑树，所以它的内存使用可能会比其它容器（如数组或向量）更高。

使用时需要注意的事项：

1. 元素的唯一性：由于?std::set?存储唯一的元素，如果你尝试插入一个已经存在的元素，std::set?将不会做任何事情，即不会插入重复的元素。因此，在插入元素之前，你可能需要检查元素是否已经存在于 set 中。
2. 迭代器的稳定性：std::set?的迭代器在删除元素后可能会失效。如果你在迭代过程中删除元素，可能会导致未定义的行为。为了安全地删除元素，你可以先保存要删除元素的迭代器，然后在迭代完成后再进行删除。
3. 与其它容器的交互：当与其它容器（如?std::vector?或?std::list）进行交互时，需要注意?std::set?的特性。例如，将一个元素从一个 set 移动到另一个 set 或从 set 移动到另一个容器时，需要特别小心。
4. 自定义比较函数：std::set?需要一个比较函数来确定元素的排序和唯一性。确保你提供的比较函数是正确的，并且对于所有可能的输入都能产生一致的结果。

迭代器迭代过程删除元素实例

#include <iostream>  
#include <set>  
  
int main() {  
    std::set<int> my_set = {1, 2, 3, 4, 5};  
      
    for (auto it = my_set.begin(); it != my_set.end(); ) {  
        if (*it == 3) {  
            it = my_set.erase(it); // 保存迭代器并删除元素  
        } else {  
            ++it; // 继续迭代  
        }  
    }  
      
    // 输出 set 中的元素  
    for (const auto& elem : my_set) {  
        std::cout << elem << " ";  
    }  
    std::cout << std::endl;  
      
    return 0;  
}