deque的内存是不是连续的？
C++ Primer这本书里说是连续的，msdn2000里也提到deque擦除N个元素时执行N个析构，以及从插入点到最近端的数个赋值。
可是我怎么想也觉得deque没必要用连续空间，记得《STL模板武道会》一文中比较过deque与vector的中间插入和动态增长，的确比vector强。那么deque就不应该是连续空间的。
那位高手告知一下你的理解？
问题点数：100、回复次数：15Top
1 楼Solstice（大佛）回复于 2002-06-24 12:05:14 得分 0
分块连续
它的iterator是Random Access Iterator，用上去感觉是连续的;实际上，在底层一般以分块的连续空间串接而成。
见《STL源码剖析》第4章，有多幅精美的示意图。Top
2 楼Serenade（号手）回复于 2002-06-24 12:19:08 得分 0
看来C++ Primer没说清楚啦。
《源码剖析》感觉暂时还用不上，没买。
再问一下，deque的iterator可以用算术运算，既然它是分块的，这是怎么实现的？
还有，既有随即访问，又有中间删除和插入的情况下，deque总的来说是比vector更好吧？Top
3 楼ydogg（灰毛兔频频）回复于 2002-06-24 12:50:28 得分 0
deque是连续。本质上是一个数组Top
4 楼xiaoxiangyy（潇湘夜雨）回复于 2002-06-24 12:57:38 得分 0
这么说来 只要申请一个指向deque头的指针 然后++ 就可以得到下一个元素?Top
5 楼Serenade（号手）回复于 2002-06-24 14:24:05 得分 0
灰毛兔，你的答案和大佛矛盾呀！我应该信谁的呢？
关键是：
如果连续（这和C++primer 以及msdn比较一致）那么插入、删除的表现应该不比vector好；
如果不连续，那么表现应该好于vector（有《武道会》一文为证），可是iterator的算术运算又说不过去。
望不辞麻烦解惑，可以加分。Top
6 楼ydogg（灰毛兔频频）回复于 2002-06-24 14:55:36 得分 0
primer上解释说，deque之所以在首部和尾部插入效率比较高，是因为它内部
使用了单独的空间，存放deque真正的首部和尾部。（有点类似循环队列的感觉)Top
7 楼Solstice（大佛）回复于 2002-06-24 15:09:21 得分 70
“deque的iterator可以用算术运算，既然它是分块的，这是怎么实现的？”
deque的iterator是一个class，可以有很复杂的行为（如跨块的访问），而《STL源码剖析》就是告诉你这些底层动作的一本好书。这本书前4章可以在www.jjhou.com免费下载。
“源码之前，了无秘密”-- J.J.Hou
Top
8 楼Serenade（号手）回复于 2002-06-24 15:58:26 得分 0
大佛：
也是，deque的iterator可以重载算术操作符。
我的疑问来自于list，既然deque可以那么干，list为什么就不可以呢？list不能用算术操作。
灰毛兔：
怎么解释deque中间插入删除比vector快？
Top
9 楼ydogg（灰毛兔频频）回复于 2002-06-24 16:44:31 得分 0
list是双向链表，当然不能算术操作
谁说deque中间插入删除比vector快？Top
10 楼Serenade（号手）回复于 2002-06-24 17:17:21 得分 0
去看看吧，兔子。
http://www.csdn.net/Develop/Read_Article.asp?Id=8657
http://www.csdn.net/Develop/Read_Article.asp?Id=8658Top
11 楼Solstice（大佛）回复于 2002-06-24 18:34:47 得分 0
deque的iterator的“算术操作”是常数时间，
而如果list的iterator也支持“算术操作”，需要花费线性时间，这是不允许的。
例如
di是deque::iterator，li是list::iterator
di += 10; // constant time
li += 10; // linear time if supported, not allowedTop
12 楼Serenade（号手）回复于 2002-06-25 10:08:55 得分 0
我的理解是这样的：
deque的二级数组是一个连续内存，它纪录了一级数组各元素的指针。我们看到用到的就是一级数组，它是分块连续的。这样一来好像问题都解决了。要是我自己设计，我就这么干。
最后再问一下，既有随即访问，又有中间删除和插入的情况下，deque总的来说是比vector更好吧？
加分到100。
Top
13 楼Serenade（号手）回复于 2002-06-25 10:13:24 得分 0
我的理解是这样的：
deque的二级数组是连续的，它纪录了一级数组各元素的地址。一级数组就是我们看到、用到的，是分块连续的。这样以来好像问题都解决了。要是我自己设计，我就这么干。
最后再问一下，既有随即访问，又有中间删除和插入的情况下，deque总的来说是比vector更好吧？
加分到100。
Top
14 楼yanwuhuan（燕无欢）回复于 2002-06-25 22:43:34 得分 10
deque的内存是分块连续的，比如说，他有50个元素，有可能就是用3个维数为20的数组组合而成。vector就是一个完整的数组了Top
15 楼cld（陈雷动）回复于 2002-06-26 12:03:49 得分 20
deque的内存并不是连续的，他在数据结构上更像一个双向的链表,所以它的插入的速度比vector要快，至于他的迭代子为什么能够支持++运算，是因为他重载了该运算符，查看一下deque的迭代子的原码就知道了.Top
16 楼Serenade（号手）回复于 2002-06-26 16:25:07 得分 0
没人回答我最后的那个问题？
算了，给分结贴。Top
