Wondering why my memory accesses were somewhat slower than I expected, I finally figured out that the Visual C++ implementation of deque
indeed has an extra layer of indirection built-in, destroying my memory locality.
i.e. it seems to hold an array of T*
, not an array of T
.
Is there another implementation I can use with VC++ that doesn't have this "feature", or is there some way (although I consider it unlikely) to be able to avoid it in this implementation?
I'm basically looking for a vector
that has also O(1) push/pop at the front.
I guess I could implement it myself, but dealing with allocator
s and such is a pain and it would take a while to get it right, so I'd rather use something previously written/tested if possible.
Duplicates are generally permitted. Allows positional access. Extends the Collection interface.
A deque is somewhat recursively defined: internally it maintains a double-ended queue of chunks of fixed size. Each chunk is a vector, and the queue (“map” in the graphic below) of chunks itself is also a vector.
Performance, mainly. An std::deque has all of the functionality of std::vector , at least for normal use, but indexing and iterating over it will typically be somewhat slower; the same may hold for appending at the end, if you've used reserve .
Deque has some advantages associated with respect to good performance, especially for insertion and deletion at the front, whereas on the other hand, we have a vector that has some repercussions like bad performance for performing insertion and deletion from one end.
For whatever reason, at least as of MSVC 2010, the std::deque
implementation appears to make use of an unbelievably small block size (the max of 16 bytes or 1 single element if I'm not mistaken!).
This, in my experience, can result in very significant performance issues, because essentially each "block" in the data structure only ends up storing a single element, which leads to all kinds of additional overhead (time and memory).
I don't know why it's done this way. As far as I understand it setting up a deque
with such a small block size is exactly how it's not supposed to be done.
Check out the gcc stdlib
implementation. From memory they use a much larger block size.
EDIT: In an attempt to address the other issues:
std::deque
should have an extra layer of indirection. It is often implemented as a "blocked" data structure - i.e. storing an array of "nodes" where each node is itself an array of data elements. It's not ever like a linked-list - the array of nodes is never "traversed" like a list, it's always directly indexed (even in the case of 1 element per block).
Of course you can roll your own data structure that keeps some extra space at the front. It wont have worst case O(1) push/pop front/back
behaviour, and as such it wont satisfy the requirements of the std::deque
container. But if you don't care about any of that...
The C++ standard does not allow std::deque
to do reallocations on pushes to the front or back. These operations are always constant time. Not amortized, always.
The C++ standard does not have such a container. Boost doesn't have one to my knowledge (thought the Boost.Container library might; I haven't looked into it).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With