什么数据结构，确切，是在C ++的deques？ [英] What data structure, exactly, are deques in C++?

问题描述

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

我以前总是假定一个deque是一个循环缓冲区，但我最近正在阅读一个C ++参考资料这里，它听起来像一个deque是某种数组数组。它似乎不是一个简单的老循环缓冲区。是间隙缓冲区，然后是可扩展数组的一些其他变体，还是仅仅是实现相关的？

解答的更新和摘要：

似乎一般的共识是deque是一种数据结构，使得：

• 插入或删除元素的时间应该在列表的开头或结尾处为常量，并且在其他位置最多为线性。如果我们解释这意味着真正的恒定时间，而不是摊还的恒定时间，正如有人评论，这似乎具有挑战性。有些人认为我们不应该将这种情况解释为非摊销的常数时间。


• deque要求任何插入都应该保留对成员元素的任何引用。被无效，但成员本身必须在记忆中保持在同一个地方。正如有人评论：只需将成员复制到堆上的某个位置并将T *存储在数据结构中即可。


• 在开始时插入单个元素或deque的结束总是占用恒定的时间，并导致对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 *，并在插入满足条件2）和3）时使用 new 。最后，由于我们使用数组结构并且可以轻松地实现O（1）访问，所以满足了4）。

解决方案

第一件事：A deque 要求任何插入到前面或后面应保持对成员元素的任何引用有效。迭代器可以无效，但是成员本身必须保持在内存中的相同位置。这很容易，只需将成员复制到堆上的某个位置，并在数据结构中保存 T * 即可。请参阅此其他StackOverflow问题关于deque& T的额外间接

（向量不保证保留迭代器或引用，而 / code>保存两者）。

因此，让我们把这个'间接'视为理所当然，看看剩下的问题。有趣的位是从列表的开始或结束插入或删除的时间。首先，看起来像 deque 可以通过向量来实现，也许通过将其解释为循环缓冲区。

但配置必须满足在
deque的开头或结尾插入单个元素总是因为我们已经提到了间接，所以很容易确保只有一个T的构造函数。

一个构造函数调用，但挑战是保证恒定的时间。如果我们可以使用常数 amortized 时间，这将容易，这将允许简单的向量实现，但它必须是常数）时间。

Is there a specific data structure that a deque in the C++ STL is supposed to implement, or is a deque just this vague notion of an array growable from both the front and the back, to be implemented however the implementation chooses?

I used to always assume a deque was a circular buffer, but I was recently reading a C++ reference here, and it sounds like a deque is some kind of array of arrays. It doesn't seem like it's a plain old circular buffer. Is it a gap buffer, then, or some other variant of growable array, or is it just implementation-dependent?

UPDATE AND SUMMARY OF ANSWERS:

It seems the general consensus is that a deque is a data structure such that:

• the time to insert or remove an element should be constant at beginning or end of the list and at most linear elsewhere. If we interpret this to mean true constant time and not amortized constant time, as someone comments, this seems challenging. Some have argued that we should not interpret this to mean non-amortized constant time.
• "A deque requires that any insertion shall keep any reference to a member element valid. It's OK for iterators to be invalidated, but the members themselves must stay in the same place in memory." As someone comments: This is easy enough by just copying the members to somewhere on the heap and storing T* in the data structure under the hood.
• "Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a constructor of T." The single constructor of T will also be achieved if the data structure stores T* under the hood.
• The data structure must have random access.

It seems no one knows how to get a combination of the 1st and 4th conditions if we take the first condition to be "non-amortized constant time". A linked list achieves 1) but not 4), whereas a typical circular buffer achieves 4) but not 1). I think I have an implementation that fulfills both below. Comments?

We start with an implementation someone else suggested: we allocate an array and start placing elements from the middle, leaving space in both the front and back. In this implementation, we keep track of how many elements there are from the center in both the front and back directions, call those values F and B. Then, let's augment this data structure with an auxiliary array that is twice the size of the original array (so now we're wasting a ton of space, but no change in asymptotic complexity). We will also fill this auxiliary array from its middle and give it similar values F' and B'. The strategy is this: every time we add one element to the primary array in a given direction, if F > F' or B > B' (depending on the direction), up to two values are copied from the primary array to the auxiliary array until F' catches up with F (or B' with B). So an insert operation involves putting 1 element into the primary array and copying up to 2 from the primary to the auxiliary, but it's still O(1). When the primary array becomes full, we free the primary array, make the auxiliary array the primary array, and make another auxiliary array that's yet 2 times bigger. This new auxiliary array starts out with F' = B' = 0 and having nothing copied to it (so the resize op is O(1) if a heap allocation is O(1) complexity). Since the auxiliary copies 2 elements for every element added to the primary and the primary starts out at most half-full, it is impossible for the auxiliary to not have caught up with the primary by the time the primary runs out of space again. Deletions likewise just need to remove 1 element from the primary and either 0 or 1 from the auxiliary. So, assuming heap allocations are O(1), this implementation fulfills condition 1). We make the array be of T* and use new whenever inserting to fulfill conditions 2) and 3). Finally, 4) is fulfilled because we are using an array structure and can easily implement O(1) access.

解决方案

(Making this answer a community-wiki. Please get stuck in.)

First things first: A deque requires that any insertion to the front or back shall keep any reference to a member element valid. It's OK for iterators to be invalidated, but the members themselves must stay in the same place in memory. This is easy enough by just copying the members to somewhere on the heap and storing T* in the data structure under the hood. See this other StackOverflow question " About deque<T>'s extra indirection "

(vector doesn't guarantee to preserve either iterators or references, whereas list preserves both).

So let's just take this 'indirection' for granted and look at the rest of the problem. The interesting bit is the time to insert or remove from the beginning or end of the list. At first, it looks like a deque could trivially be implemented with a vector, perhaps by interpreting it as a circular buffer.

BUT A deque must satisfy "Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a constructor of T."

Thanks to the indirection we've already mentioned, it's easy to ensure there is just one constructor call, but the challenge is to guarantee constant time. It would be easy if we could just use constant amortized time, which would allow the simple vector implementation, but it must be constant (non-amortized) time.

这篇关于什么数据结构，确切，是在C ++的deques？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！