An important point is that the STL deque also supports random access (using iterators), not just O(1) insertions/deletions. I have not looked at the source code, but I'm 99.9% certain that the circularised array they talk about in the Wikipedia entry on deques is how it's done. Using an array, push_front inserts at the head of the deque by looking for the current index of the head in the array. The new index is just (current_head_index - 1) % array_size... so if the head is at index 0, the new head will be at the very end of the array. Similarly with inserting at the tail, if the tail reaches the end of the array, but the 0 index element is empty... loop the tail around to the beginning of the array, using (current_tail + 1) % array_size.
Once the whole array is full, allocate a bigger array and copy everything over. Since adding and deleting items only happens at the ends, there's no item shifting involved, except when this happens. So this is O(1). But since the storage structure is actually an array, iterators can easily be used for random access. Access is constant because both the front and the back have references in the container, so this is simply following a pointer. -- View this message in context: http://www.nabble.com/C%2B%2B-question%3A-how-is-STL-%27s-deque-implemented--tp23348211p24506524.html Sent from the C-prog mailing list archive at Nabble.com.
