Удаление элементов из STL, установленных во время итерации

Ответ 1

Это зависит от реализации:

Стандарт 23.1.2.8:

Элементы вставки не должны влиять на действительность итераторов и ссылки на контейнер, а элементы стирания должны делать недействительными только итераторы и ссылки на стертые элементы.

Может быть, вы могли бы попробовать это - это стандартное соответствие:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        numbers.erase(it++);
    }
    else {
        ++it;
    }
}

Обратите внимание, что it++ является постфиксом, поэтому он передает старую позицию для удаления, но сначала переходит к новой позиции из-за оператора.

2015.10.27 обновление: С++ 11 устранил дефект. iterator erase (const_iterator position); вернуть итератор для элемента, который следует за последним удаленным элементом (или set::end, если последний элемент был удален). Итак, стиль С++ 11:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}

Ответ 2

Если вы запустите свою программу через valgrind, вы увидите кучу ошибок чтения. Другими словами, да, итераторы недействительны, но вам повезло в вашем примере (или действительно не повезло, так как вы не видите негативных последствий поведения undefined). Одним из решений этого является создание временного итератора, увеличение темпа, удаление целевого итератора, а затем установка цели на временную. Например, перепишите свой цикл следующим образом:

std::set<int>::iterator it = numbers.begin();                               
std::set<int>::iterator tmp;                                                

// iterate through the set and erase all even numbers                       
for ( ; it != numbers.end(); )                                              
{                                                                           
    int n = *it;                                                            
    if (n % 2 == 0)                                                         
    {                                                                       
        tmp = it;                                                           
        ++tmp;                                                              
        numbers.erase(it);                                                  
        it = tmp;                                                           
    }                                                                       
    else                                                                    
    {                                                                       
        ++it;                                                               
    }                                                                       
} 

Ответ 3

Вы неправильно понимаете, что означает "undefined поведение". Поведение Undefined не означает "если вы это сделаете, ваша программа выйдет из строя или приведет к неожиданным результатам". Это означает, что "если вы это сделаете, ваша программа может сработать или произвести неожиданные результаты" или сделать что-нибудь еще, в зависимости от вашего компилятора, вашей операционной системы, фазы луны и т.д.

Если что-то выполняется без сбоев и ведет себя так, как вы ожидаете, это не значит, что это не поведение Undefined. Все это доказывает, что его поведение было таким же, как и для этого конкретного запуска, после компиляции с этим конкретным компилятором в этой конкретной операционной системе.

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

Ответ 4

Просто, чтобы предупредить, что в случае контейнера deque все решения, которые проверяют равенство итератора deque на number.end(), скорее всего, не сработают на gcc 4.8.4. А именно, стирание элемента deque обычно приводит к недействительности указателя на numbers.end():

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  //numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Вывод:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()

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

int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Вывод:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)

Вот один из способов исправить это:

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;
  bool done_iterating = false;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  if (!numbers.empty()) {
    deque<int>::iterator it = numbers.begin();
    while (!done_iterating) {
      if (it + 1 == numbers.end()) {
    done_iterating = true;
      } 
      if (*it % 2 == 0) {
    cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      }
      else {
    cout << "Skipping element: " << *it << "\n";
    ++it;
      }
    }
  }
}

Ответ 5

Это поведение специфично для реализации. Чтобы гарантировать правильность итератора, вы должны использовать "it = numbers.erase(it)"; если вам нужно удалить элемент и просто выполнить итератор в другом случае.

Ответ 6

Я думаю, что использование метода STL ' remove_if ' из может помочь предотвратить некоторые странные проблемы при попытке удалить объект, обернутый итератором.

Это решение может быть менее эффективным.

Допустим, у нас есть какой-то контейнер, например, vector или список с именем m_bullets:

Bullet::Ptr is a shared_pr<Bullet>

' it ' - это итератор, который возвращает ' remove_if ', третий аргумент - это лямбда-функция, которая выполняется для каждого элемента контейнера. Поскольку контейнер содержит Bullet::Ptr, лямбда-функция должна получить этот тип (или ссылку на этот тип) в качестве аргумента.

 auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
    // dead bullets need to be removed from the container
    if (!bullet->isAlive()) {
        // lambda function returns true, thus this element is 'removed'
        return true;
    }
    else{
        // in the other case, that the bullet is still alive and we can do
        // stuff with it, like rendering and what not.
        bullet->render(); // while checking, we do render work at the same time
        // then we could either do another check or directly say that we don't
        // want the bullet to be removed.
        return false;
    }
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still 
// exist and needs to be removed if you do not want to manually fill it later 
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());

" remove_if " удаляет контейнер, в котором лямбда-функция вернула истину, и перемещает это содержимое в начало контейнера. " it " указывает на неопределенный объект, который можно считать мусором. Объекты от 'it' до m_bullets.end() могут быть удалены, так как они занимают память, но содержат мусор, поэтому в этом диапазоне вызывается метод 'erase'.

Ответ 7

С++ 20 будет иметь "равномерное стирание контейнера", и вы сможете написать:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

И это будет работать для vector, set, deque и т.д. См. CppReference для получения дополнительной информации.

Ответ 8

Я столкнулся с той же самой старой проблемой и нашел ниже код более понятным, который в некотором смысле соответствует вышеуказанным решениям.

std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
    // Use your member
    std::cout<<(*beginIt)<<std::endl;

    // delete the object
    delete (*beginIt);

    // erase item from vector
    listOfInts.erase(beginIt );

    // re-calculate the begin
    beginIt = listOfInts.begin();
}