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

Question

Мне нужно пройти набор и удалить элементы, которые соответствуют предопределенным критериям.

Это тестовый код, который я написал:

#include <set> 
#include <algorithm> 

void printElement(int value) { 
    std::cout << value << " "; 
} 

int main() { 
    int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
    std::set<int> numbers(initNum, initNum + 10); 
    // print '0 1 2 3 4 5 6 7 8 9' 
    std::for_each(numbers.begin(), numbers.end(), printElement); 

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

    // iterate through the set and erase all even numbers 
    for (; it != numbers.end(); ++it) { 
     int n = *it; 
     if (n % 2 == 0) { 
      // wouldn't invalidate the iterator? 
      numbers.erase(it); 
     } 
    } 

    // print '1 3 5 7 9' 
    std::for_each(numbers.begin(), numbers.end(), printElement); 

    return 0; 
} 

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

Мой вопрос: Является ли это определенным поведением для std-наборов или эта реализация специфична? Кстати, я использую gcc 4.3.3 на ubuntu 10.04 (32-разрядная версия).

Спасибо!

Предлагаемое решение:

Является ли это правильный способ для перебора и удаления элементов из набора?

while(it != numbers.end()) { 
    int n = *it; 
    if (n % 2 == 0) { 
     // post-increment operator returns a copy, then increment 
     numbers.erase(it++); 
    } else { 
     // pre-increment operator increments, then return 
     ++it; 
    } 
} 

Edit: предпочитаемые РЕШЕНИЕ

Я пришел в решение, которое кажется более элегантно ко мне, даже если он делает то же самое.

while(it != numbers.end()) { 
    // copy the current iterator then increment it 
    std::set<int>::iterator current = it++; 
    int n = *current; 
    if (n % 2 == 0) { 
     // don't invalidate iterator it, because it is already 
     // pointing to the next element 
     numbers.erase(current); 
    } 
} 

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

Answer 1

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

Стандартный 23.1.2.8:

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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;                
    }                  
} 

Answer 5

Просто, чтобы предупредить, что в случае DEQUE контейнера, все решения, которые проверяют на DEQUE итератора равенства numbers.end(), скорее всего, не в состоянии на ССЗ 4.8.4. А именно, удаление элемента из дека как правило, аннулирует указатель на 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 преобразование является правильным в данном конкретном случае, конец указателя был признан недействительным на этом пути. С дека другого размера ошибка более очевидна:

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; 
     } 
    } 
    } 
}