Разработчик хочет дописать вектор его текущим содержимым. Определите, корректен ли такой код, и назовите бе...

#include <vector>

int main() {
    std::vector<int> v{1, 2, 3};
    v.insert(v.end(), v.begin(), v.end());
}

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

Код некорректен: передача диапазона, принадлежащего тому же std::vector, в insert приводит к неопределённому поведению. Сначала нужно создать независимую копию исходных элементов, а затем вставить диапазон этой копии.

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

Интерфейсы STL строятся вокруг диапазонов итераторов: алгоритм или контейнер получает пару [first, last) и не обязан знать, откуда эти итераторы были получены. Такой подход сделал операции обобщёнными и позволил работать с разными контейнерами и источниками данных.

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

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

При выполнении insert вектор может увеличить ёмкость и выделить новый буфер. Даже если перевыделения не происходит, сдвиг элементов вправо может перезаписать значения, на которые указывают v.begin() и v.end().

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

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

Безопасный вариант — сначала скопировать исходный диапазон в отдельный контейнер:

#include <vector>

int main() {
    std::vector<int> v{1, 2, 3};
    std::vector<int> copy = v;
    v.insert(v.end(), copy.begin(), copy.end());
}

Теперь диапазон-источник не связан с памятью v. После операции v содержит {1, 2, 3, 1, 2, 3}.

Важны две независимые причины риска. Перевыделение памяти делает прежние итераторы недействительными, а сдвиг элементов может изменить значения в ещё не прочитанной части диапазона. Поэтому простое предварительное reserve не является универсальным исправлением: оно может устранить перевыделение, но не проблему пересечения источника и места вставки.

Копирование имеет дополнительную память O(n) и суммарную линейную стоимость копирования исходных элементов. Это осознанный компромисс ради определённого поведения. Если элементы дороги для копирования, можно рассмотреть другой дизайн данных, но передавать самоссылочный диапазон напрямую всё равно нельзя.

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

Например, нужно продублировать набор идентификаторов перед пакетной обработкой. Вариант с прямым insert(v.end(), v.begin(), v.end()) короче, но его поведение не определено стандартом и может проявляться по-разному после изменения размера или версии реализации.

Можно вместо этого вручную добавлять элементы по одному. Такой подход также опасен: итерация по v одновременно с добавлением в v может привести к инвалидированию итераторов при перевыделении и изменить условие завершения цикла.

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

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

1. Достаточно ли вызвать v.reserve(2 * v.size()) перед вставкой?

   Нет. reserve предотвращает перевыделение только при достаточной новой ёмкости, но не делает самоссылочную вставку разрешённой. При вставке в середину элементы всё равно могут сдвигаться и перезаписывать значения исходного диапазона. Кроме того, стандартное требование о недопустимости итераторов из того же vector не исчезает после reserve.

2. Можно ли заменить итераторы на индексы и добавлять элементы по индексам?

   Только при корректно спроектированном алгоритме. Например, заранее сохранить исходный размер n, увеличить вектор и заполнить позиции n до 2*n, обращаясь к исходной части по индексам; это не использует инвалидируемые итераторы. Но простая запись цикла с условием i < v.size() ошибочна: размер растёт, поэтому цикл может не завершиться.

3. Относится ли проблема к любому контейнеру при вставке диапазона из самого себя?

   Нельзя автоматически переносить правила одного контейнера на другой. У контейнеров различаются требования к операциям и инвалидированию итераторов. Для std::vector передача итераторов из того же контейнера в диапазонную перегрузку insert не допускается; безопасная переносимая практика — использовать независимый источник, если документация конкретного контейнера явно не гарантирует самовставку.