deque implementation?

[Peter Ammon]

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

 

[Jonathan Mcdougall]

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

 

[Peter Ammon]

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

 

[Neil Cerutti]

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.