l*****a
发帖数: 14598 | 1 three properties:
1) use index to access each item
2) two direction iteration
3) insert/remove from the head and the tail |
q****x
发帖数: 7404 | 2 chunk？
【在 l*****a 的大作中提到】
: three properties:
: 1) use index to access each item
: 2) two direction iteration
: 3) insert/remove from the head and the tail
|
a********m
发帖数: 15480 | |
r****t
发帖数: 10904 | 4 it uses array of arrays, with some smart iterators jumping from one array to
another.
【在 l*****a 的大作中提到】
: three properties:
: 1) use index to access each item
: 2) two direction iteration
: 3) insert/remove from the head and the tail
|
l*****a
发帖数: 14598 | 5 固定大小？
how to use index?
【在 a********m 的大作中提到】
: 恩。应该是固定大小的双向链表block.
|
v***a
发帖数: 365 | 6 Don't use it. the implementation is too bad.
【在 l*****a 的大作中提到】
: three properties:
: 1) use index to access each item
: 2) two direction iteration
: 3) insert/remove from the head and the tail
|
a********m
发帖数: 15480 | 7 deque 很少用到index吧。 （刚看到题目里面要求了，刚才没注意）
如果要支持这个的话用vector好一点。
【在 l*****a 的大作中提到】
: 固定大小？
: how to use index?
|
l*****a
发帖数: 14598 | 8 if so, how do u push_front and pop_front
Double ended queue
deque (usually pronounced like "deck") is an irregular acronym of double-
ended queue. Double-ended queues are a kind of sequence container. As such,
their elements are ordered following a strict linear sequence.
Deques may be implemented by specific libraries in different ways, but in
all cases they allow for the individual elements to be accessed through
random access iterators, with storage always handled automatically (
expanding and contracting as needed).
Deque sequences have the following properties:
Individual elements can be accessed by their position index.
Iteration over the elements can be performed in any order.
Elements can be efficiently added and removed from any of its ends (either
the beginning or the end of the sequence).
Therefore they provide a similar functionality as the one provided by
vectors, but with efficient insertion and deletion of elements also at the
beginning of the sequence and not only at its end. On the drawback side,
unlike vectors, deques are not guaranteed to have all its elements in
contiguous storage locations, eliminating thus the possibility of safe
access through pointer arithmetics.
Both vectors and deques provide thus a very similar interface and can be
used for similar purposes, but internally both work in quite different ways:
While vectors are very similar to a plain array that grows by reallocating
all of its elements in a unique block when its capacity is exhausted, the
elements of a deques can be divided in several chunks of storage, with the
class keeping all this information and providing a uniform access to the
elements. Therefore, deques are a little more complex internally, but this
generally allows them to grow more efficiently than the vectors with their
capacity managed automatically, specially in large sequences, because
massive reallocations are avoided.
For operations that involve frequent insertion or removals of elements at
positions other than the beginning or the end, deques perform worse and have
less consistent iterators and references than lists.
【在 a********m 的大作中提到】
: deque 很少用到index吧。 （刚看到题目里面要求了，刚才没注意）
: 如果要支持这个的话用vector好一点。
|
a********m
发帖数: 15480 | 9 太长。。。懒的看完。。。。
random access不从中间添加删除就没关系，iteration比random access容易。另外两
个offset值对应开头和结尾就可以了吧。添加删除就是增减offset值，需要的时候调整
vector。
,
【在 l*****a 的大作中提到】
: if so, how do u push_front and pop_front
: Double ended queue
: deque (usually pronounced like "deck") is an irregular acronym of double-
: ended queue. Double-ended queues are a kind of sequence container. As such,
: their elements are ordered following a strict linear sequence.
: Deques may be implemented by specific libraries in different ways, but in
: all cases they allow for the individual elements to be accessed through
: random access iterators, with storage always handled automatically (
: expanding and contracting as needed).
: Deque sequences have the following properties:
|
r****t
发帖数: 10904 | 10 固定每块的 memory 大小，不固定每块的 element number.
【在 l*****a 的大作中提到】
: 固定大小？
: how to use index?
|
