So, I have been working on a devector implementation for the last week or so (see https://svn.boost.org/trac/boost/wiki/soc2009#Boost.Devector). There is some stuff that still needs to be done, and some testing that is still needed, but I thought I would check if there was interest in such a thing. The implementation is basically a standard deque implementation with one addition. That is, there can be allocated "chunks" both before and after those in use. This leads to a couple of advantages for users. First, in many use cases, devector is faster than deque because it will have less allocations. For example, when used strictly as a queue, the regular deque has a number of chunk allocations linear in the total number of elements inserted in the queue, devector has allocation linear in the maximum elements in the deque at one time. When used as a stack, a particularly bad case can occur with a normal deque implementation, the case where the top of the stack switches back and forth between two chunks. Second, this allows users of devector to reserve space on either side of the structure. This does not give the same efficiency boost as vector::reserve, but, possibly more important, it allows for stronger exception guarantees and for better guarantees about when iterators are invalidated. Another benefit of devector is that chunk size is not a compile time constant. In fact, chunk size is not even required to be constant over the lifetime of a given devector. Also, devector iterators allow lower level access than std::deque as described by Matt Austern ( http://lafstern.org/matt/segmented.pdf). Support for in-place construction (described at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2212.html) will become available with c++0x's emplace_back(). Though I expected that std::deque would have a slight performance advantage due to its compile-time constant chunk_size, early tests have actually shown devector to have a slight advantage even in cases where it has no advantage from not deallocating unused blocks. My guess is that this is due to std::deque needing to do more work to maintain its invariants in the face of exceptions. Again though, that is just some simple early testing that I did. The current implementation does not actually allow changing chunk_size (though this is actually a matter of like 5 LOC), nor does it give the segmented iterator access (again a simple addition). Code is available at http://pages.cs.wisc.edu/~hopman/devector/ (along with code that tests most of the std::deque interface). -Chris Hopman