Sign in to follow this  
AshleysBrain

Deque memory format

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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this