大家好，我是凉糖。今天继续讲C++STL，今天讲set。为了写这篇文章，老梁花了一上午的时间阅读了网上大部分关于设定的博文。看完之后发现和想象中的一样。上来就说说怎么创建set，set里面有什么功能，还有标准的技术文档。当然，这些东西对于老手来说是没有问题的，一眼就能找到自己想要的东西，但是对于新手来说，可能就显得有些吃力了。一定是脑洞大开，于是老梁另辟蹊径。先不列举术语和api文档，而是以叙述的形式说说它的前因后果，前世今生。如果喜欢这类文章，不妨给老梁点个赞，给老梁一些正面的反馈。设置了什么？如果你学过几种编程语言，你会发现虽然每种主要语言的特点都大不相同，但总有那么几个东西是反复出现的。虽然它们在不同语言中的名字不同，底层实现也不同，但是它们做的事情是相似的。在C++中，这些东西的名字分别是vector、set、map，它们有一个共同的名字叫STL（StandardTemplateLibrary）容器。估计很多同学看到container这个词有点懵，会觉得我知道container是什么意思，但是不知道你这里的container是什么意思。容器在现实中就是用来存放东西的容器，在编程语言中也是一样，只是存放的不再是实际的物品，而是抽象的变量。那么问题来了，同一个容器，vector、set、map有什么区别？上一篇文章讲过，vector类似于数组，可以以线性的形式存储元素。与set、map和vector不同，它们不是线性容器，而是关联容器。看到新名词，估计有些同学要开悟了，不用着急开悟。其实我们可以大胆猜测一下。从字面上看，所谓关联就是将两个事物联系起来。那么新的问题又出现了，这个连接是什么？我们如何建立联系，为什么要这样做？这几个问题甚至可能吓到许多退伍军人。要说清楚这一点，我们需要先说说set的作用。我们从现象入手，逐步了解本质。我们有一个vector，它可以顺序存储数据，可以随意插入数据。很方便，那么除了这些我们还需要什么呢？当我们的数据多了，自然会有一个需求，就是找数据。数据被收集和存储后，总是被使用。既然要用，自然要搜一搜。面对查找需求，vector是不行的，因为里面的数据是线性排列的，排成一行，需要一个一个查找。数据少还好，数据多了就明显忙不过来了。那么如何快速搜索呢？数据一定要有顺序，有顺序查找就会快。比如同一行数字，如果都是有序的，我们可以用二分法查找，那么复杂度会突然从1增加到2。看似数学公式的一个小变化，实际上是一个巨大的差距，尤其是在海量数据的情况下。数据18,446,744,073,709,551,615够大吗？用科学计数法表示，比地球上的沙子还多。如此海量的数据，即使计算机运行速度再快，也需要永远遍历。如果使用二分法，只需要查找64次。和64这个比地球上的沙子还多的数字相比，中间的差距可想而知。所以我们要想快速搜索，就必须让数据有顺序。有了顺序，我们就可以使用二分法来快速查找了。如果我们要存的是一个数字，当然好办，自然是有序的。如果不是数字，其实很简单。我们可以给它分配一个id，给它们一个编号，用这个编号进行排序，或者根据我们的需要实现排序逻辑。这不是问题。真正的问题出在数据结构上，虽然二分法很快，但我们不能直接使用它。因为我们不能以线性形式存储数据，如果这样做，当我们要插入元素时，就会涉及到元素在数组中的移动。这一步，则插入的复杂度退化成了。所以我们需要使用二分查找的方法，但是不能使用数组，这就需要我们使用一种新的数据结构。估计学过算法或者看过老梁以前文章的同学应该猜到这样的数据结构是树，准确的说是二叉搜索树。老梁从网上找了一张图片。二叉搜索树是这样的：它看起来很普通，但是它有一个非常强大的性质，就是对于任意一个节点，它满足它的左子树的所有元素都大于它的Small，右子树的所有元素都是比它大。当我们想找到某个元素时，它非常强大。我们只需要利用这个属性从根节点从左到右遍历，找到目标即可。理想情况下，我们每进行一次分支选择，就相当于丢弃了一半的元素，也就是减少了一半的搜索空间。所以它实际上是一个具有相同复杂度的二分查找算法。有了这样的树结构，插入元素的问题就解决了，因为树上的元素都是离散的，我们插入节点不会影响其他节点。但是这样会产生另外一个问题，就是插入元素会破坏元素在树上的分布。例如，如果我们一直插入一个小于树上所有元素的数，那么这个数将一直被添加到搜索树的最左边。长此以往，树左边的元素就会过多，影响元素Lookup性能。幸运的是，这个问题并非无法解决。我们可以设计一些算法，让树在添加或删除元素时能够自我修复平衡，保持树上元素的平衡。从这个出发点设计的算法很多，所以自平衡二叉搜索树的种类也很多。比如常见的AVL、红黑树、SBT等。在这众多的算法中，公认红黑树的统计性能最好，所以set、map等关联容器的底层往往都是用红黑树来写的。那么到这里，整个逻辑就闭合了，终于可以从头回答问题了。什么是套装？集合是用红黑树实现的关联容器，可以有序地存储数据，并提供快速查找、增删改查的功能。集合有什么用？了解什么是集合之后，下一个问题就是它的用途是什么。其实从某种程度上来说，这两个问题是一个问题。了解了它的设计原理和设计思路之后，你自然会明白它能做什么。最大的功能是搜索数据。由于集合的底层是通过红黑树实现的，所以红黑树的本质是二叉搜索树。既然是二叉查找树，就要保证key唯一，所以集合中的元素也必须唯一。那么我们就可以利用这个属性来构建一个容器，保证容器中的元素是唯一的，并提供查询功能。举个简单的例子，假设开发了一个新功能，需要上线测试。为了防止除测试人员以外的其他用户遇到BUG，影响用户体验，一般的常规措施是维护一个白名单。即只有列表中的人可以看到这个功能，其他用户还是按照老逻辑。这样的白名单用set是很合适的。set的套路使用代码也很简单，只有几行：#include
