究竟什么数据结构是C++中的deques？

Question

是否有一个特定的数据结构,C++ STL中的deque应该实现,或者是一个deque只是这个模糊的概念,一个数组可以从前面和后面增长,然而实现选择实现？

我以前总是假设deque是一个循环缓冲区,但我最近在这里读了一个C++引用,听起来像deque是某种数组的数组.它似乎不是一个普通的旧循环缓冲区.那么它是一个间隙缓冲区,还是可扩展数组的其他变体,还是仅仅依赖于实现？

答案的更新和摘要:

似乎普遍的共识是,双端队列是一种数据结构,这样:

• 插入或删除元素的时间应该在列表的开头或结尾处是恒定的,并且在其他地方最多是线性的.如果我们将此解释为真正的恒定时间而非摊销的恒定时间,正如有人评论,这似乎具有挑战性.有些人认为我们不应将此解释为非摊销的常数时间.
• "deque要求任何插入都应保持对成员元素的任何引用有效.迭代器可以无效,但成员本身必须保留在内存中的相同位置." 正如有人评论的那样:只需将成员复制到堆上的某个位置并将T*存储在引擎盖下的数据结构中即可.
• "在双端队列的开头或末尾插入单个元素总是需要一个恒定的时间,并导致对T的构造函数的单个调用." 如果数据结构在引擎盖下存储T*,也将实现T的单个构造函数.
• 数据结构必须具有随机访问权限.

如果我们将第一个条件设为"非摊销的恒定时间",似乎没有人知道如何得到第一和第四条件的组合.链表实现1)但不是4),而典型的循环缓冲实现4)但不实现1).我想我的实现可以满足以下两个要求.评论？

我们从其他人建议的实现开始:我们分配一个数组并从中间开始放置元素,在前面和后面留下空间.在这个实现中,我们跟踪中心在前后方向上有多少元素,调用那些值F和B.然后,让我们用一个两倍于原始大小的辅助数组来扩充这个数据结构.数组(所以现在我们浪费了大量的空间,但渐近的复杂性没有变化).我们还将从中间填充这个辅助数组,并给它类似的值F'和B'.策略是这样的:每次我们在给定方向上向主数组添加一个元素时,如果F> F'或B> B'(取决于方向),最多两个值从主数组复制到辅助数据数组直到F'赶上F(或B'跟B).因此,插入操作涉及将1个元素放入主数组并从主数据库复制到辅助数据2,但它仍然是O(1).当主阵列变满时,我们释放主阵列,使辅助阵列成为主阵列,并制作另一个大2倍的辅助阵列.这个新的辅助数组以F'= B'= 0开始,并且没有复制到它(因此如果堆分配是O(1)复杂度,则调整大小op为O(1)).由于添加到主要和主要的每个元素的辅助副本2个元素最多开始半满,因此当主要用完空间时,辅助节点不可能赶上主要元素.删除同样只需要从主要删除1个元素,从辅助删除0或1.因此,假设堆分配为O(1),则此实现满足条件1).我们使数组为T*,并new在插入时使用以满足条件2)和3).最后,4)被实现,因为我们使用数组结构并且可以轻松实现O(1)访问.

Answer 1

它是特定于实现的.所有deque要求是在开始/结束时的恒定时间插入/删除,并且在其他地方最多是线性的.元素不需要是连续的.

大多数实现使用可以描述为展开列表的内容.固定大小的数组在堆上分配,指向这些数组的指针存储在属于deque的动态大小的数组中.

Answer 2

deque通常实现为数组的动态数组T.

 (a) (b) (c) (d)
 +-+ +-+ +-+ +-+
 | | | | | | | |
 +-+ +-+ +-+ +-+
  ^   ^   ^   ^
  |   |   |   |
+---+---+---+---+
| 1 | 8 | 8 | 3 | (reference)
+---+---+---+---+

阵列(a),(b),(c)和(d)通常具有固定容量,内部阵列(b)和(c)必须是满的.(a)和(d)未满,两端插入O(1).

想象我们做了很多push_front,(a)将填满,当它已满并且执行插入时我们首先需要分配一个新数组,然后增长(引用)向量并将指针推到前面的新数组.

这个实现简单地提供:

• 随机访问
• 参考保留在两端推动
• 在中间插入与之成比例min(distance(begin, it), distance(it, end))(标准比您要求的稍微严格一些)

但是,它没有按摊销O(1)增长的要求.因为每当(引用)向量需要增长时,数组都具有固定容量,所以我们有O(N /容量)指针副本.因为指针被轻易复制,memcpy所以可以进行单次调用,因此在实践中这通常是不变的...但这不足以通过飞行颜色.

仍然,push_front并且push_back比a更有效vector(除非你使用MSVC实现,因为数组的容量非常小,这是非常慢的...)

老实说,我知道没有数据结构或数据结构组合可以满足两者:

• 随机访问

和

• O(1)两端插入

我知道几个"近"的比赛:

• 分摊O(1)插入可以使用动态数组完成,在中间写入,这与"参考保存"语义不兼容 deque
• B + Tree可以通过索引而不是按键来提供访问,时间接近常量,但访问和插入的复杂度为O(log N)(使用小常量),它需要使用Fenwick树中级节点.
• 手指树可以类似地调整,但它再次真的是O(log N).

Answer 3

A deque<T>可以通过使用a正确实现vector<T*>.所有元素都复制到堆上,指针存储在向量中.(稍后有关矢量的更多信息).

为什么T*而不是T？因为标准要求

"在双端队列的任一端插入都会使deque的所有迭代器无效,但对deque元素的引用的有效性没有影响. "

(我的重点).将T*有助于满足这一点.它也有助于我们满足这一要求:

"在双端队列的开头或末尾插入单个元素总是.....导致对T的构造函数的单个调用."

现在为(有争议的)位.为什么用a vector来存储T*？它为我们提供随机访问,这是一个良好的开端.让我们暂时忘记向量的复杂性并仔细构建:

该标准谈到"所包含对象的操作次数".因为deque::push_front这显然是1,因为T只构造了一个对象,并且T以任何方式读取或扫描零个现有对象.这个数字1显然是一个常数,与目前在双端队列中的对象数量无关.这让我们可以这样说:

'对于我们来说deque::push_front,包含对象上的操作数(Ts)是固定的,并且与双端队列中已有的对象数无关.

当然,对它的操作次数T*不会那么好.当它vector<T*>变得太大时,它将被重新分配并且许多T*s将被复制.所以,是的,操作的数量T*会有很大差异,但操作次数T不会受到影响.

为什么我们关心计数操作T和计数操作之间的区别T*？这是因为标准说:

本节中的所有复杂性要求仅根据所包含对象的操作数量来说明.

对于deque,包含的对象是T,而不是T*,意味着我们可以忽略任何复制(或重新分配)a的操作T*.

我没有多说过一个向量在双端队列中的表现.也许我们会将它解释为循环缓冲区(向量总是占用它的最大值capacity(),然后在向量满时将所有内容重新分配到更大的缓冲区.细节无关紧要.

在最后几段中,我们分析deque::push_front了deque中对象数量与push_front对包含T对象执行的操作数量之间的关系.我们发现它们彼此独立.由于标准要求复杂性就操作而言T,我们可以说这具有不变的复杂性.

是的,操作在T*-Complexity是摊销的(由于vector),但我们只对操作在 - T复杂性感兴趣,这是常数(非摊销).

结语:vector :: push_back或vector :: push_front的复杂性与此实现无关; 这些考虑涉及操作T*,因此无关紧要.

Answer 4

（使这个答案成为社区维基。请参与其中。）

首先要做的事情是：Adeque要求对前面或后面的任何插入都应保持对成员元素的任何引用有效。迭代器失效是可以的，但成员本身必须保留在内存中的同一位置。只需将成员复制到堆上的某个位置并存储T*在底层的数据结构中，这就很容易了。请参阅另一个 StackOverflow 问题“关于 deque<T> 的额外间接寻址 ”

（vector不保证保留迭代器或引用，但list保留两者）。

因此，让我们认为这种“间接”是理所当然的，然后看看问题的其余部分。有趣的是从列表的开头或结尾插入或删除的时间。起初，看起来 adeque可以用 a 简单地实现vector，也许可以将其解释为循环缓冲区。

但是双端队列必须满足“在双端队列的开头或结尾插入单个元素总是需要恒定的时间并导致对 T 的构造函数的单次调用”。

由于我们已经提到了间接，很容易确保只有一个构造函数调用，但挑战是保证恒定的时间。如果我们只使用恒定的摊销时间，这将很容易，这将允许简单的vector实现，但它必须是恒定的（非摊销）时间。