Неверные результаты при добавлении вектора к себе с помощью copy и back_inserter

Вдохновленный этот вопрос, спрашивая, как добавить вектор к себе, моя первая мысль была следующей (и да, я понимаю, что insert - лучший вариант сейчас):

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> vec {1, 2, 3};
    std::copy (std::begin (vec), std::end (vec), std::back_inserter (vec));

    for (const auto &v : vec)
        std::cout << v << ' ';
}

Однако это печатает:

1 2 3 1 * 3

* Каждый раз, когда запускается программа, * - это другое число. Тот факт, что он заменяет только 2, является своеобразным, и если на самом деле есть объяснение, мне было бы интересно его услышать. Продолжая, если я добавляю к другому вектору (копию оригинала), он выводит правильно. Он также выводится правильно, если я добавлю следующую строку перед copy one:

vec.reserve (2 * vec.size());

Я был под впечатлением std::back_inserter был безопасным способом добавления элементов на конец контейнера, несмотря на то, что он не резервировал память заранее. Если мое понимание правильное, что случилось с копировальной линией?

Я предполагаю, что это не связано с компилятором, но я использую GCC 4.7.1.

Ответы

Ответ 1

std::back_inserter создает вставной итератор, который вставляет элементы в контейнер. Каждый раз, когда этот итератор разыменовывается, он вызывает push_back в контейнере, чтобы добавить новый элемент в контейнер.

Для контейнера std::vector вызов push_back, где v.size() == v.capacity() приведет к перераспределению: создается новый массив для хранения содержимого вектора, его текущее содержимое копируется в новый массив и старый массив уничтожается. Любые итераторы в вектор в это время недействительны, то есть они больше не могут использоваться.

В вашей программе это включает диапазон ввода, определенный begin(vec) и end(vec), из которого копируется алгоритм copy. Алгоритм продолжает использовать эти итераторы, даже если они недействительны, поэтому ваша программа демонстрирует поведение undefined.

Даже если ваш контейнер имел достаточную емкость, его поведение по-прежнему будет undefined: в спецификации указано, что при вставке "если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются в силе" (С++ 11 § 23.3.6.5/1).

Вызов push_back эквивалентен вставке в конце, поэтому конечный итератор (std::end(vec)), который вы передали в std::copy, недействителен после одного вызова push_back. Если входной диапазон не пуст, программа поэтому демонстрирует поведение undefined.

Обратите внимание, что поведение вашей программы было бы четко определено, если вы использовали std::deque<int> или std::list<int>, потому что ни один из этих контейнеров не отменяет итераторы при добавлении элементов.