用几个向量实现双端队列？ [英] Implementing deque with a couple of vectors?
问题描述
你好，
我最近一直试图通过c ++了解所提供的各种结构
，而我发现最令人困惑的是deque 。
一个关于此的快速问题。似乎大多数deque
的实现都非常复杂。为什么我不能用几个
向量V，W实现deque，其中deque是反向顺序的V元素
后跟W？在我看来，这将满足所有条件，
并且要简单得多。我错过了一些明显的东西吗？
Chris
"克里斯" < CH *** @ bubblescope.net>在消息中写道
news：cl ********** @ pump1.york.ac.uk ...你好，
<我最近一直试图理解由
c ++提供的各种结构，而我发现最令人困惑的是deque。
一个关于此的快速问题。似乎deque的大多数实现都非常复杂。为什么我不能用几个向量V，W来实现deque，其中deque是V的元素，反之后是W？在我看来，这将满足所有条件，并且显着更简单。我错过了一些明显的东西吗？
Chris
矢量和deques之间存在一些差异。在前后插入（恒定时间）时，deque非常优秀。一个deque不会将元素存储在连续的内存块中，比如矢量，但是在链接的
块中。这意味着当大小
变得大于容量时（例如向量），它不会重新分配内存，而是
分配一个新的内存阻止并将其链接到最后使用的块。
br /
Catalin
Catalin Pitis写道：
矢量和deques之间存在一些差异。 deque在前后插入时非常有效（恒定时间）。 deque不会将元素存储在连续的内存块中，例如矢量，而是存储在
链接的块中。这意味着当大小
变得大于容量时（例如向量），它不会重新分配内存，而是分配一个新的内存块并将其链接到最后一个块使用。
Herb Sutter建议使用deque作为默认容器，无需使用另一个。
新问题：
deque是否比向量更有时间效率？它是否比
列表更具内存效率？
deque听起来类似于我称之为Rope的数据结构。这是'
专为超长动态字符串而设计的。当你在块的中间插入一个
字符时，Rope可能会分割该块，并且
可能会将新字符放入较低的块中，之后会有一个保留区域
角色，期待更多。这自然会为编辑们调整。
deque在插入时拆分这样的块吗？
块拆分需要最终的堆压缩。怎么可能deque支持
那个？ （自定义内存分配器无需申请！）
-
Phlip
http://industrialxp.org/community/bi...UserInterfaces
Catalin Pitis写道：" chris" < CH *** @ bubblescope.net>在消息中写道
新闻：cl ********** @ pump1.york.ac.uk ...
你好，
<我最近一直试图理解由
c ++提供的各种结构，而我发现最令人困惑的是deque。
一个关于此的快速问题。似乎deque的大多数实现都非常复杂。为什么我不能用几个向量V，W来实现deque，其中deque是V的元素，反之后是W？在我看来，这将满足所有条件，并且显着更简单。我错过了一些明显的东西吗？
Chris
矢量和deques之间存在一些差异。 deque在前后插入时非常有效（恒定时间）。 deque不会将元素存储在连续的内存块中，例如矢量，而是存储在链接的块中。这意味着当大小
变得大于容量时（例如向量），它不会重新分配内存，而是分配一个新的内存块并将其链接到最后一个块使用。
我已经读过声明deque可以在
开始和结束以及恒定时间随机访问中进行恒定时间插入。但是可以
来满足这两个要求。我怀疑在开头和结尾的插入只需要摊销恒定时间吗？
如果要实现恒定时间随机访问，那么我们就可以''简单地说
使用一个块列表，否则访问一个任意元素将是
线性？
Chris
Hello,
I''ve recently been trying to understand the various structures supplied
by c++, and the one I find most confusing is deque.
One quick question about this. It seems most implementations of deque
are quite complex. Why couldn''t I implement deque with a couple of
vectors V,W where the deque is the element of V in reverse order
followed by W? This would appear to me to satisfy all the conditions,
and be significantly simpler. Am I missing something obvious?
Chris
"chris" <ch***@bubblescope.net> wrote in message
news:cl**********@pump1.york.ac.uk...Hello,
I''ve recently been trying to understand the various structures supplied by
c++, and the one I find most confusing is deque.
One quick question about this. It seems most implementations of deque are
quite complex. Why couldn''t I implement deque with a couple of vectors V,W
where the deque is the element of V in reverse order followed by W? This
would appear to me to satisfy all the conditions, and be significantly
simpler. Am I missing something obvious?
Chris
There are some differences between vectors and deques. A deque is very
performant at front and back insertions (constant time). A deque doesn''t
store the elements in a continuous memory block, like vectors, but in linked
blocks. This means that it doesn''t reallocate memory when the the size
becomes greater than capacity (like in the case of a vector), but instead
allocates a new memory block and links it to the last block used.
br/
Catalin
Catalin Pitis wrote:
There are some differences between vectors and deques. A deque is very
performant at front and back insertions (constant time). A deque doesn''t
store the elements in a continuous memory block, like vectors, but in linked blocks. This means that it doesn''t reallocate memory when the the size
becomes greater than capacity (like in the case of a vector), but instead
allocates a new memory block and links it to the last block used.
Herb Sutter recommends deque as the default container without a reason to
use another.
New questions:
Is deque more time efficient than vector? Is it more memory efficient than
list?
deque sounds similar to a data structure which I''l call "Rope". That''s
designed for extra long and highly dynamic strings. When you insert a
character into the middle of the block, Rope might split the block, and
might put the new character into the lower block, with a reserved area after
the character, anticipating more. This naturally tunes for editors.
Does deque split blocks like that at insert time?
Block splitting requires eventual heap compaction. How could deque support
that? (Custom memory allocators need not apply!)
--
Phlip
http://industrialxp.org/community/bi...UserInterfaces
Catalin Pitis wrote:"chris" <ch***@bubblescope.net> wrote in message
news:cl**********@pump1.york.ac.uk...Hello,
I''ve recently been trying to understand the various structures supplied by
c++, and the one I find most confusing is deque.
One quick question about this. It seems most implementations of deque are
quite complex. Why couldn''t I implement deque with a couple of vectors V,W
where the deque is the element of V in reverse order followed by W? This
would appear to me to satisfy all the conditions, and be significantly
simpler. Am I missing something obvious?
Chris
There are some differences between vectors and deques. A deque is very
performant at front and back insertions (constant time). A deque doesn''t
store the elements in a continuous memory block, like vectors, but in linked
blocks. This means that it doesn''t reallocate memory when the the size
becomes greater than capacity (like in the case of a vector), but instead
allocates a new memory block and links it to the last block used.
I''ve read claims that a deque can do constant time insertions at the
beginning and end and constant time random access. However is possible
to satisfy both of these requirements. I suspect that the insertions at
the beginning and end are only required to be amortized constant time?
If constant time random access is to be achieved, then we can''t simply
be using a list of blocks else accessing an arbitary element would be
linear?
Chris
这篇关于用几个向量实现双端队列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
