Chinaunix首页 | 论坛 | 博客

红碑山屌丝的学习园地

首页　| 　博文目录　| 　关于我

coolzsj

  • 博客访问： 291546
  • 博文数量： 111
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 816
  • 用 户 组： 普通用户
  • 注册时间： 2014-05-04 20:35
文章分类

全部博文（111）

文章存档

2016年（1）

2015年（5）

2014年（105）

我的朋友
最近访客
推荐博文
相关博文
C++ STL 之 Set和Multiset

分类： C/C++

2014-06-22 16:20:21

转载地址：http://blog.csdn.net/xiajun07061225/article/details/7459206

一、set和multiset基础

set和multiset会根据特定的排序准则，自动将元素进行排序。不同的是后者允许元素重复而前者不允许。

需要包含头文件：

#include

set和multiset都是定义在std空间里的类模板：


[cpp] view plaincopyprint?
  1. template<class _Kty,
  2. class _Pr = less<_Kty>,
  3. class _Alloc = allocator<_Kty> >
  4. class set
[cpp] view plaincopyprint?
  1. template<class _Kty,
  2. class _Pr = less<_Kty>,
  3. class _Alloc = allocator<_Kty> >
  4. class multiset

只要是可复赋值、可拷贝、可以根据某个排序准则进行比较的型别都可以成为它们的元素。第二个参数用来定义排序准则。缺省准则less是一个仿函数，以operator<对元素进行比较。


所谓排序准则，必须定义strict weak ordering，其意义如下：

1、必须使反对称的。

对operator<而言，如果x

2、必须使可传递的。

对operator<而言，如果x

3、必须是非自反的。

对operator<而言，x

因为上面的这些特性，排序准则可以用于相等性检验，就是说，如果两个元素都不小于对方，则它们相等。


二、set和multiset的功能

和所有关联式容器类似，通常使用平衡二叉树完成。事实上，set和multiset通常以红黑树实作而成。

自动排序的优点是使得搜寻元素时具有良好的性能，具有对数时间复杂度。但是造成的一个缺点就是：

不能直接改变元素值。因为这样会打乱原有的顺序。

改变元素值的方法是：先删除旧元素，再插入新元素。

存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。


三、操作函数

构造函数和析构函数

set的形式可以是：

有两种方式可以定义排序准则：

1、以template参数定义：


[cpp] view plaincopyprint?
  1. set<int,greater<int>> col1;
此时，排序准则就是型别的一部分。型别系统确保只有排序准则相同的容器才能被合并。


程序实例：


[cpp] view plaincopyprint?
  1. #include
  2. #include
  3. using namespace std;
  5. int main()
  6. {
  7. set<int> s1;
  8. set<int,greater<int> > s2;
  10. for (int i = 1;i < 6;++i)
  11. {
  12. s1.insert(i);
  13. s2.insert(i);
  14. }
  15. if(s1 == s2)
  16. cout << "c1 equals c2 !" << endl;
  17. else
  18. cout << "c1 not equals c2 !" << endl;
  19. }
程序运行会报错。但是如果把s1的排序准则也指定为greater便运行成功。


2、以构造函数参数定义。

这种情况下，同一个型别可以运用不同的排序准则，而排序准则的初始值或状态也可以不同。如果执行期才获得排序准则，而且需要用到不同的排序准则，这种方式可以派上用场。

程序实例：


[cpp] view plaincopyprint?
  1. #include
  2. #include "print.hpp"
  3. #include
  4. using namespace std;
  6. template <class T>
  7. class RuntimeCmp{
  8. public:
  9. enum cmp_mode{normal,reverse};
  10. private:
  11. cmp_mode mode;
  12. public:
  13. RuntimeCmp(cmp_mode m = normal):mode(m){}
  15. bool operator()(const T &t1,const T &t2)
  16. {
  17. return mode == normal ? t1 < t2 : t2 < t1;
  18. }
  20. bool operator==(const RuntimeCmp &rc)
  21. {
  22. return mode == rc.mode;
  23. }
  24. };
  26. typedef set<int,RuntimeCmp<int> > IntSet;
  28. void fill(IntSet& set);
  30. int main()
  31. {
  32. IntSet set1;
  33. fill(set1);
  34. PRINT_ELEMENTS(set1,"set1:");
  36. RuntimeCmp<int> reverse_order(RuntimeCmp<int>::reverse);
  38. IntSet set2(reverse_order);
  39. fill(set2);
  40. PRINT_ELEMENTS(set2,"set2:");
  42. set1 = set2;//assignment:OK
  43. set1.insert(3);
  44. PRINT_ELEMENTS(set1,"set1:");
  46. if(set1.value_comp() == set2.value_comp())//value_comp Returns the comparison object associated with the container
  47. cout << "set1 and set2 have the same sorting criterion" << endl;
  48. else
  49. cout << "set1 and set2 have the different sorting criterion" << endl;
  50. }
  52. void fill(IntSet &set)
  53. {
  54. set.insert(4);
  55. set.insert(7);
  56. set.insert(5);
  57. set.insert(1);
  58. set.insert(6);
  59. set.insert(2);
  60. set.insert(5);
  61. }
运行结果：




虽然set1和set2的而比较准则本身不同，但是型别相同，所以可以进行赋值操作。



非变动性操作

注意：元素比较操作只能用于型别相同的容器。

特殊的搜寻函数

赋值

赋值操作两端的容器必须具有相同的型别，但是比较准则本身可以不同，但是其型别必须相同。如果比较准则的不同，准则本身也会被赋值或交换。

迭代器相关函数

元素的插入和删除

注意：插入函数的返回值不完全相同。

set提供的插入函数：


[cpp] view plaincopyprint?
  1. pairbool> insert(const value_type& elem);
  2. iterator insert(iterator pos_hint, const value_type& elem);
multiset提供的插入函数：



[cpp] view plaincopyprint?
  1. iterator insert(const value_type& elem);
  2. iterator insert(iterator pos_hint, const value_type& elem);
返回值型别不同的原因是set不允许元素重复，而multiset允许。当插入的元素在set中已经包含有同样值的元素时，插入就会失败。所以set的返回值型别是由pair组织起来的两个值：


第一个元素返回新元素的位置，或返回现存的同值元素的位置。第二个元素表示插入是否成功。

set的第二个insert函数，如果插入失败，就只返回重复元素的位置！

但是，所有拥有位置提示参数的插入函数的返回值型别是相同的。这样就确保了至少有了一个通用型的插入函数，在各种容器中有共通接口。


注意：还有一个返回值不同的情况是：作用于序列式容器和关联式容器的erase()函数：

序列式容器的erase()函数：


[cpp] view plaincopyprint?
  1. iterator erase(iterator pos);
  2. iterator erase(iterator beg, iterator end);
关联式容器的erase()函数：



[cpp] view plaincopyprint?
  1. void erase(iterator pos);
  2. void erase(iterator beg, iterator end);
这完全是为了性能的考虑。因为关联式容器都是由二叉树实现，搜寻某元素并返回后继元素可能很费时。

五、set应用示例：



[cpp] view plaincopyprint?
  1. #include
  2. #include
  3. using namespace std;
  5. int main()
  6. {
  7. typedef set<int,greater<int> > IntSet;
  8. IntSet s1;
  10. s1.insert(4);
  11. s1.insert(3);
  12. s1.insert(5);
  13. s1.insert(1);
  14. s1.insert(6);
  15. s1.insert(2);
  16. s1.insert(5);
  17. //the inserted element that has the same value with a element existed is emitted
  19. copy(s1.begin(),s1.end(),ostream_iterator<int>(cout," "));
  20. cout << endl << endl;
  22. pairbool> status = s1.insert(4);
  23. if(status.second)
  24. cout << "4 is inserted as element "
  25. << distance(s1.begin(),status.first) + 1 << endl;
  26. else
  27. cout << "4 already exists in s1" << endl;
  28. copy(s1.begin(),s1.end(),ostream_iterator<int>(cout," "));
  29. cout << endl << endl;
  31. set<int> s2(s1.begin(),s1.end());//default sort criterion is less<
  32. copy(s2.begin(),s2.end(),ostream_iterator<int>(cout," "));
  33. cout << endl << endl;
  34. }

上述程序最后新产生一个set：s2，默认排序准则是less。以s1的元素作为初值。


注意：s1和s2有不同的排序准则，所以他们的型别不同，不能直接进行相互赋值或比较。

运行结果：

阅读(576) | 评论(0) | 转发(0) |
0

上一篇：C++ STL 之 Multimap

下一篇：C++ STL 之 deque

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6