前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >关联容器小结

关联容器小结

作者头像
Enterprise_
发布2019-11-12 22:57:46
4640
发布2019-11-12 22:57:46
举报
文章被收录于专栏:小L的魔法馆

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。undefined本文链接:https://blog.csdn.net/Enterprise_/article/details/102943141

关联容器和顺序容器的不同

关联容器和顺序容器的根本不同之处在于,关联容器中的元素是按关键字来保存和访问的(比如map和set),而顺序容器中的元素是按照在容器中的位置来顺序保存和访问的(比如vector和string)。

顺序容器有

代码语言:javascript
复制
vector
deque
list
forward_list
array
string

关联容器有

代码语言:javascript
复制
按照关键字有序保存
map
set
multimap
multiset
无序保存
unordered_map
unordered_set
unordered_multimap
unordered_multiset

关联容器不支持和位置相关的操作,因为是按关键字顺序存储的,关联容器的迭代器都是双向的。

对于有序关联容器中的关键字类型要求

对与有序关联容器而言,关键字类型必须定义元素比较的方法(这一点尤其重要),默认时,使用关键字类型的<运算符来比较两个关键字。即虽然可以向容器中保存自己定义的类或者结构体,但是如果这些类和结构体中没有定义<运算符的话,则该行为就是不合法的。

但是可以向算法提供一个自己定义的比较操作(通常是一个函数)或者对<进行重载来完成比较操作,唯一需要注意的就是,所提供的操作必须在关键字类型上严格弱序(可以看作小于等于)

严格弱序具有反自反性**(不能同时小于等于对方),也具有传递性(k1<=k2,k2<=k3则有k1<=k3)**,

严格弱序上的等价关系是任何一个都不小于等于另一个,这个等价关系也具有传递性。

在使用自己定义的操作时,必须要提供该操作类型(可以使用decltype来获得函数指针类型),比如定义一个multiset

代码语言:javascript
复制
multiset<type,decltype(CompareFunction)*>name(CompareFunction);

关联容器额外的类型别名

类型别名

含义

key_type

该容器的关键字类型

mapped_type

关键字关联的类型,只适用于map

value_type

对于set而言和key_type相同;对于map,为pair<const key_type,mapped_type>

关联容器和算法

实际使用算法时,关联容器只能是一个源序列或者目的序列。

比如:

代码语言:javascript
复制
	multiset<string>c{ "1","2","1" };
	vector<string>v;
	copy(c.begin(), c.end(), back_inserter(v));//v为目的序列,c为源序列
代码语言:javascript
复制
	multiset<string>c;
	vector<string>v{ "1","2","1" };
    copy(v.begin(), v.end(), inserter(c,c.end())); //c为目的序列,v为源序列

关联容器的操作及其返回值

插入元素

insert向容器中插入一个元素,不存在则什么也不做。emplace也是插入元素,但是只有当关键字不在容器时才插入。

代码语言:javascript
复制
insert(value_type);  //value_type对于set就是关键字,对于map而言就是一个pair
insert(args);		//arges时一个初始化列表
insert(begin,end);	//insert也可以接受一对迭代器begin,end;
insert(p,args);		//从容器的p位置开始搜索新元素args的插入位置

emplace(value_type);//当关键字不在容器时才插入
emplace(p,args);//从容器的p位置开始搜索新元素args的插入位置

对于插入一个元素的**insert(value_type)**和**emplace(value_type)**会返回一个**pair< value_type::iterator,bool >**,

pair的first时一个指向给定插入元素的迭代器,pair的second是一个表示是否插入成功的布尔值;

对于insert(args)insert(begin,end),返回一个void;

对于insert(p,args)emplace(p,args),返回一个迭代器,指向给定元素。

删除元素

关联容器有三个版本的erase操作,分别接受一个关键字,一个迭代器和一对迭代器。

访问和查找元素

1.下标(有序无序可用)

对于map而言,可以使用下标或者一个at函数来对容器中的元素进行访问,比如m[key]或者m.at(key)这样的操作。

对于下标而言,如果该关键字在容器中不存在,那么**就会被当作一个新元素加入到容器中去。**at函数没有这样的作用,它只会对参数进行检查,如果不存在就抛出一个out_of_range的异常。

而对于set而言,是不能用下标进行访问的。

2.find或者count(有序无序可用)

对于map和set都有自带的find和count版本,find会返回一个迭代器,指向第一个关键字为参数的元素,但如果该关键字不存在,就返回尾后迭代器。

count会返回容器中符合要求的关键字的数量,不存在则为0;

3.lower_bound和upper_bound(有序版本)

lower_bound(k)会返回一个迭代器,指向第一个关键字不小于k的元素(即<k的上界,>=k的下界)。如果不存在则返回一个不影响排序的关键字的插入位置(即如果要将这个不存在的关键字插入到容器中时要放入的位置)

upper_bound(k)会返回一个迭代器,指向第一个关键字大于k的元素,即>k的下界,<=k的下界。如果不存在也会返回一个不影响排序的关键字的插入位置

比如:

代码语言:javascript
复制
multimap<string,string>words;
string k="Test";
auto b=words.lower_bound(k),e=words.upper_bound(k);
for(;b!=e;++b)cout<<b->second<<endl;

如果调用lower_bound(k)的话,如果容器中存在关键字k的话,b就会匹配到第一个k所在的元素位置,e则会指向最后一个k之后的位置,否则b和e都会指向一个相同位置,即不影响排序的关键字的插入位置

所以对于同样的参数调用,如果lower_bound和upper_bound指向的迭代器不相同,那么两个就是一个包含所有关键字k的迭代器范围[b,e)

4.equal_range函数(有序版本)

对于上面的版本,用equal_range函数可以改写为:

代码语言:javascript
复制
multimap<string,string>words;
string k="Test";
auto pos=words.equal_range(k);
for(;pos.first!=pos.second;++pos.first)cout<<pos.first->second<<endl;

//pos.first和words.lower_bound(k)相等
//pos.second和words.upper_bound(k)相等

equal_range接受一个关键字,返回一个pair,包含两个迭代器。当关键字存在时,两个迭代器就是刚才用lower_bound和upper_bound得到的迭代器。当不存在时,也返回不影响排序的关键字的插入位置

无序容器

概念和性能

无序容器使用一个哈希函数和关键字类型的==运算符来组织元素,而不是<运算符。

无序容器在存储上的组织形式为一组桶,利用哈希函数将具有一个相同哈希值的元素保存在相同的桶中(即使是重复版本的无序容器也是一样),所以无序容器的性能取决于哈希函数的性能和桶的数量和大小。

无序容器对关键字类型的要求

对于内置的类型比如int,以及标准库类型比如string,标准库都提供了默认的hash模板,所以可以直接定义,比如:

代码语言:javascript
复制
unordered_map<string, int>words;

但是对于自定义的类型,就需要提供hash模板或者提供函数来替代==运算符和哈希函数(类似重载)。

一种特别的情况时,如果关键字是一个已经自定义了==运算符的类,则只需要提供哈希函数即可。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/11/06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 关联容器和顺序容器的不同
  • 对于有序关联容器中的关键字类型要求
  • 关联容器额外的类型别名
  • 关联容器和算法
  • 关联容器的操作及其返回值
    • 插入元素
      • 删除元素
        • 访问和查找元素
          • 1.下标(有序无序可用)
          • 2.find或者count(有序无序可用)
          • 3.lower_bound和upper_bound(有序版本)
          • 4.equal_range函数(有序版本)
      • 无序容器
        • 概念和性能
          • 无序容器对关键字类型的要求
          相关产品与服务
          容器服务
          腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档