某项目需要针对某结构进行一些频繁的存放操作，而针对该结构的读

[单选题]

某项目需要针对某结构进行一些频繁的存放操作，而针对该结构的读操作则相对较小，以下哪个数据结构最能够保证效率

查看答案及解析

凉风起天末

首先必需明确的是，这讨论是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收藏 2060浏览