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 allocators 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.
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).
The indirection you complain about is actually mandated by the standard requirement that references/pointers are never invalidated by push/pop front/back (except those references/pointers to removed elements, obviously).
So you see that this requirement has nothing to do with any complexity requirement.
This indirection also allows for faster (but still O(size)) push front/back when there is no available room.
