Почему std::deque нельзя передать API, требующему непрерывный диапазон, хотя у него есть быстрый доступ по индексу?
std::deque обеспечивает быстрый доступ по индексу, но не гарантирует непрерывное размещение всех элементов в памяти. Поэтому его нельзя безопасно рассматривать как единый массив и передавать API, которому нужен указатель на непрерывный диапазон, например std::span или функция, работающая с парой указатель–размер.
std::vector оптимизирован под последовательное хранение элементов и эффективное расширение в конце. std::deque предназначен для эффективной вставки и удаления элементов с обоих концов, поэтому его модель хранения должна позволять добавлять новые участки памяти без перемещения всего существующего диапазона.
Такое различие решает разные задачи: vector удобен для непрерывного буфера, а deque — для двусторонней очереди с доступом по индексу.
Наличие операции индексирования не означает непрерывность памяти. У deque соседние логические элементы могут находиться в разных сегментах, поэтому арифметика указателей между ними некорректна, а передача адреса первого элемента вместе с размером не описывает весь контейнер.
Если ошибочно передать часть deque как непрерывный массив, API может прочитать данные за пределами одного сегмента. Это приводит к неопределённому поведению или к обработке посторонней памяти.
Контейнер std::deque гарантирует произвольный доступ за константное время, поэтому выражение с индексом не требует последовательного прохода. Однако стандарт не предоставляет ему свойства contiguous_range: элементы не обязаны занимать один непрерывный участок памяти.
Обычно deque реализуют как набор блоков и структуру, хранящую сведения об этих блоках. Переход к элементу включает вычисление нужного блока и смещения внутри него. Такая организация позволяет добавлять блоки с начала или конца без обязательного перемещения всех элементов, но лишает контейнер гарантии единого массива.
У std::vector элементы гарантированно расположены непрерывно, поэтому его диапазон можно передать как указатель на первый элемент и количество элементов, если время жизни контейнера и отсутствие перемещающих операций обеспечены. Для deque такой способ допустим только для отдельного непрерывного участка, если API явно поддерживает подобную модель, но не для всего контейнера.
Если API требует непрерывный диапазон, возможны три решения:
При этом итераторы deque имеют категорию произвольного доступа, но категория итератора описывает операции перемещения и сравнения, а не непрерывность адресов элементов.
Сервис сериализации принимает адрес первого элемента и число объектов, рассчитывая выполнить один последовательный проход по памяти. Разработчик выбирает deque из-за частых добавлений с обеих сторон и пытается передать в сервис весь контейнер.
Использовать deque напрямую опасно: быстрый доступ по индексу не создаёт гарантии непрерывного хранения. Скопировать данные во временный vector проще и безопаснее, но добавляет время и память на копирование. Перейти на vector выгодно, если двусторонние операции не являются критичными; иначе лучше изменить сериализатор на обработку диапазона через итераторы или адаптер диапазона.
Выбор зависит от контракта API: для действительно массивного интерфейса используется vector или копия в vector, а для алгоритма, которому достаточно последовательного обхода, сохраняется deque и меняется способ передачи данных.
Нет. Произвольный доступ означает, что переход к элементу по позиции выполняется за константное время. Он не требует, чтобы адрес элемента вычислялся простым прибавлением индекса к адресу первого элемента. Именно поэтому deque может поддерживать индексирование без свойства непрерывного диапазона.
Нельзя считать это корректным способом передачи всего deque. Адрес первого элемента относится только к конкретному объекту элемента, а последующие логические элементы могут находиться в других сегментах. Такой интерфейс допустим лишь для API, которому передают заранее известный непрерывный поддиапазон и который не выходит за его границы; для всего deque это не гарантируется.
При непрерывном хранении вставка в начало обычно требует сдвига существующих элементов или резервирования свободного пространства перед первым элементом. Это может стоить линейного времени и усложнять управление ёмкостью. Сегментированное хранение позволяет добавлять память отдельными блоками и избегать обязательного перемещения всего диапазона, жертвуя совместимостью с интерфейсами, требующими единый массив.