`
473687880
  • 浏览: 478115 次
文章分类
社区版块
存档分类
最新评论

深入理解vector list deque——存储结构机理

 
阅读更多

先来看一下 c++标准模板库中,容器类vector、list 、deque都属于顺行性容器(所谓顺序性容器是一种各元素之间有顺序关系的线性表,是一种线性结构的可序群集,每个元素都有固定的位置,这个位置与元素无关,只与插入删除的先后顺序有关);都可以用来存储一组类型相同的对象;不同于内置数据类型数组的是,vector、list、deque的大小不是固定的,他们支持动态增长。

之所以设计 vector、list、deque不同的容器类,是因为它们适用于不同的情况。 (详细可参考http://www.360doc.com/content/11/0330/22/4390689_106013089.shtml#)


vector

从后面快速的插入与删除,直接访问任何元素

deque

从前面或后面快速的插入与删除,直接访问任何元素

list

双链表,从任何地方快速插入与删除

单从上面适用情况来看,似乎deque完全可以代替vector和list的,后者没有存在的必要,但是,情况并不是这样的,还要看一下他们的性能。有人曾专门对各种情况性能做过对比,里面有些数值似乎不准确,但能说明一定的问题 (http://www.cnblogs.com/kingcat/archive/2012/04/13/2446186.html)


比赛项目/参赛选手

Vector

Deque

List

内存管理

Poor

Good

perfect

使用[ ]和at() 操作访问数据

Very good

Normal

N/A

Iterator的访问速度

Good

Very good

Good

Push_back操作(后插入)

Good

Good

Good

Push_front操作(前插入)

N/A

Very good

Good

Insert(中间插入)

Poor

Perfect

Perfect

Erase(中间删除)

Poor

Perfect

Perfect

Pop_back(后部删除)

Perfect

Perfect

Normal

Swap(交换数据)

Perfect

Very good

Good

遍历

Perfect

Good

Normal

从表中可以总结出一下几点:

(1)vector适用于随机存取,支持[],随机存取时间为常数;但是在非末尾删除插入数据时,效率极低。

(2)list适用于数组中间频繁插入删除数据,其插入删除开销低,但是不支持随机存取。

(3)deque界于vector和list两者之间,支持随机存取,队首队尾插入删除操作开销极小。随机存取效率接近于vector,队首队尾插入删除接近于list。

接下来,从它们的内部机制来分析原因:

vector事实上表示的是一块连续的内存,当数据超过数组大小,需要申请新的内存,这时,vector会申请一块足够大的连续内存,把原来数据复制到新的内存,并释放原来vector占用的内存。所谓随机存取,就是可以通过公式直接计算出元素地址的方式,而不需要挨个查找。vector的计算公式类似于 a0+(i-1)*d (a0为vector地址,i为第i个元素,d为每个元素占用的地址个数。

list是双向链式表,在内存中不一定连续。如果要实现随机访问,需要遍历整个数组,在c++标准库模版索性没有提供随机存储([]操作)。但是链式存储有一个好处,就是在表中间插入和删除元素特别方便。

deque事实上是有多个连续块组成是c++中的双向队列,因此在两端插入删除元素特别方便,(其内存结构如下: http://blog.csdn.net/yfkiss/article/details/6559149)

image

对于deque的工作机制,有几点没得到确认的猜测:

(1)因为可以再队列两头快速的插入元素,则说明,元素的第一个位置并不在申请内存的第一个位置,其前面应该还有连续的空间待用

(2)因为deque的随机访问时间为常数,所以可推测其其随机访问公式为 一分段函数

if(i<s0)
     addr=a0+d*(i-1)
else if(i>s0&&i<s1)
       addr=a1+d*(i-s0)
else if(i>s1 && i<s2)
      addr=a2+d*(i-s0-s1)
else
      ....
(3)因为中间插入删除元素逊于list,优于vector,可推测:对于中间插入删除时这样的,给待插入(删除)元素所在的连续块重新分配内存,插入(删除)新元素,其他连续快不动。


下图为vector、list、deque的无理存储结构。(http://www.360doc.com/content/11/0330/22/4390689_106013089.shtml#)


待继续完善.......

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics