By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,433 Members | 1,665 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,433 IT Pros & Developers. It's quick & easy.

deque implementation?

P: n/a
According to SGI's STL reference, a deque:

Supports amortized constant time random access (like a vector)
Allows amortized constant time insertions at the beginning and end

One way you could implement this would be to allocate a chunk of memory
and start in the middle rather than in the beginning, but then deque
would have a reserve() function. So how is deque usually implemented?

Thanks,
-Peter

Nov 22 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Peter Ammon wrote:
According to SGI's STL reference, a deque:

Supports amortized constant time random access (like a vector)
Allows amortized constant time insertions at the beginning and end

One way you could implement this would be to allocate a chunk of memory
and start in the middle rather than in the beginning, but then deque
would have a reserve() function. So how is deque usually implemented?


No, it is usually an array of arrays. One end grows from 0 to x and the
other grows from x to 0.

......<=
=======
=======
=>.....
Jonathan

Nov 22 '05 #2

P: n/a

Jonathan Mcdougall wrote:
Peter Ammon wrote:
According to SGI's STL reference, a deque:

Supports amortized constant time random access (like a vector)
Allows amortized constant time insertions at the beginning and end

One way you could implement this would be to allocate a chunk of memory
and start in the middle rather than in the beginning, but then deque
would have a reserve() function. So how is deque usually implemented?


No, it is usually an array of arrays. One end grows from 0 to x and the
other grows from x to 0.

.....<=
=======
=======
=>.....


Thanks for your reply, but I am still confused. How do you manage this
array of subarrays? You need the ability to insert a subarray at
either end with good performance to maintain the deque's performance
contract. What data structure allows you to insert stuff at either end
with good performance? A deque, of course. You can see my confusion.

To put it another way: Let's say a deque is a naive array of arrays;
how long is each of these subarrays? If each is a fixed length, say,
L, then inserting L elements into the beginning of a deque of N
elements will require allocating a new subarray, moving every subarray
pointer in the outer array forward by one, and then inserting the new
subarray at the beginning. That second step requires you to copy N/L
pointers to insert L elements; the work per element is therefore
N/L**L, which is O(N). But a deque is supposed to have O(1)
insertions.

-Peter

Nov 22 '05 #3

P: n/a
On 2005-11-17, Peter Ammon <pa****@gmail.com> wrote:

Jonathan Mcdougall wrote:
Peter Ammon wrote:
> According to SGI's STL reference, a deque:
>
> Supports amortized constant time random access (like a vector)
> Allows amortized constant time insertions at the beginning and end
>
> One way you could implement this would be to allocate a chunk of memory
> and start in the middle rather than in the beginning, but then deque
> would have a reserve() function. So how is deque usually implemented?
No, it is usually an array of arrays. One end grows from 0 to x and the
other grows from x to 0.

.....<=
=======
=======
=>.....


Thanks for your reply, but I am still confused. How do you manage this
array of subarrays? You need the ability to insert a subarray at
either end with good performance to maintain the deque's performance
contract. What data structure allows you to insert stuff at either end
with good performance? A deque, of course. You can see my confusion.

To put it another way: Let's say a deque is a naive array of
arrays; how long is each of these subarrays? If each is a
fixed length, say, L, then inserting L elements into the
beginning of a deque of N elements will require allocating a
new subarray, moving every subarray pointer in the outer array
forward by one, and then inserting the new subarray at the
beginning.


Yes, and the memory will be allocated in such a way that this
seldom happens, as with a vector.
That second step requires you to copy N/L pointers to insert L
elements; the work per element is therefore N/L**L, which is
O(N). But a deque is supposed to have O(1) insertions.


O(1) amortized time. I think that's how they put it. Memory
allocation won't have to take place very often with a good
implementation.

A good and simple approach doubles the size whenever capacity
fills up. Starting from zero capacity, it requires only 14
allocations for 10000 calls to push_front. So log2(N) times out
of N, performance is O(N). That's a very small ratio.

--
Neil Cerutti
Nov 22 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.