算法学习之路|用C++刷算法会用到的STL(二)——set

  1. 云栖社区>
  2. 博客>
  3. 正文

算法学习之路|用C++刷算法会用到的STL(二)——set

kissjz 2018-02-09 12:08:19 浏览1753
展开阅读全文

二、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容器的一点总结

《算法笔记》(胡凡,曽磊)

 

网友评论

登录后评论
0/500
评论
kissjz
+ 关注