Рассмотрите добавление элемента в конец std::deque. Определите, является ли обращение после операции коррек...

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d{10, 20, 30};
    auto it = d.begin() + 1;
    int& ref = d[1];
    d.push_back(40);
    std::cout << *it << ' ' << ref << '
';
}

Краткий ответ

Программа имеет неопределённое поведение: после push_back все итераторы std::deque становятся недействительными, поэтому разыменование it некорректно. Ссылка ref на существующий элемент сохраняет действительность, потому что добавление элемента в начало или конец deque не инвалидирует ссылки на элементы.

Исторический контекст

std::deque предназначен для эффективного добавления и удаления элементов с обоих концов. В отличие от непрерывного массива, контейнер не обязан хранить все элементы в одном непрерывном блоке памяти, поэтому ему проще выделять новые сегменты по мере роста.

Такой подход решает конфликт между быстрым доступом по индексу и операциями на обоих концах. Однако внутренняя структура контейнера сложнее, чем у std::vector, поэтому правила действительности итераторов и ссылок отличаются.

Постановка проблемы

В коде сохранены два разных вида доступа к одному элементу: итератор it и ссылка ref. После push_back они подчиняются разным правилам, и перенос этих правил с одного вида доступа на другой приводит к ошибке.

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

Подробное решение

Для операций push_front и push_back у std::deque действующие итераторы инвалидируются. Поэтому it нельзя использовать после d.push_back(40): нельзя ни разыменовывать его, ни сравнивать с другими итераторами контейнера, ни выполнять над ним арифметику.

При этом ссылки и указатели на уже существующие элементы сохраняют действительность при добавлении элемента на один из концов deque. Объект, на который ссылается ref, остаётся тем же элементом со значением 20, поэтому чтение ref корректно.

Код демонстрирует именно это различие:

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d{10, 20, 30};
    int& ref = d[1];
    d.push_back(40);
    std::cout << ref << '
'; // корректно: 20
}

Это не означает, что ссылки в deque стабильны при любой операции. Вставка или удаление элементов внутри контейнера может инвалидировать ссылки, указатели и итераторы в соответствии с правилами конкретной операции. Поэтому после структурной модификации нельзя автоматически считать ранее полученные дескрипторы безопасными.

Ситуация из практики

Предположим, очередь задач должна поддерживать добавление с обоих концов, а обработчик временно хранит ссылки на уже помещённые задачи. std::vector неудобен из-за возможного перераспределения памяти, которое инвалидирует ссылки, указатели и итераторы; std::list сохраняет их стабильность, но не предоставляет быстрого доступа по индексу и хуже использует кэш процессора.

std::deque может быть подходящим компромиссом: операции на концах эффективны, а ссылки на существующие элементы сохраняются при добавлении на конец. Однако сохранённые итераторы всё равно придётся получать заново после такой операции, а для доступа к элементам в середине нужно учитывать менее компактное размещение по сравнению с vector.

Практическое решение — хранить стабильный идентификатор задачи или ссылку только там, где допустимы правила deque, и не сохранять итераторы между операциями изменения контейнера. Это устраняет неопределённое поведение без перехода к более дорогой структуре данных.

Что кандидаты часто упускают

1. Вопрос: Можно ли продолжить цикл по deque после push_back, если итератор указывает не на добавленный, а на старый элемент?

   Ответ: Нет. Добавление в конец инвалидирует все итераторы deque, включая итераторы на ранее существовавшие элементы. Нужно выполнить операцию изменения до создания итераторов либо получить итератор заново после неё.

2. Вопрос: Что произойдёт со ссылкой на элемент при push_front?

   Ответ: Ссылка на уже существующий элемент сохраняет действительность, хотя его логическая позиция и индекс изменятся. Если ссылка использовалась для доступа к самому объекту, это корректно; если отдельно запоминался индекс, он может перестать обозначать тот же элемент.

3. Вопрос: Можно ли заменить итератор на указатель, чтобы сохранить безопасный доступ после push_back?

   Ответ: При добавлении в начало или конец указатель на существующий элемент сохраняет действительность так же, как ссылка. Но это правило не распространяется автоматически на вставку или удаление в середине, а указатель не даёт операций перемещения и сравнения, доступных итератору. Замена типа доступа не отменяет необходимость учитывать правила инвалидирования конкретной операции.