Могу ли я удалить элементы из std::list, когда я итерирую по нему?

Question

Могу ли я удалить элементы из std::list, когда я итерирую по нему? Например так:

std::list<int> lst;
//....
for (std::list<int> itr = lst.begin(); itr != lst.end(); itr++)
{
    if (*itr > 10)
         lst.remove(*itr);
}

? И почему?

Answer 1

Правильный код следующий:

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); /*nothing*/)
{
    if (*itr > 10)
        itr = lst.erase(itr);
    else
        ++itr;
}

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

Еще лучшая идея будет использовать std::remove_if:

bool greater_than_10(int x)
{
    return x > 10;
}

lst.remove_if(greater_than_10);

Если ваш компилятор поддерживает лямбды, вы можете поместить его еще короче:

lst.remove_if([](int x){ return x > 10; });

(Я не тестировал этот код, так как мой компилятор не такой новый; к счастью, лямбда-функция украдена из ответа @John Dibling.)

---

На самом деле удаление из списка делает недействительными только итераторы, указывающие на удаляемый элемент. Однако помните, что другие контейнеры STL не имеют этого свойства.

---

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

Помните, что для других контейнеров STL (например, векторов) ограничение еще более строгое: удаление из контейнера делает недействительными не только итераторы, указывающие на удаленный элемент, но, возможно, и другие итераторы! Таким образом, удаление из этих контейнеров во время итерации по ним еще более проблематично.

Answer 2

Нет. Код примера делает недействительным itr, вызывая неопределенное поведение. Но это будет работать:

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); )
{
    if (*itr > 10)
        itr = lst.erase(itr);
    else
        ++itr;
}

Answer 3

Нет, ты не можешь.

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

#include <list>
#include <algorithm>


int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), std::bind2nd(std::greater<int>(), 10)), lst.end());
}

Другой, более общий способ сделать это - написать свой собственный функтор. Вот функтор is_a_match это возвращает true если проверяемое значение больше 10. Вы можете переопределить operator() возвращать true соответствовать тому, что в вашем случае означает "соответствовать":

#include <list>
#include <algorithm>
#include <functional>

struct is_a_match : public std::unary_function<int, bool>
{
    is_a_match(int val) : val_(val) {};
    bool operator()(int victim) const { return victim > val_; }
private:
    int val_;
};

int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), is_a_match(10) ));
}

Если у вас есть преимущество компилятора, совместимого с C++0x, вы также можете использовать лямбда-выражения, что позволяет во многих случаях избавиться от функтора и написать более выразительный код

#include <list>
#include <algorithm>

int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), [](int v) {return v > 10;}));
}

Answer 4

Я думаю, что вы можете, но вы должны переназначить итератор после удаления элемента, что можно сделать с помощью eraseметод вместо этого remove,

В противном случае это будет небезопасно и не должно быть сделано.

Answer 5

См. http://www.cppreference.com/wiki/iterator/start для описания итераторов.

Пара заметок:

• Вы должны использовать оператор предварительного увеличения (++itr) вместо оператора постинкремента (itr++)
• Недействительность зависит от точной реализации итератора и связанной с ним коллекции.