# Deque memory format

This topic is 4575 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

As I understand it, in STL: - Vectors are a contiguous block of memory with O(1) access time for any element, but are slow at insertion/deletion from the middle (since the entire following block has to be shifted). - Lists are doubly-linked lists, with each element in an arbitrary place in memory, alongside a pointer to the next and previous elements. Insertion/deletion from the middle is fast because it's just a bit of pointer tweaking and a new allocation. Slow random access due to traversing the list. But my understanding of deques isn't so good - how do they hold elements in memory? My project requires dynamic arrays with a fair amount of inserting/deleting from the middle but also good access time when being iterated from begin to end. I've been using deques, but how does inserting and erasing from the middle compare to vectors and lists? How does the efficiency of iterating a deque compare to iterating a vector and list? Thanks

##### Share on other sites
Deques are similar to vectors. O(1) insertion/removal at either end, linear insertion/removal elsewhere. They probably wrap a vector in most STL implementations anyway. If you're using MSVC, look up Dinkumware's STL reference, as far as I remember MSVC still uses Dinkumware's STL implementation. If you use GCC look around the GNU web site.

##### Share on other sites
Quote:
 Original post by outRiderDeques are similar to vectors. O(1) insertion/removal at either end, linear insertion/removal elsewhere. They probably wrap a vector in most STL implementations anyway.

They are certainly similar, but they are not implemented as a wrapper around a vector. deques have efficient insertion/deletion at the front of the container, which a vector can't give.

##### Share on other sites
A deque typically will store elements in blocks of N. Then it'll store a separate index to the blocks. Last, the first and last blocks can be half full (this allows efficient insertion in the beginning). This also allows the deque to use less memory in exponential growth, as blocks are only allocated when referenced (only the pointer array needs exponential re-size to provide factored constant operation time).

The draw-back is that there's some constant factor (one additional memory access) of slowdown per random access, plus the additional 4 byte overhead per stored block.

The default block size is surprisingly small; something like 4 items in STLPort IAICR.

1. 1
2. 2
Rutin
20
3. 3
A4L
15
4. 4
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633739
• Total Posts
3013619
×