Делает ли std::vector::insert() недействительными итераторы, если в векторе достаточно места (созданного за счет резерва)?

Ответ на Как самостоятельно скопировать вектор? меня немного смутил об инвалидации итератора. В некоторой литературе говорится: «Если вы используете вставку, push_back и т. д., считайте все итераторы недействительными». Это ясно, это может привести к увеличению вектора, что сделает итераторы недействительными. Как насчет особого случая, когда я знаю, что места будет достаточно?

первая попытка:

myvec.reserve(myvec.size()*3);  //does this protect me from iterator invalidation?
vector<string>::iterator it = myvec.end();    
myvec.insert(myvec.end(), myvec.begin(), it);
myvec.insert(myvec.end(), myvec.begin(), it);

После нескольких отличных ответов вторая попытка:

auto size = myvec.size();
myvec.reserve(size*3);  //does this protect me from iterator invalidation?  
myvec.insert(myvec.end(), myvec.begin(), myvec.begin()+size);
myvec.insert(myvec.end(), myvec.begin(), myvec.begin()+size);

После более отличных ответов третья попытка:

auto size = myvec.size();
myvec.reserve(size*3);  //does this protect me from iterator invalidation?  
back_insert_iterator< vector<string> > back_it (myvec);
copy (myvec.begin(),myvec.begin()+size,back_it);
copy (myvec.begin(),myvec.begin()+size,back_it);

Эта цитата из "Справочника по стандартной библиотеке С++" Джосуттиса:

Вставка или удаление элементов делает недействительными ссылки, указатели и итераторы, которые относятся к следующему элементу. Если вставка вызывает перераспределение, она делает недействительными все ссылки, итераторы и указатели.

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


person odinthenerd    schedule 11.02.2013    source источник
comment
Просто для тех, кто хочет продолжить поиски: да, где-то есть проход, просто у меня его нет под рукой. Там сказано почти то же самое, что и в книге Джосутти.   -  person PlasmaHH    schedule 12.02.2013
comment
У меня нет стандартного под рукой, но следующий лучший вариант, cppreference.com указывает следующее относительно std::vector<T>::insert() : Вызывает перераспределение, если новый size() больше, чем старый capacity(). Если новый size() больше, чем capacity(), все итераторы и ссылки становятся недействительными. . В противном случае аннулируются только итераторы и ссылки после добавленного элемента. Я бы проконсультировался со стандартом, но, в отличие от других сайтов, cppreference поддерживается участниками, которые живут, дышат и умирают согласно стандарту.   -  person WhozCraig    schedule 12.02.2013


Ответы (2)


Итератор прошлого конца всегда немного особенный. Я был бы осторожен. Стандарт говорит об этом (23.3.6.5):

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

Ключ здесь «перед точкой вставки». Поскольку ваш исходный it не находится перед точкой вставки (поскольку он является точкой вставки), я бы не стал рассчитывать на то, что он останется действительным.

person Kerrek SB    schedule 11.02.2013
comment
ничего себе, вы просто поразили меня, так как это указывает на старый конец, который является теоретическим значением прошлого, тогда конец, конечно, может быть признан недействительным. +1 Я исправлю свой код, чтобы исключить эту ошибку. - person odinthenerd; 12.02.2013
comment
+1 спасибо, что посмотрели это. Мне очень нужно получить копию стандарта на моем рабочем компьютере. - person WhozCraig; 12.02.2013
comment
@WhozCraig: Просто черновик, но подходит для большинства целей: open-std.org/JTC1/SC22/WG21/docs/papers/2012/n3485.pdf - person Benjamin Lindley; 12.02.2013
comment
@PorkyBrain: однажды у меня была похожая ситуация :-) - person Kerrek SB; 12.02.2013

Хотя это правда, что вставки в вектор не вызовут перераспределения, пока не будет превышена емкость, и не сделают недействительными итераторы к элементам перед точкой вставки (что, возможно, имеет место в случае end() , как указал @KerrekSB), в таблице 100 стандарта С++ 11 (параграф 23.2.3) указано следующее предварительное условие для функции a.insert(p,i,j) для контейнеров последовательности:

[...] pre: i и j не являются итераторами в a. [...]

В вашем случае они явно есть, что заставляет меня думать, что программа имеет неопределенное поведение.

person Andy Prowl    schedule 11.02.2013
comment
это в значительной степени суть вопроса;) Говорит ли стандарт только об этом, потому что вставка может вызвать рост? Может быть, но с другой стороны, это не устоит перед языковым юристом... - person odinthenerd; 12.02.2013
comment
@PorkyBrain: не имеет значения, почему это указано в стандарте. Достаточно того факта, что он указывает это как предварительное условие: реализации разрешено делать что угодно, если вы его нарушите. - person Andy Prowl; 12.02.2013