C++ STL学习之容器set和multiset (补充材料)

本文涉及的产品
容器服务 Serverless 版 ACK Serverless,317元额度 多规格
容器服务 Serverless 版 ACK Serverless,952元额度 多规格
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: 一、set和multiset基础 set和multiset会根据特定的排序准则,自动将元素进行排序。不同的是后者允许元素重复而前者不允许。 需要包含头文件: #include set和multiset都是定义在std空间里的类模板: 1 template 4 class set 1 template 4 class multiset   只要是可复赋值、可拷贝、可以根据某个排序准则进行比较的型别都可以成为它们的元素。

一、set和multiset基础

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

需要包含头文件:

#include <set>

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

1 template<class _Kty,
2     class _Pr = less<_Kty>,
3     class _Alloc = allocator<_Kty> >
4 class set
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<y为真,则y<x为假。

2、必须使可传递的。

对operator<而言,如果x<y为真,且y<z为真,则x<z为真。

3、必须是非自反的。

对operator<而言,x<x永远为假。

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

 

二、set和multiset的功能

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

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

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

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

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

 

三、操作函数

构造函数和析构函数

set的形式可以是:

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

1、以template参数定义:

 1 set<int,greater<int>> col1; 

此时,排序准则就是型别的一部分。型别系统确保只有排序准则相同的容器才能被合并。

程序实例:

 

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     set<int> s1;
 8     set<int,greater<int> > s2;
 9 
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<int>便运行成功。

 

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

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

程序实例:

 

 1 #include <iostream>
 2 #include "print.hpp"
 3 #include <set>
 4 using namespace std;
 5 
 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){}
14 
15     bool operator()(const T &t1,const T &t2)
16     {
17         return mode == normal ? t1 < t2 : t2 < t1;
18     }
19 
20     bool operator==(const RuntimeCmp &rc)
21     {
22         return mode == rc.mode;
23     }
24 };
25 
26 typedef set<int,RuntimeCmp<int> > IntSet;
27 
28 void fill(IntSet& set);
29 
30 int main()
31 {
32     IntSet set1;
33     fill(set1);
34     PRINT_ELEMENTS(set1,"set1:");
35 
36     RuntimeCmp<int> reverse_order(RuntimeCmp<int>::reverse);
37 
38     IntSet set2(reverse_order);
39     fill(set2);
40     PRINT_ELEMENTS(set2,"set2:");
41 
42     set1 = set2;//assignment:OK
43     set1.insert(3);
44     PRINT_ELEMENTS(set1,"set1:");
45 
46     if(set1.value_comp() == set2.value_comp())//value_comp <span style="font-family: verdana, arial, helvetica, sans-serif; ">Returns the comparison object associated with the container</span>
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 }
51 
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提供的插入函数:

pair<iterator,bool> insert(const value_type& elem); 
iterator  insert(iterator pos_hint, const value_type& elem); 

 

multiset提供的插入函数:

iterator  insert(const value_type& elem); 
iterator  insert(iterator pos_hint, const value_type& elem);

 

返回值型别不同的原因是set不允许元素重复,而multiset允许。当插入的元素在set中已经包含有同样值的元素时,插入就会失败。所以set的返回值型别是由pair组织起来的两个值:

 

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

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

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

 

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

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

 

iterator erase(iterator pos); 
iterator erase(iterator beg, iterator end);

 

关联式容器的erase()函数:

 void     erase(iterator pos); 
 void     erase(iterator beg, iterator end); 

 

这完全是为了性能的考虑。因为关联式容器都是由二叉树实现,搜寻某元素并返回后继元素可能很费时。

五、set应用示例:

 

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     typedef set<int,greater<int> > IntSet;
 8     IntSet s1;
 9 
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
18 
19     copy(s1.begin(),s1.end(),ostream_iterator<int>(cout," "));
20     cout << endl << endl;
21 
22     pair<IntSet::iterator,bool> 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;
30 
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有不同的排序准则,所以他们的型别不同,不能直接进行相互赋值或比较。

运行结果:

目录
相关文章
|
1月前
|
存储 算法 C++
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
89 10
|
22天前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
60 5
|
22天前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
44 1
|
30天前
|
算法 安全 Linux
【C++STL简介】——我与C++的不解之缘(八)
【C++STL简介】——我与C++的不解之缘(八)
|
1月前
|
Kubernetes Linux 持续交付
docker容器学习
【10月更文挑战第1天】
32 1
|
24天前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
19 0
|
5天前
|
Kubernetes 监控 开发者
掌握容器化:Docker与Kubernetes的最佳实践
【10月更文挑战第26天】本文深入探讨了Docker和Kubernetes的最佳实践,涵盖Dockerfile优化、数据卷管理、网络配置、Pod设计、服务发现与负载均衡、声明式更新等内容。同时介绍了容器化现有应用、自动化部署、监控与日志等开发技巧,以及Docker Compose和Helm等实用工具。旨在帮助开发者提高开发效率和系统稳定性,构建现代、高效、可扩展的应用。
|
18天前
|
存储 Docker 容器
docker中挂载数据卷到容器
【10月更文挑战第12天】
47 5
|
2天前
|
Java 应用服务中间件 Linux
【Docker容器化技术】docker安装与部署、常用命令、容器数据卷、应用部署实战、Dockerfile、服务编排docker-compose、私有仓库
本文主要讲解了Docker的安装与部署、常用命令、容器数据卷、应用部署实战、Dockerfile、服务编排docker-compose、私有仓库以及Docker容器虚拟化与传统虚拟机比较。
【Docker容器化技术】docker安装与部署、常用命令、容器数据卷、应用部署实战、Dockerfile、服务编排docker-compose、私有仓库
|
1天前
|
关系型数据库 MySQL API

热门文章

最新文章