Comment by _4r6j

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.