Как узнать, что `std::vector::begin()` стал недействительным?

Строго ли перераспределение определено в стандарте C++?

Определено, что std::vector разрешено перераспределять, но не указано, когда. Вы просто можете вызвать reserve или resize, прежде чем добавлять новые данные. Часто алгоритм заключается в дублировании выделенной памяти, если новые данные требуют перераспределения, то есть 2,4,8,16...

Вы просто можете взглянуть на std::vector в разделе Iterator invalidation, чтобы понять, когда итераторы будут признаны недействительными.

Почему std::vector::begin() недействителен, если векотр вставлен в третий раз.

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

Строго ли перераспределение определено в стандарте C++?

Нет. Это деталь реализации. Хотя, как указано в стандарте C++ std::vector, ясно, что перераспределение должно произойти (и, конечно, спецификация была написана с учетом этого). А требования к временной сложности вставки элементов таковы, что реализация не может перераспределять их при каждой отдельной вставке. Следовательно, каждая вставка потенциально делает итераторы недействительными.

std::vector::begin() следует вызывать каждый раз при вызове метода Insert() в демонстрационном коде.

Нет. it используется в коде несколько раз. Всегда, когда элемент вставляется, итератор it обновляется допустимым итератором, прежде чем он будет использован снова.

Стандарт C++ дает библиотеке std свободу действий в том случае, когда она делает векторы недействительными.

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

Большинство языков, кроме C++, имеют одну реализацию. Итак, стандарт этого языка описывает, что делает реализация. В стране C++ этого не происходит, поэтому все становится более абстрактным.

Сейчас я дам описание того, как на практике поступают разработчики C++ std. Для простоты он будет содержать несколько «лжи, рассказанной детям».

std::vector<T> управляет буфером памяти, часть которого содержит объекты типа T, а также количество объектов в этом буфере.

Когда вы выполняете операцию, результирующий вектор которой помещается в этот буфер, std::vector<T> просто использует этот буфер.

Так, например, данный вектор может иметь буфер на 7 Ts и использовать только 3. Если вы добавите элемент, он перетасует элементы и ничего не перераспределит.

Однако если вы добавили 5 элементов, они больше не поместятся в ваш буфер (так как 3+5=8, что больше 7). В этот момент std::vector<T> запускает перераспределение.

Когда происходит перераспределение — когда буфер заменяется на больший — все итераторы становятся недействительными.

Если вы увеличите .reserve() до большего размера, реализации std::vector имеют тенденцию увеличивать вектор именно до того размера, который вы запрашиваете. Но если вы выполняете .push_back или .insert или подобные операции, реализации std::vector должны выполнять так называемую «амортизированную постоянную стоимость». По сути, это означает, что они должны расти в геометрической прогрессии.

Если вы начнете с вектора с буфером, в котором есть место для 1 элемента, и продолжите отталкиваться, буфер не будет расти, как «1, 2, 3, 4, 5, 6, ...». Вместо этого он растет как «1, 2, 4, 7, 11, 17, 26, ...» или «1, 2, 4, 8, 16, 32, ...». Некоторая функция, которая асимптотически ведет себя как «k^n».

Двумя типичными темпами роста являются «вдвое больше старого размера буфера» и «в 1,5 раза больше старого размера буфера»; разные реализации выбирают разные темпы роста, и стандарт C++ достаточно гибок, чтобы позволить и то, и другое. (есть преимущества более высоких или медленных темпов роста).

Из-за такой гибкости в выборе скорости роста реализации стандарт не говорит, когда итераторы становятся недействительными для данной программы. Там просто сказано, при каких условиях они могут быть признаны недействительными.

Итератор std::vector может быть признан недействительным при каждом изменении .capacity(). .reserve() гарантирует минимум .capacity(). .size() всегда меньше или равно .capacity(). Методы .insert() и .push_* могут расти .size().

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

Иногда хочется пофантазировать. Если вы хотите проявить фантазию, вам нужно во время выполнения получить .capacity(), когда вы получаете свои итераторы, и гарантировать, что ваш набор операций по добавлению элементов никогда не пройдет проверку правильности. Если это так, вы можете гарантировать, что ваши итераторы не будут признаны недействительными при добавлении элементов.

(Другой распространенный способ признания векторных итераторов недействительными — это замена, перемещение-назначение и перемещение-конструкция из или двух векторов. В случае перемещения-конструкции и замены итераторы определены для миграции в другой контейнер; в случае move-assignment, такая гарантия не предоставляется, поскольку она оставляет на усмотрение реализации принятие решения во время выполнения, должен ли вектор перемещать элементы или перемещать буферы)