C++ set到底是什么

1、set是什么

如果大家学过几门编程语言，会发现各大语言的特性虽然迥异，但是总有几个东西反复出现刷存在感。它们在各个语言当中的名字虽然不太一样，底层实现也不同，但是做的事情差不多。

在C++当中，这几个东西的名字叫做vector、set和map，它们有一个共同的名字叫做STL（标准模板库）容器。

估计不少同学看到容器这两个字脑袋有点发蒙，会有一种我当然知道容器是什么意思，但是我不知道你这里说容器是什么意思的感觉。现实中的容器是用来存储东西的器皿，在编程语言当中，也是一样，只不过存储的不再是实际的物品而是抽象的变量。

那么问题来了，同样是容器，vector、set、map这些又有什么区别呢？前面的文章里说过，vector类似于数组，可以以线性的形式存储元素。而set、map和vector不同，它们不是线性的容器，而是关联式的容器。

看到新的术语，估计又有同学要发蒙了，先别着急发蒙。其实我们可以大胆猜测一下，从字面理解，所谓关联式说白了也就是把两个事物关联起来。那么新的问题又来了，这个关联是什么？我们怎么做的关联，又为什么要做关联？

这几个问题估计连很多老鸟都能唬住。

要解释清楚这个，就需要先来说说set的功能。我们从现象入手去逐渐理解本质。

我们有了vector，可以顺序地存储数据，还可以随心所欲地插入数据非常的方便，那么除了这些之外我们还需要什么呢？

当拥有的数据多了之后，就会产生一个很自然的需求，就是查找数据。数据搜集存储起来之后总是要拿来用的，既然要拿出来用，自然就需要查找。在查找这个需求面前，vector很不够看，因为它当中的数据都是线性排列的，排成一排，需要一个一个查找。数据少还行，如果数据多了，显然忙不过来。

那怎样查找才快呢？

得让数据有顺序，有了顺序查找就快了。比如同样是一行数，如果它们都是有序的，我们就可以通过二分法来查找了，那么复杂度就陡然地从提升到了。看起来好像只是数学公式上的一点微小变化，实际上这两者之间的差距大的离谱，尤其是在海量数据的情况下。

18,446,744,073,709,551,615这个数据够大吗？表示成科学记数法是，比地球上的沙子都多。这么庞大的数据要是一个一个遍历过来真得天荒地老，即使计算机运行速度超快也不行。如果用二分法呢，只需要查找64次。64和一个比地球上沙子数量都大的数相比，这中间的差距可想而知。

所以我们想要快速查找，就必须要让数据有顺序，有了顺序就可以用二分法快速查找。如果我们要存的数是数字，当然很好办，天然有序。如果不是数字其实也很简单，我们可以给它赋上一个id，给它们一个编号，用这个编号来排序，或者是根据我们的需要自己实现排序的逻辑，这都不是问题。

真正的问题在于数据结构，虽然二分法很快，但我们并不能直接使用它。因为我们不能以线性的形式来存储数据，如果我们这样做，当我们要插入元素的时候，就会涉及数组中元素的移动。这一移动，那么插入的复杂度又蜕化成了。

所以我们需要使用二分查找的方法，但又不能使用数组，这就需要我们使用一个新的数据结构。估计学过算法或者是看过老梁之前文章的同学应该已经猜到了，这样的数据结构就是树，准确得说是二叉搜索树。

老梁从网上找来一张图，二叉搜索树长这样：

它看起来很普通，但有一个很牛的性质，就是对于任意一个节点，它都满足它左子树的所有元素都比它小，右子树的所有元素都比它大。当我们想要查找某一个元素的时候就很强大了，我们只需要利用这个性质从根节点开始往左往右遍历，就能找到目标了。

在理想情况下，我们每次进行分支选择的时候，都等价于舍弃掉了一半的元素，也就是将搜索空间缩小了一半。所以它其实也是一个二分查找算法，复杂度同样是。

有了这样的树结构，插入元素的问题就解决了，因为树上的元素都是离散的，我们插入节点并不会影响其他节点。但这又会产生另外一个问题，就是插入元素会破坏树上元素的分布。比如我们一直插入一个比树上所有元素都要小的数，那么这个数会一直被添加在搜索树的最左侧，长此以往就会导致这棵树的左侧元素特别多，这样就会影响元素查找的性能。

好在这个问题并不是无解的，我们可以设计一些算法让树在元素添加或者删除的时候能够自我修复平衡性，一直保持树上元素的平衡。

从这个出发点设计出来的算法有很多，所以自平衡二叉搜索树有很多种。比如常见的AVL、红黑树、SBT等等。在这许多算法当中，公认红黑树的统计性能最好，所以往往set、map这些关联式容器的底层都是用红黑树写的。

所以到这里，整个逻辑就闭合上了，我们也终于可以回答那个一开始的问题。set是个啥？

set是一个用红黑树实现的关联式容器，它可以有序地存储数据，提供快速的查找、添加删除的功能。

2、set有什么用

搞明白了set是个啥，接下来的问题就是它有什么用。

其实某种程度上来说这两个问题是一个问题，理解了它的设计原理和设计思路，自然也就明白了它能干什么。

最大的功能就是数据的查找，由于set底层是通过红黑树实现的，红黑树的本质是二叉搜索树。既然是二叉搜索树就需要保证key唯一，所以set中的元素也必须是唯一的。那么我们就可以利用这个性质来构建一个容器，保证容器内的元素是唯一的，并提供查询功能。

举个简单的例子，比如说开发了一个新功能要上线测试。为了防止除测试人员之外的其他用户遇到bug影响用户体验，所以一般常规措施都是维护一个白名单。也就是在名单中的人才能看到这个特性，其他用户还是走老的逻辑。这样的一个白名单用set就非常合适。

set的常规使用代码也非常简单，也就只有几行：

#include <set>

// 创建set
std::set<T> st;

// 插入元素
T t = T();
st.insert(t);

// 查找元素
if (st.count(t)) {
    
}

当然这个只是最常规最常规的用法，除了这些之外，set还有很多进阶用法，以及不少注意事项。由于篇幅原因，我们下一篇文章再和大家详细聊聊。

注：文章转自微信公众号：Coder梁（ID：Coder_LT）