Делает ли перемещение вектора недействительными итераторы?

Если у меня есть итератор в вектор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 не делает недействительными итераторы.

 John Dibling13 июн. 2012 г., 21:21
Pedantic - вы не двигались, вы назначали движение.
 David Brown13 июн. 2012 г., 21:21
@Cris Я надеюсь, чтоa_iter теперь ссылается на элемент вb послеa перемещен
 John Dibling13 июн. 2012 г., 21:50
@Luc: итераторы могут быть недействительными, если сам класс итератора поддерживает указатели обратно на векторный класс. Просто плевок.
 Luc Touraille13 июн. 2012 г., 21:47
Я не могу придумать причину, по которой итераторы будут признаны недействительными, но я не могу найти никаких цитат в стандарте, чтобы поддержать это ... Поскольку валидность итераторов после перестановки четко определена, кажется разумным думать, что то же самое можно сказать при движении (даже больше, если мы думаем о том, какvectors реализованы).
 Benjamin Lindley13 июн. 2012 г., 21:41
@ Томаш: Если ответ таковdoes лишать законной силы итераторы, а затем неопределенное поведение разыменовывать их, так как бы вы это проверили?

Ответы на вопрос(4)

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

 13 июн. 2012 г., 22:05
Разве это не наоборот? Можете ли вы предположить, что итераторы остаются действительными, если иное не указано в стандарте? Вот что я понимаю из этой цитаты:Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container. [Container.requirements.general]
 13 июн. 2012 г., 22:26
@LucTouraille: я не знаю. Мне разрешено постигать только столько стандартов в месяц, и я превысил мой лимит.
 13 июн. 2012 г., 21:55
Согласившись с Джоном Диблингом, ближайшая ссылка заключается в том, что итераторы не становятся недействительными, если два контейнера поменялись местами, что, по-видимому, указывает на то, что он должен быть действительным, но я не нашел такой гарантии. Удивительно, насколько тихий стандарт в отношении перемещения контейнеров.
 David Brown13 июн. 2012 г., 22:20
Wouldn & APOS; тvector::swap постоянное время, а также не делает недействительными итераторыvector::iterator содержать указатель на оригинальный контейнер?
 13 июн. 2012 г., 21:50
+1: я бы согласился с этой оценкой, и за то, что она того стоит, я искал такую ссылку в течение последних 30 минут, и я ничего не могу найти. :)

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

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

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

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

Возможность назначения элементов перемещению подтверждается описанием: «Все существующие элементы элемента либо назначены, либо уничтожены». «Разрушенный» часть будет соответствовать уничтожению существующего содержимого и «краже» указатель из источника - но перемещение, назначенное для & quot; будет указывать на перемещение отдельных элементов из источника в пункт назначения.

 28 дек. 2012 г., 17:17
Оно не просто линейно по количеству элементов, подлежащих уничтожению. Как указано в [container.requirements.general] / 7 конструкция перемещения всегда перемещает распределитель, назначение перемещения только перемещает распределитель, еслиpropagate_on_container_move_assignment истина, если это не так, и распределители не равны, то существующее хранилище не может быть перемещено, и, таким образом, существует возможное перераспределение, и каждый элемент перемещается индивидуально.
 13 июн. 2012 г., 21:51
@Dave: Соответствующая реализация должна работать не хуже, чем любые гарантии производительности, предписанные в Стандарте.
 13 июн. 2012 г., 21:59
Почему бы им не требовать постоянной сложности для назначения перемещения std :: vector ?! (и все остальные контейнеры ...)
 13 июн. 2012 г., 21:59
Я на самом деле думаю, что он линейный с точки зрения размера назначаемого контейнера. Это то же самое, что деструктор, являющийся линейным, он должен уничтожить все существующие элементы, проблема, которой нет у конструктора перемещения, поскольку нет существующих элементов.
 13 июн. 2012 г., 21:49
Я вижу то же самое, что и вы, в таблице 96, но у меня шокированная конструкция хода и назначение перемещения имеют разные требования к сложности! Соответствующая реализацияhave чтобы соответствовать сложности в этой таблице, или это может быть лучше? (AKA: является ли std :: vector копирующим указатель на его данные в соответствии со стандартным назначением перемещения?)
Решение Вопроса

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

Там нет ссылки, которую я могу найти в стандарте, которыйspecifically states что итераторы, которые существовали доmove все еще действительныafter move.

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

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

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

Следовательно, в общем и целом, вы не можете предполагать, что ваши итераторы все еще хороши послеmove.

EDIT:

23.2.1 / 11 в проекте N3242 говорится, что:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

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

 13 июн. 2012 г., 22:04
+1 Но, может быть, вы можете разумно предположить, что ониare все еще хорошо после переезда - но просто знайте, что это может не сработать, если вы переключите компиляторы. Он работает в каждом только что протестированном компиляторе и, вероятно, всегда будет.
 13 июн. 2012 г., 22:08
Я обычно соглашался бы, но было бы трудно написать своп, который поддерживает действительные итераторы, и назначение перемещения, которое не делает. Автор библиотеки почти потребовал бы преднамеренных усилий, чтобы сделать итераторы недействительными. Кроме того, undefined - мой любимый тип поведения.
 07 июн. 2015 г., 03:25
ЭтоLWG 2321
 15 июн. 2012 г., 16:36
@ Свен Марнах: я никогда не знаю, Погода использовать ли или :)
 13 июн. 2012 г., 22:04
@Dave: опора на неопределенное поведение - очень скользкий путь и, педантично, технически недопустимый. Лучше всего просто не делать этого.

tl;dr : Yes, moving a std::vector<T, A> possibly invalidates the iterators

The common case (with std::allocator in place) is that invalidation does not happen but there is no guarantee and switching compilers or even the next compiler update might make your code behave incorrect if you rely on the fact the your implementation currently does not invalidate the iterators.

On move assignment:

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

В каждой реализации, которую я видел, перемещение-присваиваниеstd::vector<T, std::allocator<T>>1 фактически не сделает недействительными итераторы или указатели. Однако возникает проблема, когда речь заходит об использовании этого, какthe standard just cannot guarantee that iterators remain valid for any move-assignment of a std::vector instance in general, because the container is allocator aware.

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

Позволять:

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 && (possibly as of c++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 оба являются typedefs дляstd::true_type (для любого неспециализированногоstd::allocator).

On move construction:

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

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

Note: There is still no guarantee for iterators to remain valid even for move construction.

On swap:

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

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

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

Ваш ответ на вопрос