what is the internal implementation of Deque - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

what is the internal implementation of Deque

what is the internal implementation of Deque# JobHunting - 待字闺中

h*e2011-12-30 08:12

1 楼

【小清新】活动落下了帷幕。
这个周末修养生息一下，大家好专心去捡彩蛋，或者去看蝠娃大超。
周末有什么好菜色的，别忘了跟版友们分享分享哦。
下个礼拜准备开始新的活动：【又快又好】。
大致方向就是不花太长的时间，做出好看好吃有营养的菜品。
细节还在酝酿，先跟大家打个招呼，下周正式公布。

l*a2011-12-30 08:12

2 楼

three properties:
1) use index to access each item
2) two direction iteration
3) insert/remove from the head and the tail

h*e2011-12-30 08:12

3 楼

在剩饭剩菜活动结束之后，我打算推出两个活动，同步进行。
一个是中式面点如馒头花卷包子等。
一个是西式各种面包蛋糕。
暂定名字是【中式面点】【西式糕点】。
详情还没有敲定，欢迎大家提意见建议。

q*x2011-12-30 08:12

4 楼

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

M*A2011-12-30 08:12

5 楼

可不可以要求加上原料照片？

a*m2011-12-30 08:12

6 楼

恩。应该是固定大小的双向链表block.

M*A2011-12-30 08:12

7 楼

最好还有制作使用工具的照片。这样大家要学起来也方便找东西和原材料。

r*t2011-12-30 08:12

8 楼

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

h*e2011-12-30 08:12

9 楼

楼上两楼的可以考虑接纳。

l*a2011-12-30 08:12

10 楼

固定大小？
how to use index?

【在 a********m 的大作中提到】

: 恩。应该是固定大小的双向链表block.

d*22011-12-30 08:12

11 楼

[在 horseone (马甲) 的大作中提到：]
：【小清新】活动落下了帷幕。
：这个周末修养生息一下，大家好专心去捡彩蛋，或者去看蝠娃大超。
：...........
建议加上制作过程图片。

v*a2011-12-30 08:12

12 楼

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

M*A2011-12-30 08:12

13 楼

这个建议好。录像不一定方便，但是有过程照片就容易好多。
不是说，一千字也抵不上一张图嘛

【在 d****2 的大作中提到】

: [在 horseone (马甲) 的大作中提到：]
: ：【小清新】活动落下了帷幕。
: ：这个周末修养生息一下，大家好专心去捡彩蛋，或者去看蝠娃大超。
: ：...........
: 建议加上制作过程图片。

a*m2011-12-30 08:12

14 楼

deque 很少用到index吧。（刚看到题目里面要求了，刚才没注意）
如果要支持这个的话用vector好一点。

【在 l*****a 的大作中提到】

: 固定大小？
: how to use index?

l*32011-12-30 08:12

15 楼

很喜欢这个活动，我现在急需方便好做又健康的饭菜

l*a2011-12-30 08:12

16 楼

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好一点。

c*a2011-12-30 08:12

17 楼

囧，我之前的两个小清新一个是中式面点（发糕），一个是西式蛋糕（草莓戚风）。。。

【在 h******e 的大作中提到】

: 在剩饭剩菜活动结束之后，我打算推出两个活动，同步进行。
: 一个是中式面点如馒头花卷包子等。
: 一个是西式各种面包蛋糕。
: 暂定名字是【中式面点】【西式糕点】。
: 详情还没有敲定，欢迎大家提意见建议。

a*m2011-12-30 08:12

18 楼

太长。。。懒的看完。。。。
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:

c*a2011-12-30 08:12

19 楼

不要啊，放过我这种最怕拍照的人吧，拍个成品照都感觉很艰难。。

【在 M*******A 的大作中提到】

: 最好还有制作使用工具的照片。这样大家要学起来也方便找东西和原材料。

r*t2011-12-30 08:12

20 楼

固定每块的 memory 大小，不固定每块的 element number.

【在 l*****a 的大作中提到】

: 固定大小？
: how to use index?

c*a2011-12-30 08:12

21 楼

如果引用的方子里有步骤图的话那就不用再帖一遍自己的山寨图了吧？

【在 h******e 的大作中提到】

: 楼上两楼的可以考虑接纳。

h*e2011-12-30 08:12

22 楼

我感觉吧，上图更直接明了。
比如用的什么粉啊，买的什么肉，切什么形状。面团发酵到什么地步，横截面气泡啊神
马的。
特别是对一些鉴定分析解说等来说有很大帮助。
但是尽管没有过程照片的话，还是鼓励大家积极参与的。
我再斟酌一下奖励方法上面怎么做个平衡吧。

【在 c*******a 的大作中提到】

: 如果引用的方子里有步骤图的话那就不用再帖一遍自己的山寨图了吧？