Удаление элементов из std :: set во время итерации
Мне нужно пройти через набор и удалить элементы, которые соответствуют предопределенным критериям.
Это тестовый код, который я написал:
#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;
}
Сначала я подумал, что стирание элемента из набора во время его итерации приведет к аннулированию итератора, и приращение в цикле for будет иметь неопределенное поведение. Хотя я выполнил этот тестовый код, и все прошло хорошо, и я не могу объяснить, почему.
Мой вопрос: Является ли это определенным поведением для стандартных наборов или это конкретная реализация? Кстати, я использую 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;
}
}
Редактировать: ПРЕДПОЧТИТЕЛЬНОЕ РЕШЕНИЕ
Я нашел решение, которое кажется мне более элегантным, хотя оно и делает то же самое.
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);
}
}
Если в то время как есть несколько условий тестирования, каждое из них должно увеличивать итератор. Мне больше нравится этот код, потому что итератор увеличивается только в одном месте , делая код менее подверженным ошибкам и более читаемым.
4 ответа
Это зависит от реализации:
Стандарт 23.1.2.8:
Члены insert не должны влиять на действительность итераторов и ссылок на контейнер, а члены erase должны аннулировать только итераторы и ссылки на стертые элементы.
Возможно, вы могли бы попробовать это - это соответствует стандарту:
for (auto it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
numbers.erase(it++);
}
else {
++it;
}
}
Обратите внимание, что it++ является постфиксным, поэтому он передает старую позицию для стирания, но сначала перескакивает на более новую из-за оператора.
2015.10.27 update:
В C++11 дефект устранен. iterator erase (const_iterator position); возвращает итератор к элементу, который следует за последним удаленным элементом (или set::end, если последний элемент был удален). Так что стиль C++11 таков:
for (auto it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
it = numbers.erase(it);
}
else {
++it;
}
}
Это поведение специфично для конкретной реализации. Для гарантии корректности итератора следует использовать оператор "it = numbers.erase(it);", если вам нужно удалить элемент, и просто увеличить итератор в другом случае.
Вы неправильно понимаете, что означает "неопределенное поведение". Неопределенное поведение не означает, что «если вы сделаете это, ваша программа приведет к сбою или выдаст неожиданные результаты». Это означает, что «если вы сделаете это, ваша программа может дать сбой или дать неожиданные результаты» или сделать что-нибудь еще, в зависимости от вашего компилятора, вашей операционной системы, фазы луны и т. Д.
Если что-то выполняется без сбоев и ведет себя так, как вы ожидаете, то есть не доказательство того, что это не неопределенное поведение. Все, что он доказывает, - это то, что его поведение соответствовало наблюдаемому для этого конкретного запуска после компиляции с этим конкретным компилятором в этой конкретной операционной системе.
Удаление элемента из набора делает недействительным итератор для стертого элемента. Использование недействительного итератора - неопределенное поведение. Так уж получилось, что наблюдаемое поведение было тем, что вы планировали в данном конкретном случае; это не значит, что код правильный.
Если вы запустите свою программу через valgrind, вы увидите множество ошибок чтения. Другими словами, да, итераторы становятся недействительными, но в вашем примере вам повезло (или действительно не повезло, поскольку вы не видите отрицательных эффектов неопределенного поведения). Одним из решений этого является создание временного итератора, увеличение значения temp, удаление целевого итератора, а затем установка целевого значения temp. Например, перепишите свой цикл следующим образом:
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;
}
}