Особенность размещение элементов в std::deque

#include <iostream>
#include <deque>
int main()
{
    std::deque<int>d{ 0,1,2,3,4,5,6,7,8,9 };
    for (auto & i : d)
        std::cout << i << ":" << &i << std::endl;
    return 0;
}

Дек должен обеспечить компромисс между быстрым добавлением в конец и снятием элемента из начала (доступ за O(1)) и легким расширением. Это можно обеспечить при хранении очереди в циклическом виде в динамическом массиве, который при необходимости расширяется

При увеличении размера умножением на определенный коэффициент (например, 2) обеспечивается амортизированная сложность расширения O(1) на элемент, однако при этом могут быть моменты довольно долгой перезаписи. Кроме того, такой подход требует выделения единого куска памяти (возможно - большого).

Так устроен vector. Ему требуется обеспечивать быстрый доступ к произвольному элементу, а перед деком такой задачи не стоит.

Видимо, с целью избавления от этих недостатков выбран метод хранения дека в наборе чанков определённого размера, указатели на которые лежат в векторе.

Картинка отсюда

cppreference

The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location.

В отличии класса std::list где элементы хранятся поодиночке, преимущество - запись

0->1->2->3

И вектора std::vector где элементы хранятся вместе, преимущество - чтение

[0, 1, 2, 3]

Класс std::deque предлагает среднее меджу вышеуказаными, он хранит данные в "кусках" и является компромиссом. Cкорость чтения и записи что-то "среднее" этими двумя потому-что ему не приходится итерироватся по каждому элементу одновременно не приходится пересоздавать весь массив для вставки новых элементов.

[0, 1, 2, 3]->[4, 5, 6, 7] 

std::deque логичнее всего реализовывать как двунаправленный список, т.е. каждый элемент содержит два указателя - на предыдущий и последующий элементы. На современный компьютерах указатели 64-х битные, итого 16 байт. Было бы обидно на каждый 4 байта int иметь 16 байт служебной информации, т.е. КПД 20%. Упаковывая по 4 значения в один элемент мы доводим КПД до 50%