🔒 Locked

Deque memory format

Started by AshleysBrain Jun 7, 2006 at 10:39 AM 3 replies 600+ views

Original Post

Jun 7, 2006 at 10:39 AM

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

Zahlman

Jun 7, 2006 at 11:17 AM

Results 1 - 10 of about 94 for std::deque implementation. (0.33 seconds)

outRider

Jun 7, 2006 at 11:25 AM

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.

mfawcett

Jun 7, 2006 at 12:06 PM

Quote:
Original post by outRider
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.

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.

hplus0603

Jun 7, 2006 at 12:19 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.