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

Question

У меня есть код, который выглядит так:

for (std::list<item*>::iterator i=items.begin();i!=items.end();i++)
{
    bool isActive = (*i)->update();
    //if (!isActive) 
    //  items.remove(*i); 
    //else
       other_code_involving(*i);
}
items.remove_if(CheckItemNotActive);

Я бы хотел удалить неактивные элементы сразу после их обновления, чтобы избежать повторного просмотра списка. Но если я добавляю закомментированные строки, я получаю сообщение об ошибке i++: «Итератор списка не может быть увеличен». Я попробовал несколько альтернатив, которые не увеличивались в выражении for, но я не мог заставить что-либо работать.

Каков наилучший способ удаления элементов при ходьбе по стандартному списку:

Answer 1

Вы должны сначала увеличить итератор (с помощью i ++), а затем удалить предыдущий элемент (например, используя возвращаемое значение из i ++). Вы можете изменить код на цикл while следующим образом:

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive)
    {
        items.erase(i++);  // alternatively, i = items.erase(i);
    }
    else
    {
        other_code_involving(*i);
        ++i;
    }
}

Answer 2

Вы хотите сделать:

i= items.erase(i);

Это правильно обновит итератор, чтобы он указывал на местоположение после итератора, который вы удалили.

Answer 3

Вам нужно сделать комбинацию ответа Кристо и MSN:

// Note: Using the pre-increment operator is preferred for iterators because
//       there can be a performance gain.
//
// Note: As long as you are iterating from beginning to end, without inserting
//       along the way you can safely save end once; otherwise get it at the
//       top of each loop.

std::list< item * >::iterator iter = items.begin();
std::list< item * >::iterator end  = items.end();

while (iter != items.end())
{
    item * pItem = *iter;

    if (pItem->update() == true)
    {
        other_code_involving(pItem);
        ++iter;
    }
    else
    {
        // BTW, who is deleting pItem, a.k.a. (*iter)?
        iter = items.erase(iter);
    }
}

Конечно, самый эффективный и SuperCool & reg; Сообразительная вещь STL будет примерно такой:

// This implementation of update executes other_code_involving(Item *) if
// this instance needs updating.
//
// This method returns true if this still needs future updates.
//
bool Item::update(void)
{
    if (m_needsUpdates == true)
    {
        m_needsUpdates = other_code_involving(this);
    }

    return (m_needsUpdates);
}

// This call does everything the previous loop did!!! (Including the fact
// that it isn't deleting the items that are erased!)
items.remove_if(std::not1(std::mem_fun(&Item::update)));

Answer 4

Использовать алгоритм std :: remove_if.

Edit: Работа с коллекциями должна быть такой: 1. подготовить коллекцию. 2. процесс сбора.

Жизнь станет проще, если вы не будете смешивать эти шаги.

1. станд :: remove_if. или list :: remove_if (если вы знаете, что работаете со списком, а не с TCollection)
2. станд :: for_each

Answer 5

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

for(auto i = items.begin(); i != items.end();)
{
    if(bool isActive = (*i)->update())
    {
        other_code_involving(*i);
        ++i;

    }
    else
    {
        i = items.erase(i);

    }

}

items.remove_if(CheckItemNotActive);

Answer 6

Альтернатива для петлевой версии ответа Кристо.

Вы теряете некоторую эффективность, при удалении вы идете назад и затем снова вперед, но в обмен на дополнительное приращение итератора вы можете объявить итератор в области видимости цикла, а код выглядит немного чище. Что выбрать, зависит от приоритетов на данный момент.

Ответ был совершенно несвоевременным, я знаю ...

typedef std::list<item*>::iterator item_iterator;

for(item_iterator i = items.begin(); i != items.end(); ++i)
{
    bool isActive = (*i)->update();

    if (!isActive)
    {
        items.erase(i--); 
    }
    else
    {
        other_code_involving(*i);
    }
}

Answer 7

У меня есть сумма, вот три метода с примером:

1. используя while loop

list<int> lst{4, 1, 2, 3, 5};

auto it = lst.begin();
while (it != lst.end()){
    if((*it % 2) == 1){
        it = lst.erase(it);// erase and go to next
    } else{
        ++it;  // go to next
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

2. используя remove_if функцию участника в списке:

list<int> lst{4, 1, 2, 3, 5};

lst.remove_if([](int a){return a % 2 == 1;});

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

3. использование функции std::remove_if в сочетании с функцией-членом erase:

list<int> lst{4, 1, 2, 3, 5};

lst.erase(std::remove_if(lst.begin(), lst.end(), [](int a){
    return a % 2 == 1;
}), lst.end());

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

4. используя цикл for, следует обновить итератор:

list<int> lst{4, 1, 2, 3, 5};

for(auto it = lst.begin(); it != lst.end();++it){
    if ((*it % 2) == 1){
        it = lst.erase(it);  erase and go to next(erase will return the next iterator)
        --it;  // as it will be add again in for, so we go back one step
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2 

Answer 8

Вы можете написать

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive) {
        i = items.erase(i); 
    } else {
        other_code_involving(*i);
        i++;
    }
}

Вы можете написать эквивалентный код с помощью std::list::remove_if, который является менее подробным и более явным

items.remove_if([] (item*i) {
    bool isActive = (*i)->update();
    if (!isActive) 
        return true;

    other_code_involving(*i);
    return false;
});

Идиому std::vector::erase std::remove_if следует использовать, когда элементы являются вектором, а не списком, чтобы сохранить целостность на уровне O (n), или если вы пишете общий код, а элементы могут быть контейнером без эффективного способа стереть отдельные элементы (например, вектор)

items.erase(std::remove_if(begin(items), end(items), [] (item*i) {
    bool isActive = (*i)->update();
    if (!isActive) 
        return true;

    other_code_involving(*i);
    return false;
}));

Answer 9

Если вы думаете о std::list как о очереди, то вы можете удалить из очереди и поставить в очередь все элементы, которые вы хотите сохранить, но только удалить из очереди (а не поставить в очередь) элемент, который вы хотите удалить. Вот пример, где я хочу удалить 5 из списка, содержащего числа 1-10 ...

std::list<int> myList;

int size = myList.size(); // The size needs to be saved to iterate through the whole thing

for (int i = 0; i < size; ++i)
{
    int val = myList.back()
    myList.pop_back() // dequeue
    if (val != 5)
    {
         myList.push_front(val) // enqueue if not 5
    }
}

myList теперь будет иметь только цифры 1-4 и 6-10.

Answer 10

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

Таким образом, в этом случае после удаления * i, i становится недействительным, и вы не можете делать приращение на нем.

Что вы можете сделать - это сначала сохранить итератор элемента, который нужно удалить, затем увеличить итератор и затем удалить сохраненный.