Перемещает ли вектор аннулировать итераторы?

Если у меня есть итератор в вектор a, то я перемещаю-строю или переношу-присваиваю вектор b из a, делает ли этот итератор все тот же элемент (теперь в векторе b)? Вот что я имею в виду в коде:

#include <vector>
#include <iostream>

int main(int argc, char *argv[])
{
    std::vector<int>::iterator a_iter;
    std::vector<int> b;
    {
        std::vector<int> a{1, 2, 3, 4, 5};
        a_iter = a.begin() + 2;
        b = std::move(a);
    }
    std::cout << *a_iter << std::endl; // Is a_iter valid here?
    return 0;
}

Является ли a_iter еще действительным, так как a был перемещен в b, или итератор недействителен при перемещении? Для справки, std::vector::swap не делает недействительными итераторы.

Ответы

Ответ 1

Хотя может быть разумным предположить, что iterator по-прежнему действуют после move, я не думаю, что стандарт действительно гарантирует это. Поэтому итераторы находятся в состоянии undefined после move.

В стандарте нет ссылки, в которой конкретно указано, что итераторы, существовавшие до move, по-прежнему действуют после move.

На поверхности, как представляется, вполне разумно предположить, что iterator обычно реализуется как указатели на управляемую последовательность. Если это так, то итераторы все равно будут действительны после move.

Но реализация iterator определяется реализацией. Смысл, если iterator на конкретной платформе соответствует требованиям, установленным Стандартом, он может быть реализован любым способом. Теоретически он может быть реализован как комбинация указателя назад к классу vector наряду с индексом. Если это так, то итераторы становятся недействительными после move.

Независимо от того, действительно ли реализован iterator, этот способ не имеет значения. Он может быть реализован таким образом, поэтому без конкретной гарантии от Стандарта, что итераторы post-move остаются в силе, вы не можете предположить, что они есть. Имейте в виду также, что есть такая гарантия для итераторов после a swap. Это было специально разъяснено из предыдущего Стандарта. Возможно, это был просто контроль над комитетом Std, чтобы не сделать аналогичные разъяснения для итераторов после move, но в любом случае такой гарантии нет.

Следовательно, длинные и короткие, вы не можете предположить, что ваши итераторы по-прежнему хороши после move.

EDIT:

23.2.1/11 в проекте n3242 гласит, что:

Если не указано иное (либо явно, либо путем определения функция в терминах других функций), вызывая член контейнера функции или передачи контейнера в качестве аргумента функции библиотеки не должны аннулировать итераторы или изменять значения объектов внутри этого контейнера.

Это может привести к выводу, что итераторы действительны после move, но я не согласен. В вашем примере кода a_iter был итератором в vector a. После move, этот контейнер, a, безусловно, был изменен. Мой вывод - это вышеприведенный пункт не применяется в этом случае.

Ответ 2

Я думаю, что редактирование, которое изменило конструкцию перемещения, чтобы переместить назначение, изменяет ответ.

По крайней мере, если я правильно читаю таблицу 96, сложность построения перемещения задается как "примечание B", которое является постоянной сложностью для чего-либо, кроме std::array. Однако сложность назначения перемещения задается как линейная.

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

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

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

Ответ 3

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

Ответ 4

tl; dr: Да, перемещение a std::vector<T, A> возможно делает недействительными итераторы

Общий случай (с std::allocator на месте) заключается в том, что недействительность не выполняется, но нет никаких компиляторов гарантии и переключения, или даже следующее обновление компилятора может привести к неправильному действию вашего кода, если вы полагаетесь на то, что ваша реализация в настоящее время не делает недействительными итераторы.

При назначении перемещения:

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

В каждой реализации, которую я видел, move-присваивание std::vector<T, std::allocator<T>> 1 фактически не приведет к аннулированию итераторов или указателей. Однако существует проблема, когда дело доходит до использования этого, поскольку стандарт просто не может гарантировать, что итераторы остаются действительными для любого перемещения-назначения экземпляра std::vector в общем случае, поскольку контейнер является распределителем.

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

Пусть:

std::vector<T, A> a{/*...*/};
std::vector<T, A> b;
b = std::move(a);

Теперь, если

  • std::allocator_traits<A>::propagate_on_container_move_assignment::value == false &&
  • std::allocator_traits<A>::is_always_equal::value == false && (возможно, из С++ 17)
  • a.get_allocator() != b.get_allocator()

то b будет выделять новое хранилище и перемещать элементы a один за другим в это хранилище, тем самым аннулируя все итераторы, указатели и ссылки.

Причина в том, что выполнение вышеуказанного условия 1. запрещает переводить назначение распределителя при перемещении контейнера. Поэтому нам приходится иметь дело с двумя разными экземплярами распределителя. Если эти два объекта-распределителя теперь не всегда сравниваются с равными (2.) и не сравниваются равными, то оба распределителя имеют другое состояние. Распределитель x может не освободить память другого распределителя y, имеющего другое состояние, и поэтому контейнер с распределителем x не может просто украсть память из контейнера, который выделил свою память через y.

Если распределитель распространяется при назначении перемещения или если оба распределителя сравниваются с равными, то реализация, скорее всего, решит просто сделать b собственные a данные, поскольку он может быть уверен, что сможет правильно освободить хранилище.

1: std::allocator_traits<std::allocator<T>>::propagate_on_container_move_assignment и std::allocator_traits<std::allocator<T>>::is_always_equal оба являются typdefs для std::true_type (для любого неспециализированного std::allocator).

В режиме перемещения:

std::vector<T, A> a{/*...*/};
std::vector<T, A> b(std::move(a));

Конструктор перемещения контейнера, поддерживающего распределитель, будет перемещать-построить свой экземпляр распределителя из экземпляра распределителя контейнера, из которого текущее выражение перемещается. Таким образом, обеспечивается надлежащая способность к освобождению, и память может (и на самом деле) быть украдена, потому что конструкция перемещения (за исключением std::array) связана с постоянной сложностью.

Примечание. Итераторы по-прежнему не могут оставаться в силе даже для перемещения.

В swap:

Требование, чтобы итераторы двух векторов оставались действительными после свопинга (теперь просто указывая на соответствующий обменный контейнер), легко, потому что подкачка только определила поведение, если

  • std::allocator_traits<A>::propagate_on_container_swap::value == true ||
  • a.get_allocator() == b.get_allocator()

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