顺序容器vector、list、deque的区别

顺序容器

三种容器均支持resieze()操作,重新划定容器大小,且此函数有重载。 vector vector和built-in数组类似,是一个在堆上建立的一维数组,它拥有一段连续的内存空间,并且起始地址不变,因此 它能非常好的支持随即存取,即[]操作符。vector因为存储在堆上,所以支持erase( ), resieze()(重新划分容器容量)等操作; vector不用担心越界当空间不够用的时候,系统会自动按照一定的比例(对capacity( )大小)进行扩充。在vector序列末尾添加(push_back( ))或者删除(pop_back( ))对象效率高,在中间进行插入或删除效率很低,主要是要进行元素的移动和内存的拷贝,原因就在于当内存不够用的时候要执行重新分配内存,拷贝对象到新存储区,销毁old对象,释放内存等操 作,如果对象很多的话,这种操作代价是相当高的。为了减少这种代价,使用vector最理想的情况就是事先知道所要装入的对象数目,用成员函式 reserve( )预定下来;vector最大的优点莫过于是检索(用operator[ ])速度在这三个容器中是最快的,

list

list的本质是一个双向链表(根据sgi stl源代码),内存空间不连续,通过指针进行操作。说道链表,它的高效率首先表现是插入,删除元素,进行排序等等需要移动大量元素的操作。显然链表没有检索操作operator[ ], 也就是说不能对链表进行随机访问,而只能从头至尾地遍历,这是它的一个缺陷。list有不同于前两者的某些成员方法,如合并list的方法splice( ), 排序sort( ),交换list 的方法swap( )等等。

deque

deque是一个double-ended queue是由多个连续内存块构成,deque是list和vector的兼容,分为多个块,每一个块大小是512字节,块通过map块管理,map块里保存每个块得首地址。因此该容器也有索引操作operator[ ],效率没vector高。另外,deque比vector多了push_front( ) & pop_front( )操作。在两端进行此操作时与list的效率 差不多

下面是选择顺序容器类型的一些准则

1.如果我们需要随机访问一个容器则vector要比list好得多 。 2.如果我们已知要存储元素的个数则vector 又是一个比list好的选择。 3.如果我们需要的不只是在容器两端插入和删除元素则list显然要比vector好 4.除非我们需要在容器首部插入和删除元素否则vector要比deque好。 5.如果只在容易的首部和尾部插入数据元素,则选择deque. 6.如果只需要在读取输入时在容器的中间位置插入元素,然后需要随机访问元素,则可考虑输入时将元素读入到一个List容器,接着对此容器重新排序,使其适合顺序访问,然后将排序后的list容器复制到一个vector容器中

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端新视界

立即执行函数表达式(IIFE)

原文:immediately-invoked-function-expression 译者:nzbin 也许你还没有注意到,我是一个对术语比较坚持的人。因此...

2145
来自专栏Brian

Python Data Model

概述 最近在看《Fluent Python》一书,书中解释了Python很多重要的设计理念和实践,下面是我在看此书的读书笔记。Python的设计思想主要体现在它...

3816
来自专栏屈定‘s Blog

Java--Enum的思考

枚举类是Java5引进的特性,其目的是替换int枚举模式或者String枚举模式,使得语义更加清晰,另外也解决了行为和枚举绑定的问题.

1394
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 五、高阶函数

30310
来自专栏老马说编程

(92) 函数式数据处理 (上) / 计算机程序的思维逻辑

上节我们介绍了Lambda表达式和函数式接口,本节探讨它们的应用,函数式数据处理,针对常见的集合数据处理,Java 8引入了一套新的类库,位于包java.uti...

1916
来自专栏架构之路

Java 中冷门的 synthetic 关键字原理解读

看JAVA的反射时,看到有个synthetic ,还有一个方法isSynthetic() 很好奇,就了解了一下: 1.定义 Any constructs int...

3455
来自专栏黑泽君的专栏

【Java面试复习经典】传智播客Java就业班入学测试题及答案解析(2012年版)

  共50道题,每道题2分,总分100分,80分为合格。   注意,题目有多选,也有单选。请认真作答。

1733
来自专栏aCloudDeveloper

C++primer笔记之顺序容器

最近又重新拾起C++primer,发现每一次看都会有不同的体验,但每一次看后因为不常用,忘记得很快,所以记笔记是很关键的一环,咋一看是浪费时间,实际上是节省了很...

2049
来自专栏Jimoer

数据结构:数组、链表、栈、队列的理解

解释定义 数据结构: 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。再简单描述一下:数据结构就是描述对象间逻辑关系的学科。 如果还是不太清楚下面会...

47210
来自专栏Python攻城狮

正则表达式1.正则表达式概述2.re模块操作3.表示字符4.re模块的高级用法5.贪婪和非贪婪

在Python中需要通过正则表达式对字符串进行匹配的时候,可以使用一个模块,名字为re

2042

扫码关注云+社区

领取腾讯云代金券