首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
某项目需要针对某结构进行一些频繁的存放操作,而针对该结构的读
[单选题]
某项目需要针对某结构进行一些频繁的存放操作,而针对该结构的读操作则相对较小,以下哪个数据结构最能够保证效率
list
map
vector
pair
查看正确选项
添加笔记
求解答(9)
邀请回答
收藏(273)
分享
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条回答
273收藏
2061浏览
热门推荐
相关试题
下列需要重新启动计算机的操作有?
华为
Windows
评论
(5)
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(3)
来自
职能类模拟题14
小支欲用积分兑换安仔娃娃。兑换的规...
360集团
智力题
评论
(24)
来自
360公司2014校招笔试卷
设哈希表长为8,哈希函数为Hash...
360集团
哈希
Java工程师
C++工程师
iOS工程师
运维工程师
前端工程师
算法工程师
测试工程师
2019
系统工程师
测试开发工程师
评论
(7)
来自
360公司-2019校招...
有以下程序 #include
C++
C++工程师
评论
(32)
来自
360公司-2019校招...
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题