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