首页 > 技术文章 > multiset和set

1436177712qqcom 原文

set集合容器:实现了红黑树的平衡二叉检索树的数据结构,插入元素时,它会自动调整二叉树的排列,把元素放到适当的位置,以保证每个子树根节点键值大于左子树所有节点的键值,小于右子树所有节点的键值;另外,还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法,检索效率高于vector、deque和list等容器,另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索,不可直接去修改键值。

set是STL中一种标准关联容器(vector,list,string,deque都是序列容器,而set,multiset,map,multimap是标准关联容器),它底层使用平衡的搜索树——红黑树实现,插入删除操作时仅仅需要指针操作节点即可完成,不涉及到内存移动和拷贝,所以效率比较高。set,顾名思义是“集合”的意思,在set中元素都是唯一的,而且默认情况下会对元素自动进行升序排列,支持集合的交(set_intersection),差(set_difference) 并(set_union),对称差(set_symmetric_difference) 等一些集合上的操作,如果需要集合中的元素允许重复那么可以使用multiset

multiset

用法和set差不多

multiset篇(平衡二叉树,允许重复值)

  头文件 #include<set>

1.元素的创建

1 multiset<int>v;

2.元素的插入

1     v.insert(1);
2     v.insert(1);
3     v.insert(2);
4     v.insert(3);

3.定位器

   1         multiset<int>::iterator it; 

   2         *it //返回指针所指的元素

4.元素的输出

1     multiset<int>::iterator it;
2     for(it=v.begin();it!=v.end();it++)
3         cout<<*it<<" ";
4     cout<<endl;

5.元素的删除

1     int n=v.erase(1);//删除键值为1的所有元素,并返回删除的个数
2     multiset<int>::iterator it;
3     it=v.begin();
4      v.erase(it);

6.常见函数的使用

              v.empty()      // 如果集合为空,返回true
              v.clear()         //   清除所有元素
              v.count(temp)        // 返回指向某个值元素的个数
              v.find(temp)   //查找键值为temp的元素
              v.size()          // 多元集合中元素的数目

参考https://www.cnblogs.com/lsx54321/archive/2012/07/25/2608879.html

set

set常用函数

begin()        ,返回set容器的第一个元素

end()      ,返回set容器的最后一个元素

clear()          ,删除set容器中的所有的元素

empty()    ,判断set容器是否为空

max_size()   ,返回set容器可能包含的元素最大个数

size()      ,返回当前set容器中的元素个数

rbegin     ,返回的值和end()相同

rend()     ,返回的值和rbegin()相同

count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了。

示例代码:

equal_range() ,返回一对定位器,分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素,这个返回值是一个pair类型,如果这一对定位器中哪个返回失败,就会等于end()的值。具体这个有什么用途我还没遇到过~~~

erase(iterator)  ,删除定位器iterator指向的值

erase(first,second),删除定位器first和second之间的值

erase(key_value),删除键值key_value的值

小结:set中的删除操作是不进行任何的错误检查的,比如定位器的是否合法等等,所以用的时候自己一定要注意。


find()  ,返回给定值值得定位器,如果没找到则返回end()。

insert(key_value); 将key_value插入到set中 ,返回值是pair<set<int>::iterator,bool>,bool标志着插入是否成功,而iterator代表插入的位置,若key_value已经在set中,则iterator表示的key_value在set中的位置。

inset(first,second);将定位器first到second之间的元素插入到set中,返回值是void.

lower_bound(key_value) ,返回第一个大于等于key_value的定位器

upper_bound(key_value),返回最后一个大于等于key_value的定位器

自定义比较函数

(1)元素不是结构体:
        例:
        //自定义比较函数myComp,重载“()”操作符

  1. struct myComp  
  2. {  
  3.     bool operator()(const your_type &a,const your_type &b)  
  4.     [  
  5.         return a.data-b.data>0;  
  6.     }  
  7. }  
  8. set<int,myComp>s;  

(2)如果元素是结构体,可以直接将比较函数写在结构体内。
        例:

  1. struct Info  
  2. {  
  3.     string name;  
  4.     float score;  
  5.     //重载“<”操作符,自定义排序规则  
  6.     bool operator < (const Info &a) const  
  7.     {  
  8.         //按score从大到小排列  
  9.         return a.score<score;  
  10.     }  
  11. }  
  12. set<Info> s;  

参考http://www.360doc.com/content/18/0824/18/58991947_780926783.shtml

推荐阅读