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

Question

std::vector<int> ints;

// ... fill ints with random values

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

Этот код не работает, потому что когда вызывается pop_back(), it становится недействительным. Но я не вижу никаких документов, говорящих о признании недействительными итераторов в std::vector::pop_back().

У вас есть ссылки по этому поводу?

Answer 1

Вот ваш ответ, прямо из Священного Стандарта:

23.2.4.2 Вектор удовлетворяет всем требованиям контейнера и обратимого контейнера (приведенным в двух таблицах в 23.1) и последовательности, включая большинство необязательных требований последовательности (23.1.1).

23.1.1.12 Таблица 68 expressiona.pop_back () возвращение typevoid операционная семантика a.erase (- a.end ()) контейнерный вектор, список, deque

Обратите внимание, что a.pop_back эквивалентен a.erase (- a.end ()). Глядя на специфику вектора при стирании:

23.2.4.3.3 - стирание итератора (позиция итератора) - эффекты - Делает недействительными все итераторы и ссылки после точки стирания

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

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

Answer 2

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

Вставка или удаление элементов делает недействительными ссылки, указатели и итераторы, которые ссылаются на следующее элемент. Если вставка вызывает перераспределение, это делает недействительным все ссылки, итераторы и указатели.

Answer 3

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

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

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

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

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

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

23.2.6.4 (относительно вектора 4.erase ()):

Эффекты: делает недействительными итераторы и ссылки в или после точки удаления.

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

Answer 4

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

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

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

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

Answer 5

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

Вставка или удаление элементов делает недействительными ссылки, указатели и итераторы, которые ссылаются на следующее элемент. Если вставка вызывает перераспределение, это делает недействительным все ссылки, итераторы и указатели.

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

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

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

Answer 6

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

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

Answer 7

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

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 (как и мой первый алгоритм) стабилен, поэтому, возможно, это не самый эффективный способ сделать это, но он лаконичен.

Answer 8

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

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

Answer 9

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

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

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

Answer 10

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