Инвалидация итераторов std::vector: подробное объяснение

Концепция аннулирования итераторов в std::vector часто обсуждалась. Чтобы уточнить, стирание векторных элементов с помощью std::vector::erase делает недействительными итераторы, расположенные строго после стертого элемента.

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

Рассмотрите следующий пример, который иллюстрирует удаление нечетных целых чисел из вектора:

typedef std::vector vectype;
vectype vec;

for (int i = 0; i 
Хотя на практике этот код выполняется без ошибок, его достоверность остается спорной.
Ответ кроется в поведении метода Erase: он действительно делает недействительными все итераторы на итераторе или после него( s) передано на стирание. Однако он также возвращает новый итератор сразу после стертых элементов или до конца, если такой элемент не существует. Этот итератор можно использовать для возобновления итерации.
Важно отметить, что описанный выше метод удаления нечетных целых чисел неэффективен (O(n2)) поскольку каждое стирание требует сдвига всех последующие элементы. Идиома стирания-удаления предлагает гораздо более эффективное решение (O(n)):
bool is_odd(int x) { return (x % 2) == 1; }
vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end());