Подтвердить что ты не робот

Гарантии переупорядочения вектора

Скажем, у меня есть этот код:

#include <iostream>
#include <vector>

int main() 
{
    std::vector<int> vec {10, 15, 20};
    auto itr = vec.begin();
    vec.erase(itr);
    for(const auto& element : vec)
    {
        std::cout << element << " ";
    }
    return 0;
}

Это дает мне 15 20, как и ожидалось. Теперь cppreference говорит this о erase():

Недействительные итераторы и ссылки на или после точки erase, включая end() iterator

Достаточно справедливо, но единственная гарантия, которую дает стандарт vector::erase()?

Является ли вектор разрешенным для его упорядочивания после стираемого итератора?

Например, гарантируются ли эти условия после стирания, что означало бы все элементы после того, как итератор erase() сдвинулся 1 влево:

vec[0] == 15
vec[1] == 20

Или реализациям разрешено перемещать значения по мере их соответствия, и, таким образом, создавать сценарии, где vec[0] == 20 и т.д.

Мне нужна цитата из соответствующей части стандарта.

4b9b3361

Ответ 1

Пусть начинается с начала:

23.2.3 Контейнеры последовательности

Контейнер последовательности организует конечный набор объектов, все одного типа, в строго линейную компоновку. Библиотека предоставляет четыре основных типа контейнеров последовательностей: вектор, forward_list, list и deque.

Акцент на "строго линейное расположение". Это недвусмысленно.

За этим определением следует таблица, называемая "требования контейнера последовательности", которая описывает erase() следующим образом:

a.erase(q) [ ... ]
Effects:  Erases the element pointed to by q

Совмещенный, это не оставляет места для интерпретации. Элементы в векторе всегда находятся в "строгом линейном расположении", поэтому, когда один из них erase() d, существует только один возможный результат.

Ответ 2

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

Практически, очевидно, это не будет сделано. Это было бы смешно.

В законном порядке вы, вероятно, можете взять предложение "Эффекты":

Стирает элемент, на который указывает q

как не имеющий других эффектов, если не указано иное (например, аннулирование итератора, что следует из эффекта стирания).

Ответ 3

Два утверждения, которые я нашел, что я думаю, гарантируют, что это будет:

С++ 11 Standard

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

Если вы не можете "изменить значения", вы не можете произвольно переупорядочить элементы (например, заменять конечное значение на стираемое).

23.2.3 12 Итератор, возвращаемый из a.erase(q), указывает на элемент, следующий за q до стирания элемента. Если такой элемент не существует, возвращается a.end().

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

Посредством объяснения.

В стандарте рассматривается абстрактная концепция, а не фактическая реализация, хотя ее утверждения влияют на реализацию.

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

3  5  7  4  2  9 (6 values)

Если мы уничтожим 3-й элемент, что это нам дает концептуально?

3  5  4  2  9 (5 values)

Это должно быть верно из-за первого вышеприведенного утверждения:

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

Если реализация переупорядочивает элементы, скажем, заменяя стертый элемент конечным элементом, это правило будет нарушено, потому что мы получим следующее:

3  5  9  4  2  

Концептуально результирующее значение справа от стираемого элемента изменилось с 4 на 9, нарушив правило.