iterating over vectors (of trivial types that aren't pointers) is generally going to be faster since the memory is contiguous. deque is implemented with chunks i believe? loading in new chunk could be cache eviction.
I was thrown for a bit of a loop working through virtual vs actual memory addresses and how this works under the hood, but it makes more sense now. In that case then virtual_vec would be better than std::deque in terms of iterating over the contained data in order.