二、set

1.set的自我介绍

 <li>set意思是集合，从初中就接触到了集合的概念，真是的好东西。set是一个内部自动有序且不含重复元素的容器。</li>
 <li>set是一种关联式容器，是用来存储同一种数据类型的数据类型，有点绕口，就是sety也就是集合里里面要不然全部装int型的要不然全部装double型的要不然....就是这个意思。并且能从这个同一种数据类型构成的集合中取出元素，而且set中的每个元素都是唯一的，不能重复，好像是数学里集合概念中的唯一性（哈哈哈，强大的数学功底）。更令人欣慰的是，能根据元素的值进行自动排序。</li>
 <li>一个集合（set）是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集 合中的元素按一定的顺序排列，并被作为集合中的实例。如果你需要一个键/值对（pair）来存储数据，map是一个更好的选择。一个集合通过一个链表来组 织，在插入操作和删除操作上比向量（vector）快，但查找或添加末尾的元素时会有些慢。（原因后文简单说说）</li>
 <li>要注意的是，set中书元素的值不能被直接改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树，即一种自平衡二叉树（以后会讲到啥叫平衡二叉树~~）：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。</li>

2.set的定义

 <li>单独定义一个set:</li>

          set<typename> setname;

 <li>其定义和大部分STL的定义都差不多，这里的typename依然一样可以是任何基本类型，比如int,double,char，结构体啊，还有STL的标准容器vector,set,queue啊等等。</li>
 <li>需要注意的是，比如<em>set&lt;vector&lt;int&gt; &gt; setname;</em>两个'&gt;‘之间一定要加上空格，否则会编译错误，原因是会误以为位移运算（详见上篇）。</li>
 <li>特别的，set数组：</li>

set<typename> Arrayname[arraySize];

比如，set<int>a[100];定义了一个set型的数组，数组中每一个数都是一个集合，每一个集合里都是int型的值。

3.set容器内元素的访问形式

 <li>只有一种！</li>

          hhh,选择

          困难症的同学是不是很开森呢？

          只能通过迭代器访问（啥叫迭代器？详见上篇）：

          set<typename>::iterator it;（这个也不多说了，和vector是一模一样滴）

          比如，set<int>::iterator it;

          set<double>::iterator it;

          同样的，和vector一样可以通过*it来访问set里的元素啦，忍不住再唠叨一句，迭代器就是指针。

4.set中的基本操作

 <li>insert(x)：    插入元素，并且自动递增排序噢，而且去重，时间复杂度O(logN)，N为set中元素的个数。</li>
 <li>insert(first,second)：    将定位器first到second之间的元素插入到set中，返回值是void</li>
 <li>find(value)：    返回set中对应值为value的迭代器，时间复杂度未O(logN)!!后文会重点讲（见下文5.set的注意点和优良特性），有助于加深理解O(logN)，举一反三，以后也不过多强调了qwq。</li>
 <li>begin():    返回set容器的第一个元素//桥黑板！！begin() 和 end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空</li>
 <li>end()：    返回set容器的最后一个元素</li>
 <li>clear()：    删除set容器中的所有的元素//时间复杂度O(N)</li>
 <li>empty()：    判断set容器是否为空</li>
 <li>max_size()：    返回set容器可能包含的元素最大个数</li>
 <li>size() ：    返回当前set容器中的元素个数//时间复杂度O(1),贼快！</li>
 <li>rbegin：    返回的值和end()相同</li>
 <li>rend()：    返回的值和rbegin()相同</li>
 <li>count()：    顾名思义嘛，用来查找set中某个某个键值出现的次数。但是，这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。（小技巧）</li>
 <li>erase(iterator)：    删除迭代器iterator指向的值//时间复杂度O(1),贼快！注意和erase(value)不同噢</li>
 <li>erase(first,second)：    删除定位器first和second之间的值（美国人的思维是左闭右开，最后一次强调）</li>
 <li>erase(value)：    删除值为value的元素，时间复杂度O(logN)//桥黑板！！set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。</li>
 <li>lower_bound(key_value)：    返回第一个大于等于key_value的定位器</li>
 <li>upper_bound(key_value)：    返回最后一个大于等于key_value的定位器//二分啦！</li>

5.set的注意点和优良特性

（加深对set的理解,初学者可以先跳过此部分）

 

 <li>不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，则插入新元素</li>
 <li>不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取，而且从迭代器角度来看，元素值是常数</li>
 <li>元素比较动作只能用于型别相同的容器(即元素和排序准则必须相同)

因为set中重写比较函数的用的真还不多，所以就不细细的讲了，等降到后面的priority_queue的时候，我会重新讲一下结构体的比较函数（其实也叫优先级设置）。

从原型可以看出，可以看出比较函数对象及内存分配器采用的是默认参数，因此如果未指定，它们将采用系统默认方式，
另外，利用原型，可以有效地辅助分析创建对象的几种方式。

之前提到了set（map也一样哈）的插入删除效率比用其他序列容器高，简单的讲set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。需要插入或删除，只要改变指针指向的节点就可以啦。（其实本质上还是因为set自带的红黑树的内部结构，就是外挂啊。气哭！STL容器各个都是身怀绝技）

set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。

6.set的常见用途

set最主要的作用是自动去重，并在没有写比较函数的情况下，默认按升序排序，因此碰到需要去重但是却不方便直接开数组的情况，可以尝试用set来解决噢。

set/multiset会根据待定的排序准则，自动将元素排序。两者不同在于前者不允许元素重复，而后者允许。

7.练习题，桥黑板！！

PAT A1063. Set Similarity (25)

 

参考：C++中关于set的自定义排序函数的书写，STL中set容器的一点总结

《算法笔记》（胡凡，曽磊）