Действительно ли pop_back () аннулирует * все * итераторы в std :: vector?

Итераторы становятся недействительными только при перераспределении памяти. Google - ваш друг: сноску 5.

Ваш код не работает по другим причинам.

Ознакомьтесь с информацией здесь (cplusplus.com):

Delete last element

Removes the last element in the vector, effectively reducing the vector size by one and invalidating all iterators and references to it.

Ошибка в том, что когда «он» указывает на последний элемент вектора и если этот элемент меньше 10, этот последний элемент удаляется. И теперь «it» указывает на ints.end (), следующее «it ++» перемещает указатель на ints.end () + 1, так что теперь «it» убегает от ints.end (), и вы получаете бесконечный цикл, сканирующий все ваши объем памяти :).

Вызов pop_back() удаляет последний элемент в векторе, и поэтому итератор этого элемента становится недействительным. Вызов pop_back() делает нет недействительными итераторы для элементов перед последним элементом, это сделает только перераспределение. Из «Справочника по стандартной библиотеке C++» Джосуттиса:

Inserting or removing elements invalidates references, pointers, and iterators that refer to the following element. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.

Вот цитата из документации SGI STL (http://www.sgi.com/tech/stl/Vector.html):

[5] Итераторы вектора становятся недействительными при перераспределении памяти. Кроме того, вставка или удаление элемента в середине вектора делает недействительными все итераторы, которые указывают на элементы, следующие за точкой вставки или удаления. Отсюда следует, что вы можете предотвратить аннулирование итераторов вектора, если вы используете функцию Reserve () для предварительного выделения такого объема памяти, который будет когда-либо использоваться вектором, и если все вставки и удаления находятся в конце вектора.

Я думаю, из этого следует, что pop_back аннулирует только итератор, указывающий на последний элемент, и итератор end (). Нам действительно нужно увидеть данные, для которых код не работает, а также то, как он не может решить, что происходит. Насколько я могу судить, код должен работать - обычная проблема в таком коде заключается в том, что удаление элемента и ++ на итераторе происходит в одной итерации, как указывает @mikhaild. Однако в этом коде это не так: этого ++ не происходит при вызове pop_back.

Что-то плохое может произойти, если он указывает на последний элемент, а последний элемент меньше 10. Сейчас мы сравниваем признан недействительным it и end (). Он может работать, но никаких гарантий быть не может.

«Официальная спецификация» - это стандарт C++. Если у вас нет доступа к копии C++ 03, вы можете получить последний черновик C++ 0x на веб-сайте Комитета: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf

В разделе «Операционная семантика» требований к контейнеру указано, что pop_back () эквивалентен {iterator i = end (); --я; стереть (i); }. раздел [vector.modifiers] для стирания говорит: «Эффекты: делает недействительными итераторы и ссылки в точке стирания или после нее».

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

Вот ваш ответ прямо из The Holy Standard:

23.2.4.2 A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.1) and of a sequence, including most of the optional sequence requirements (23.1.1).

23.1.1.12 Table 68 expressiona.pop_back() return typevoid operational semanticsa.erase(--a.end()) containervector, list, deque

Обратите внимание, что a.pop_back эквивалентно a.erase (- a.end ()). Рассмотрим особенности вектора при стирании:

23.2.4.3.3 - iterator erase(iterator position) - effects - Invalidates all the iterators and references after the point of the erase

Следовательно, как только вы вызываете pop_back, любые итераторы для предыдущего последнего элемента (который теперь больше не существует) становятся недействительными.

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

(Я использую схему нумерации, используемую в рабочем проекте C++ 0x, можно получить здесь

Таблица 94 на странице 732 говорит, что pop_back (если он существует в контейнере последовательности) имеет следующий эффект:

{ iterator tmp = a.end(); 
--tmp; 
a.erase(tmp); } 

23.1.1, пункт 12 гласит, что:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

Оба обращения к end () в качестве префикса - не имеют такого эффекта, однако erase ():

23.2.6.4 (относительно vector.erase () пункт 4):

Effects: Invalidates iterators and references at or after the point of the erase.

Итак, в заключение: pop_back () сделает недействительным только итератор для последнего элемента, в соответствии со стандартом.

pop_back () аннулирует Это, только если Это указывал на последний элемент в векторе. Таким образом, ваш код будет терпеть неудачу всякий раз, когда последнее int в векторе меньше 10, как показано ниже:

* it = ints.back (); // Устанавливаем * его на уже имеющееся значение
ints.pop_back (); // Аннулируем итератор
Продолжить; // Цикл и доступ к недопустимому итератору

pop_back() делает недействительными только итераторы, указывающие на последний элемент. Из справочника стандартной библиотеки C++:

Inserting or removing elements invalidates references, pointers, and iterators that refer to the following element. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.

Итак, чтобы ответить на ваш вопрос, нет, это не делает недействительными итераторы все.

Однако в вашем примере кода он может сделать it недействительным, если он указывает на последний элемент и значение меньше 10. В этом случае STL отладки Visual Studio пометит итератор как недействительный и дополнительно проверит, не равен ли он end ( ) покажет утверждение.

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

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

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if (*it < 10)
        it = ints.erase( it );
    else
        ++it;
}

std::remove_if также может быть альтернативным решением.

struct LessThanTen { bool operator()( int n ) { return n < 10; } };

ints.erase( std::remove_if ( ints.begin(), ints.end(), LessThanTen() ), ints.end() );

std::remove_if (как и мой первый алгоритм) стабилен, поэтому, возможно, это не самый эффективный способ сделать это, но он краток.