Как deque управляет памятью?

Question

Есть некоторые путаницы для меня при использовании контейнера deque.

Я сравнил vector с deque, я ввел значения Integer динамически и заметил, что после того, как несколько векторов векторных объектов начинают перемещаться, и адреса были изменены, что казалось логичным. Однако объекты deque остались в одном месте в памяти даже после того, как я ввел несколько сотен целых чисел.

Это наблюдение дает мне представление о том, что deque хранит гораздо большую память, чем вектор, но если это правда, то в чем смысл динамической памяти вместо статики? Даже если это произойдет, у него где-то не хватит места памяти и нужно будет изменить место в памяти. Итак, следующий вопрос: перемещает ли он каждый объект или просто начинает использовать память в другом месте и связывает его с предыдущим местоположением?

контейнер deque поддерживает арифметику итератора, но безопасно ли его использовать? Я хочу знать, как deque управляет памятью, а не тем, как можно было бы использовать его.

Answer 1

От this std::deque reference:

... типичные реализации используют последовательность индивидуально распределенных массивов фиксированного размера

Вы могли бы думать о нем, как список массивов.

Answer 2

Deque обычно реализуется как последовательность страниц фиксированной длины элементов. Если вы добавляете элементы, когда страница заполнена, новый выделяется и добавляется в конце индекса страниц. Это гарантирует, что если вы добавляете или удаляете элементы только в конце или в начале, те, которые уже были сохранены, не перемещаются в памяти (в стандартном разговоре ссылки на существующие элементы не являются недействительными push_back, pop_back , push_front и pop_front).

Answer 3

Deque - это двойной список мини-векторов. Это означает, что адреса стабильны.

Итерационная арифметика действительна, если не выполняется операция, которая делает недействительными итераторы.

Это верно для векторов слишком