首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
某项目需要针对某结构进行一些频繁的存放操作,而针对该结构的读
[单选题]
某项目需要针对某结构进行一些频繁的存放操作,而针对该结构的读操作则相对较小,以下哪个数据结构最能够保证效率
list
map
vector
pair
查看正确选项
添加笔记
求解答(9)
邀请回答
收藏(274)
分享
1个回答
添加回答
46
凉风起天末
首先必需明确的是,这讨论是
C++里STL的容器
,而不是Java的,理由是C++容器的首字母小写(Java大写),另外,Java的Map只是一个接口,无法直接实例化,只能使用实现了它的类TreeMap或者HashMap,但是C++的map是可以直接用的(相当于TreeMap)
接下来分析题目,数据的存放操作多而读操作少,说明对容器的需求是:
重插入性能,而轻查找性能
,下面介绍STL里常用的几种容器及特点,对号入座即可:
list
:底层是双向链表,在
当前结点
前后插入新元素的效率为O(1),当然如果需要有序插入的话,还是会退化为O(n),因为需要遍历比较元素值
vector
:底层是动态数组,把数组的常用操作封装起来,方便使用,插入性能为O(n),尾插为O(2),需要注意的是,数组的空间是有限的,空间用尽时会进行扩容,因此平均下来性能比list要差一点点;
deque
:双端队列,主要是和 vector 相比较,从头部插入的性能优于 vector,同样也有扩容机制,头尾平均插入效率O(2);
set
:底层是红黑树,要求存储的数据是可以比较的,存储元素不能重复,插入性能是log(n),树的平衡调整规则会有一定的开销;
map
:底层是红黑树,存储的数据类型是 pair(键值对),和 set 相比,map 对存储的值要求没那么高,而把要求转移到键上(键不能重复),插入效率log(n);
pair
:通常是 map 的存储数据类型,只能存储两个值。pair,为map而生(锅牛,为梦想而生,不知道是哪里的广告了);
priority_queue
:底层是个堆结构(大小顶堆),实刻保证队首元素是当前的极值,因此可以拿来排序,插入性能也是log(n);
那么
由此看来,
在无序的情况下,list最符合题意了,vector和deque主要是空间管理(扩容)方面碍事了点;
编辑于 2020-11-02 22:12:24
回复(1)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
系统工程师
运维工程师
哈希
2019
Windows
360集团
来自:
360公司-2019校...
上传者:
小小
难度:
1条回答
274收藏
2064浏览
热门推荐
相关试题
下列叙述中不正确的一项是:
数据库工程师
搜狐畅游
游戏工程师
2020
公关
商务
人力资源
系统工程师
评论
(6)
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(2)
来自
职能类模拟题14
下面描述中,符合结构化程序设计风格...
搜狐
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
关于 CSS,以下说法正确的有:
360集团
运维工程师
2019
系统工程师
CSS
评论
(26)
来自
360公司-2019校招...
对于初始关键字(67,66,77,...
排序
评论
(6)
来自
360公司-2019校招...
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题