Делает ли std :: vector :: insert () недействительными итераторы, если в векторе достаточно места (созданного с помощью резерва)?
Ответ Как самостоятельно скопировать вектор? меня немного смутило недействительность итератора. В некоторых литературных источниках говорится, что «если вы используете 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);
Эта цитата из «Справочника по стандартной библиотеке C ++» Джозуттиса:
Вставка или удаление элементов
делает недействительными ссылки, указатели и
итераторы, которые ссылаются на следующее
элемент. Если вставка вызывает
перераспределение, это делает недействительным все
ссылки, итераторы и указатели.
предполагает, что мой код является безопасным и определенным поведением. Есть ли в стандарте отрывок, гарантирующий это?
Решение
Последний итератор всегда немного особенный. Я был бы осторожен. Стандарт гласит следующее (23.3.6.5):
Если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются действительными.
Ключ здесь «до точки вставки». Так как ваш оригинал it не до точки вставки (так как является точка вставки), я бы не рассчитывал, что она останется в силе.
Другие решения
Хотя верно, что вставки в вектор не будут вызывать перераспределение, пока емкость не будет превышена, и не будут делать недействительными итераторы для элементов до точка вставки (что, возможно, имеет место end()как указано @KerrekSB), в таблице 100 стандарта C ++ 11 (пункт 23.2.3) указано следующее предварительное условие для a.insert(p,i,j) функция для контейнеров последовательности:
[…] pre: i и j не являются итераторами в a. […]
В вашем случае, они явно таковы, что заставляет меня думать, что программа имеет неопределенное поведение.
Итераторы не должны быть признаны недействительными в середине функции. Идея, что память может быть переселены не выдерживает, потому что вы не можете использовать realloc на объектах с нетривиальными конструкторами. Даже если бы строительство не было проблемой, ему все равно пришлось бы дважды копировать исходную последовательность в худшем случае, сводя на нет любые преимущества в среднем случае.
Суть в том, что не имеет смысла реализовывать это таким образом; alloc, copy, free почти наверняка сделано, независимо от того, что говорит стандарт.
Это безопасно, потому что v.begin() а также v.end() всегда актуальны.
v.insert(v.end(), v.begin(), v.end());
v.insert(v.end(), v.begin(), v.end());
Это не.
vector<foo>::iterator i = v.begin();
vector<foo>::iterator j = v.end();
v.insert(v.end(), i, j);
v.insert(v.end(), i, j);
Тем не менее, самостоятельная вставка может быть вялым. Попробуйте следующее в GCC. Самостоятельная вставка дает неверный результат только если достаточно памяти доступно (не уверен, что это ошибка).
int main()
{
int position = 1, first = 2, last = 3;
// enforce error condition.
assert(position < first);
int size = 8;
// sanity check.
assert(first < last && last <= size);
std::vector<int> right, wrong;
// force resize during insertion.
right.reserve(size);
// avoid resize during insertion.
wrong.reserve(size + (last - first));
for ( int i = 0; i < size; i++ )
{
right.push_back(i);
wrong.push_back(i);
}
std::vector<int>::iterator i;
i = right.begin();
right.insert(i + position, i + first, i + last);
i = wrong.begin();
wrong.insert(i + position, i + first, i + last);
assert(right == wrong);
return 0;
}
Замечания: Приведенное выше мнение относится к vector в частности, не контейнеры в целом. Кроме того, предположение о том, что приведенное выше поведение может быть ошибкой, не имеет ничего общего со стандартом, а скорее с простотой реализации надежной самостоятельной вставки для vector,