【C++】set的使用

正文

序列式容器和关联式容器

我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

这里进行讲解的map和set，底层是红黑树，红黑树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

set系列的使⽤

set和multiset

在一个set中不会存在两个相等的元素。例如，如果试图插入一个已经存在于set中的元素，插入操作将被忽略。

multiset也是一个有序关联容器，但它允许存储多个相等的元素。这是它与set的主要区别。例如，同样的插入操作在multiset中的行为就不同。

tips：

在set中我们其实不太关注容量，vector/string这样的需要扩容的才会关注容量。

可以获取底层的仿函数。

……框架上这几个部分还是我们之前学过的那一套东西。我们关注的可能不到10个接口。

set类的介绍

注意源码这里用的是class T，而不是class K；

然后它支持一个仿函数，跟优先级队列类似。不支持比较大小，或者比较大小的方式不是我们想要的，我们就可以写一个仿函数。比如以前我们遇到的，存储类型是一个date*，是按地址比较的，但我们想要date *指向的日期进行比较，我们就可以自己写一个仿函数传过去。一般情况不需要我们传，因为默认用库里的less；

less函数：

功能：在 C++ 标准库中，less是一个函数对象（function object），也被称为仿函数（functor）。它用于比较两个对象，以确定第一个对象是否小于第二个对象。这在许多需要进行排序或元素比较的场景中非常有用，比如在关联容器（如std::set、std::map、std::multiset、std::multimap）中定义元素的顺序。

定义位置与头文件：less定义在<functional>头文件中。当你需要使用less函数对象时，需要包含这个头文件。

**工作原理：**less是一个模板类，其模板参数是要比较的对象类型。例如，less用于比较两个整数。它实现了一个函数调用运算符（operator()），当使用less的对象进行函数调用时（就像调用普通函数一样），它会使用<运算符来比较两个传入的对象，并返回比较结果（true或false）。

例如，对于less类型的对象comp，comp(a, b)实际上等价于a < b，其中a和b是整数。

在容器中的使用：

#include <iostream>
#include <set>
#include <functional>
int main() {
    std::set<int, std::less<int>> mySet;
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(2);
    for (int num : mySet) {
       std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

在这个例子中，std::set<int, std::less>表示创建一个存储整数的集合mySet，其中元素的比较规则是由std::less定义的，也就是按照整数的大小升序排列。当插入元素3、1、2后，集合中的元素会自动按照升序排序，遍历集合时会输出1 2 3。

与其他比较方式的对比：

相比于直接使用<运算符，less函数对象的优点在于它是一个可传递的对象，可以在模板函数或模板类中作为参数传递，从而增加了代码的灵活性和通用性。例如，在自定义的排序算法或者自定义的容器类中，可以接收一个less类型的参数来确定比较规则，而不是硬编码<运算符。

同时，less可以被继承或者特化，以满足更复杂的比较需求。比如，对于自定义的类，你可以继承less并重新定义其operator()函数，以根据类的特定成员进行比较。

然后就是容器都有的空间配置器。set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。（⼀般情况下，我们都不需要传后两个模版参数。）

set底层是⽤红⿊树实现，增删查效率是 O(logN)，迭代器遍历是⾛的搜索树的中序，所以是有序的。

vector/list等容器的使⽤，STL容器接⼝设计，⾼度相似.

set的构造和迭代器

我们看看文档：

第一个可以认为是无参的，两个参数给了缺省值，所以是默认构造。

第二个版本就是支持显式地传空间配置器的。

第三个是用迭代器区间初始化，这个也用的比较多，可以是set自己容器的，也可以是其他容器的。

然后四、五是两个拷贝构造。

六、七是两个移动构造，日后再提。

最后是initializer list。

在 C++ 中，initializer list（初始化列表）是一种用于初始化对象的语法机制。它允许你使用花括号{}来包含一个或多个初始化值，这些值可以用于初始化数组、结构体、类的对象，以及标准容器（如std::vector、std::list等）等多种数据结构。

int arr[] = {1, 2, 3};//初始化数组

struct Point {
   int x;
   int y;
};
Point p = {1, 2};//初始化结构体

class MyClass {
public:
   MyClass(int a, int b) : m_a(a), m_b(b) {}
private:
   int m_a;
   int m_b;
};
MyClass obj = {1, 2};//初始化类对象（构造函数使用）：

#include <vector>
std::vector<int> v = {1, 2, 3};//在标准容器中的应用

工作原理：

当使用初始化列表时，编译器会根据对象的类型和初始化列表中的元素个数及类型，调用相应的构造函数或者初始化函数。对于类的对象，编译器会优先查找能够匹配初始化列表中元素个数和类型的构造函数。如果找不到完全匹配的构造函数，可能会尝试进行隐式类型转换或者报错。

例如，在std::vector的初始化中，std::vector类有一个接受初始化列表的构造函数，当使用{1, 2, 3}初始化时，就会调用这个构造函数来创建一个包含指定元素的vector。

优点：

简洁性：提供了一种简洁明了的方式来初始化多种类型的对象，避免了繁琐的逐个赋值操作。
初始化顺序明确：在初始化类对象时，通过初始化列表可以明确成员变量的初始化顺序，这对于一些需要特定初始化顺序的对象（如包含引用成员或 const 成员的对象）非常重要。
支持聚合初始化：对于聚合类型（如数组、结构体等简单的数据结构），可以直接进行初始化，方便了数据结构的创建。

迭代器

容器的迭代器严格来说也是分类型的，主要分为三种：单向、双向和随机。

vector/string/deque这些就是随机迭代器，随机的特征是支持+、-。

链表就是典型的双向迭代器的情况。

map/set也算是双向迭代器，可以++，–。

单链表和哈希表就是单向迭代器。

而且从其支持rbegin/rend也可以看出是双向。

只有begin、end没有rbegin、rend。

可以看到对比。

析构我们不关注。

拷贝构造、赋值重载，一颗树拷贝给哦另一颗树，按理来说是深拷贝。但我们也不关注。

增删查改

set不支持改。因为会破坏掉搜索二叉树的性质。

增的核心接口是insert。删是erase，find是查。

这个value_type我们到外面看：

这是为了跟map保持一致，set这俩其实都是key。

所以这个insert的就是一个key，这个没见过的返回值，我们之后讲解map的时候再提。&&是右值引用，也以后再说。

下面两个是在某个位置插入，但一般我们不会用这种在某个位置插入的概念。

然后是可以插入一段迭代器区间。

最后注意，还可以插入一个initializer_list。

可以看到我们无法插入两个5.

const迭代器不支持修改，但是我们发现set的普通迭代器也不支持修改：

我们可以通过控制仿函数来让它变成去重+降序。默认是less，也就是说插入的值与当前值比较，返回为真就走左边。

我们传一个greater，比当前大为真。

所以这样中序遍历就是有序的。

所以这样就是降序的了。

在底层，我们只有less，怎么进行三种情况，大于小于和等于的区分呢？

我们看到， 可以改成这样，顺序反过来，就都是小于的比较了。

可以看到，新功能c++11还支持这样插入（构造也可以这样）：

它底层其实去调insert一个个插入。其实就是套了一层。

所以如果我们传冗余，也会被去重。

不同数据类型

set除了支持整型，还可以字符串：

set<string> strset = { "sort","insert","add" };

我们这样初始化，走的就是下面这个构造函数的隐式类型转换：

任何值要转换成另一个值只要支持这个单参数的构造函数都支持隐式类型的转换。

语法逻辑上说，是用{“sort”,“insert”,“add”}去构造一个set，再去拷贝构造。编译器会直接将其简化成构造。

也可以这样写，更贴近原型，语法上就是调构造了：

set<string> strset({"sort","insert","add"});

两个结果上都是直接调构造，语义不一样。

那么，这个string类型的，底层是如何比较的？

按照ascll码的大小顺序遍历的。

打印出来的顺序可以见得：

查找

找到了返回迭代器，没有找到，会返回end。

end是最后一个数据的下一个位置。

我们可以想到，它的find并不是遍历查找。而是比较，比当前值大往右走，比当前值小往左走。

因为set是平衡树，所以最多找高度次，是logN

删

最多支持三个版本的删除：

第一个，删除一个迭代器的位置；

第二个，也可以给个值然后去删除它,size_type是个无符号整型；

也就是删除成功返回1，没删除成功返回0.

那么，既然结果只有0或1，为什么不用bool值作为返回值类型呢？

因为这是为了兼容multiset，因为其允许冗余，这个值可能存在多个，所以不用bool；

第三个，还可以删除一个迭代器区间。

我们思考一下，删除最小值会怎么删？

begin和end一定是左闭右开，默认情况下我们不调整仿函数，也就是升序，那么begin()就是最小值：

然后我们再测试输入一个值，让它删：

我们可以将这种理解为其实是这样的代码：

int x;
cin >> x;
auto pos = s.find(x);
if (pos != s.end())
{
	s.erase(pos);
}
//……

也就是，传值删除的erase版本相当于封装了一个传值的find（返回一个迭代器）和一个传迭代器版本的erase。

这里erase之后，迭代器失效吗？

失效。这里失效有两种情况，要结合底层来看。

第一种情况：

set的迭代器里面也包含一个结点的指针。结点都被删了，结点的指针就是野指针了。

第二种情况：

搜索树里删除结点有两种情况，一种是直接删，另一种是替代它删除。

这种，虽然替代它删除了，这个迭代器还能访问，但是意义已经变了。

这里和vector很相似，vector中删除一个位置，后面的数据整体前移，意义也已经变了已经不是原来那个值了。有些编译器可能会进行强制的检查，去访问就报错。

我们可以看到，vs下是不允许我们去访问这个即使替代法删除但意义变了的迭代器的：

查找效率

查找有两种方式，一种是用库里面的find，一种是用set自带的find。

后者效率更好，因为它是按照搜索树的规则走到，小的往左走，大的往右走。最差走高度次，也就是logN；

算法库里的是遍历，它不管底层是什么容器所有容器都可以用迭代器区间查找。O(N).可以说是暴力查找，一般写给vector/list偶尔查找的，注意的是vector/list这两种容器本身就不适合大量查找，而应该用搜索树这样的结构才会大量查找效率高！

交换

支持两个树进行swap，会怎么swap两棵树呢？

直接swap根结点就可以了。效率非常高。（库里面的swap效率也会很高，原因在以后学习c++11时再说）

clear——清理掉所有的数据

emplace，涉及右值引用和模版的可变参数，以后再说。

count

返回一个值的个数。也是为了跟multiset进行对称。

不过，回想一下我们的find函数，其实很不方便：

返回的都是迭代器，所以我们还需要有一步，也就是检查返回值是否为end()，如果不是才是找到了，是就是没找到。

如果用count来确定值在不在会非常方便，因为对于set来说，count返回的要么1要么0，找到了返回1找不到返回0，刚好对应bool值（0为假非0为真）。

lower_bound和upper_bound

这俩的区别值得注意：前者返回大于等于val位置的迭代器，后者返回大于val位置的迭代器。

这是用来找一段区间的。

记住，在STL中，只要是迭代器区间，必须是左闭右开。

比如我们现在要求将某段区间删掉：

erase支持一个迭代器区间删除，而且要给的是左闭右开的迭代器区间。

（设计巧妙：）

再试一下[25,55]这个区间：

总之就是我们要删哪段区间，就给哪段区间的值给对应的lower_bound和upper_bound，然后得到的迭代器给erase进行删除，得到的就是我们要删除的结果。（设计之巧妙）

无论是删除还是查找还是遍历我们都需要的是左闭右开的区间，而lower_bound和upper_bound就能帮我们找到左闭右开的区间。

这俩在查找时也是按照搜索树的规则来找的。（比当前值小往左走，大往右走）

如果这种情况，我们在这棵树里找5：

第一轮查找找到空指针，我们知道5是不在这棵树里的，其实它的底层是一个三叉链，也就是右指向parent的指针，所以往上走回去，发现parent4比5小，再往上走，6比5大。

所以这俩也是属于log级别的算法。

那么set的基本内容到此结束。敬请期待后面关于multiset、map的更多内容。