The advice I've always read about std::deque is that unless you can measure a performance difference, it's better to simply default to std::vector as the cache advantages of laying everything out in a contiguous block of memory cover for many of its "Big O" sins.

Something interesting I've come across is a so-called Veque which tries to claw back some of the on-paper advantages of a std::deque but with a performance of a std::vector by keeping scratch space both before and after the used data. Can't speak to its usefulness personally, but it does look neat.