Поведение перекрывающегося vector::insert

Где стандарт C++ объявляет, что пара итераторов, переданных в std::vector::insert, не должна перекрывать исходную последовательность?

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

std::vector<int> v(10);
std::vector<int>::iterator first = v.begin() + 5;
std::vector<int>::iterator last = v.begin() + 8;
v.insert(v.begin() + 2, first, last);

Однако мне не удалось найти в стандарте ничего, что запрещало бы диапазоны [first, last) и [v.begin(), v.end()) пересекаться.


person avakar    schedule 25.08.2009    source источник


Ответы (2)


23.1.1/4 Требования к последовательности:

выражение: a.insert(p,i,j)

тип возвращаемого значения: void

предварительное условие: i,j не являются итераторами в a. вставляет копии элементов в [i,j) перед p.

Таким образом, i и j не могут быть итераторами в вашем векторе.

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

person Richard Corden    schedule 25.08.2009
comment
Большое спасибо, это именно то, что я искал. :-) - person avakar; 25.08.2009
comment
Почти уверен, что вы имеете в виду i и j, а не p; p должен быть итератором в векторе. - person Rob Kennedy; 25.08.2009

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

person JaredPar    schedule 25.08.2009
comment
Вы хотите сказать, что стандарт прямо не указывает это требование? - person avakar; 25.08.2009
comment
Я быстро проверил это, и да, это не говорит об этом явно. - person AraK; 25.08.2009
comment
АраК, при всем уважении, как можно было так быстро проверить? - person avakar; 25.08.2009
comment
@avakar Я только что проверил модификаторы векторов 23.2.4.3, и по вашему вопросу ничего нет. Извините, если я неправильно понял вопрос :) - person AraK; 25.08.2009
comment
Я имею в виду, что я не нашел слова «перекрытие» ни в одном из соответствующих мест, но его можно сформулировать по-разному. - person avakar; 25.08.2009
comment
AraK, я думаю, вы все правильно поняли, просто недостаточно заглянуть в 23.2.4.3 (для протокола, я тоже проверял, прежде чем спрашивать). Тем не менее, я ценю ваш комментарий, извините, если я был нервным. :-) - person avakar; 25.08.2009
comment
Если бы это было разрешено, то стандарт наверняка определил бы его таким образом, чтобы он не приводил к вектору бесконечного размера. Например, потребовать, чтобы он вставлял значения этого диапазона итераторов такими, какими они были во время вызова, независимо от любых изменений, внесенных в диапазон во время вызова. - person Rob Kennedy; 25.08.2009