How does deque manage memory?

Question

There are some confusion for me in using deque container.

I compared a vector with a deque, I entered Integer values dynamically and observed that after a few insertions vector's objects start moving around and addresses have been changed which seemed logical. However deque's objects stayed on the same place in the memory even after I entered a few hundred integers.

This observation gives me the idea that deque reserves a much larger memory than vector but if it is true then what is the point of having dynamic memory instead of static? Even if it does, it will run out of memory at somewhere and need to change the place on the memory, So the next question is does it move every object or just start using memory somewhere else and links it with previous location?

deque container supports iterator arithmetic but is it safe to use it? i want to know how deque manage the memory not how one might prefer to use it.

Answer 1

A deque is a double linked list of mini vectors. That means addresses are stable.

Iterator arithmetic is valid unless operation which invalidates iterators is performed.

This is true for vectors too

Answer 2

From this std::deque reference:

... typical implementations use a sequence of individually allocated fixed-size arrays

You could think of it like a list of arrays.

Answer 3

A deque is typically implemented as a sequence of fixed-length pages of elements. If you append elements, when a page is full a new one is allocated and added at the end of the pages index. This guarantees that, if you add or remove elements only at the end or at the beginning, the ones that have already been stored aren't moved around in memory (in standardese speak, references to existing elements aren't invalidated by push_back, pop_back, push_front and pop_front).