STL-set

简介

set 直译集合，为标准模板库容器的一部分

set拥有一个特性就是去重排序，且其底层为红黑树，set 所有元素为 const 特性，即不允许修改，但可以插入和删除

set为关联式容器，底层为红黑树（RB-Tree）

类模板

template<
    class Key,                              //数据类型
    class Compare = std::less<Key>,         //排序方法
    class Allocator = std::allocator<Key>   //分配器
> class set;

成员函数

由于 set 以 RB-Tree 为底层，又由于 set 开放的所有操作接口，RB-Tree 也都提供了，所以所有的 set 操作行为，都只是转调用 RB-Tree 的操作行为而已

迭代器

1. begin() - 返回指向 set 个元素的迭代器
2. end() - 返回指向 set 中最后一个元素之后的理论元素的迭代器
3. rbegin() - 返回指向 set 中最后一个元素的反向迭代器（反向开始）
4. rend() – 返回一个反向迭代器，指向 set 中第一个元素之前的理论元素
5. cbegin() - 返回指向 set 中第一个元素的const迭代器
6. cend() - 返回一个const迭代器，指向 set 中最后一个元素之后的理论元素
7. crbegin() – 返回指向 set 中最后一个元素的const反向迭代器（反向开始）
8. crend() - 返回指向 set 中第一个元素之前的理论元素的const反向迭代器

容量相关

1. size() - 返回 set 中元素数 O(1)
2. max_size() - 返回 set 可以容纳的最大元素数 O(1)
3. empty() - 当前 set 是否为空 O(1)

修改器相关

1. clear() - 清空所有元素，size()置 0
2. insert() - 插入一个或多个元素到指定位置
3. erase() - 删除指定位置元素
4. swap() - 交换元素
5. emplace() - 插入一个元素到指定位置，调用构造函数 (C++11)
6. emplace_hint() - 插入新元素到容器中尽可能接近于恰在 hint 前的位置，调用构造函数 (C++11)
7. extract() - 从另一容器释出结点 (C++17)
8. merge() - 从另一容器接合结点 (C++17)

元素查找相关

1. count() - 返回匹配特定键的元素数量 O(1)
2. find() - 寻找带有特定键的元素
3. equal_range() - 返回匹配特定键的元素范围
4. lower_bound() - 返回指向首个不小于给定键的元素的迭代器
5. upper_bound() - 返回指向首个大于给定键的元素的迭代器
6. contains() - 检查容器是否含有带特定键的元素 (C++20)

set迭代器详解

set的所有迭代器都是双向迭代器

const迭代器

set 所返回的迭代器都是 const 迭代器，只能对其操作，不能更改其指向的值，即：

set<int> v{ 1,2,3,4,5,6 };
auto i = v.begin(); //*i为1
i++;                //*i为2
*i = 100;           //error！

set的特性

为何 set 的插入删除效率比用其他序列容器高

因为对于关联容器来说，不需要做内存拷贝和内存移动，set 容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点

因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点

有关于 insert

set 的 insert 函数所返回的值类型为 pair<iterator,bool>，其中 bool 成员表明了key被插入之前，set中是否已存在相同的key，也就是说，如果set中已经存在相同key的元素，那么插入操作是会失败的，新的元素不会被插进去