A-A+

STL之set的使用汇总

2015年09月02日 STL 暂无评论 阅读 206 次

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

set集合容器实现了红黑树(Red-Black Tree)的平衡二叉检索树的的数据结构,在插入元素时,它会自动调整二叉树的排列,把该元素放到适当的位置,以确保每个子树根节点的键值大于左子树所有节点的键值,而小于右子树所有节点的键值;另外,还得确保根节点的左子树的高度与有字数的高度相等,这样,二叉树的高度最小,从而检索速度最快。要注意的是,它不会重复插入相同键值的元素,而采取忽略处理。

平衡二叉检索树的检索使用中序遍历算法,检索效率高于vector、deque、和list的容器。另外,采用中序遍历算法可将键值由小到大遍历出来 ,所以,可以理解为平衡二叉检索树在插入元素时,就会自动将元素按键值从小到大的顺序排列。构造set集合的主要目的是为了快速检索,使用set前,需要在程序头文件中包含声明“#include<set>”。

微软帮助文档中对集合(set)的解释: “描述了一个控制变长元素序列的对象(注:set中的key和value是Key类型的,而map中的key和value是一个pair结构中的两个分 量)的模板类,每一个元素包含了一个排序键(sort key)和一个值(value)。对这个序列可以进行查找、插入、删除序列中的任意一个元素,而完成这些操作的时间同这个序列中元素个数的对数成比例关 系,并且当游标指向一个已删除的元素时,删除操作无效。而一个经过更正的和更加实际的定义应该是:一个集合(set)是一个容器,它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的
时候是有用的。集 合中的元素按一定的顺序排列,并被作为集合中的实例。如果你需要一个键/值对(pair)来存储数据,map是一个更好的选择。一个集合通过一个链表来组 织,在插入操作和删除操作上比向量(vector)快,但查找或添加末尾的元素时会有些慢。

使用总结:

#include <set>

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.

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

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

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

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

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

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

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

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

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

count() 查找set中键值出现的次数。因为set唯一性,其实是判断键值是否在set出现过。

equal_range() 返回一对定位器,分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素,这个返回值是一个pair类型,如果这一对定位器中哪个返回失败,就会等于end()的值。

//pair<set<int>::const_iterator,set<int>::const_iterator> pr;

//pr = x.equal_range(y);

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

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

erase(key_value) 删除键值key_value的值

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

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

set_intersection() //交集

//set_intersection( S.begin(), S.end(),S2.begin(), S2.end(),inserter(Si,Si.begin()));

set_union() //并集

//set_union( S.begin(), S.end(),S2.begin(), S2.end(),inserter(Su,Su.begin()));

set_difference() //差集

//set_difference( S.begin(), S.end(),S2.begin(), S2.end(),inserter(Sd, Sd.begin()));

set_symmetric_difference() //对称差

//set_symmetric_difference( S.begin(), S.end(),S2.begin(), S2.end(),inserter(Ssd, Ssd.begin()));

[参考资料]
http://blog.sina.com.cn/s/blog_4c98b9600100az2v.html
http://blog.csdn.net/lyhvoyage/article/details/22989659
http://www.cnblogs.com/BeyondAnyTime/archive/2012/08/13/2636375.html
另:修正了一些转载文章的错误。示例代码可见参考资料

标签:

给我留言