There are weasel words in the standard that let implementations still be pretty inefficient. The problem is that memory reallocation is a leaky abstraction, and an interface that doesn't make guarantees about memory behavior can't be relied upon at scale.
The implementation of std::deque I just read uses a circular queue, resized to a power of two upon growth. It would exhibit the same bad performance as std::vector.
Are you sure? You're not allowed to invalidate iterators or pointers to elements in a deque, so it shouldn't be reallocating memory (aside from its underlying map of nodes, which will need to grow very rarely).
The implementation of std::deque I just read uses a circular queue, resized to a power of two upon growth. It would exhibit the same bad performance as std::vector.