CODEWITHSUNDEEP
c++liststdstdlist
AShelly
AShelly

Reputation: 35600

Can you remove elements from a std::list while iterating through it?

I've got code that looks like this:

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'd like remove inactive items immediately after update them, in order to avoid walking the list again. But if I add the commented-out lines, I get an error when I get to i++: "List iterator not incrementable". I tried some alternates which didn't increment in the for statement, but I couldn't get anything to work.

What's the best way to remove items as you are walking a std::list?

Upvotes: 292

Views: 312393

Answers (15)

Michael Kristofik
Michael Kristofik

Reputation: 35218

You have to:

  1. Increment the iterator (with i++).
  2. Remove the previous element (e.g., by using the returned value from i++).

You can change the code to a while loop like so:

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

Upvotes: 352

rherrmannr
rherrmannr

Reputation: 338

With C++20, you can use std::erase_if:

std::erase_if(items, [](auto& i){ 
  if (!i.update()) {
    return true;
  }
  other_code_involving(i);
  return false;
};

Upvotes: 5

mach6
mach6

Reputation: 408

I'd like to share my method. This method also allows the insertion of the element to the back of the list during iteration

#include <iostream>
#include <list>

int main(int argc, char **argv) {
  std::list<int> d;
  for (int i = 0; i < 12; ++i) {
    d.push_back(i);
  }

  auto it = d.begin();
  int nelem = d.size(); // number of current elements
  for (int ielem = 0; ielem < nelem; ++ielem) {
    auto &i = *it;
    if (i % 2 == 0) {
      it = d.erase(it);
    } else {
      if (i % 3 == 0) {
        d.push_back(3*i);
      }
      ++it;
    }
  }

  for (auto i : d) {
      std::cout << i << ", ";
  }
  std::cout << std::endl;
  // result should be: 1, 3, 5, 7, 9, 11, 9, 27,
  return 0;
}

Upvotes: 1

Mykola Golubyev
Mykola Golubyev

Reputation: 59922

Use std::remove_if algorithm.

Edit:
Work with collections should be like:

  1. prepare collection.
  2. process collection.

Life will be easier if you won't mix this steps.

  1. std::remove_if. or list::remove_if ( if you know that you work with list and not with the TCollection )
  2. std::for_each

Upvotes: 10

Oliver Stieber
Oliver Stieber

Reputation: 11

do while loop, it's flexable and fast and easy to read and write.

auto textRegion = m_pdfTextRegions.begin();
    while(textRegion != m_pdfTextRegions.end())
    {
        if ((*textRegion)->glyphs.empty())
        {
            m_pdfTextRegions.erase(textRegion);
            textRegion = m_pdfTextRegions.begin();
        }
        else
            textRegion++;
    }

Upvotes: 1

Mike
Mike

Reputation: 1267

You need to do the combination of Kristo's answer and MSN's:

// 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 != 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);
    }
}

Of course, the most efficient and SuperCool® STL savy thing would be something like this:

// 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)));

Upvotes: 30

sancho.s ReinstateMonicaCellio
sancho.s ReinstateMonicaCellio

Reputation: 15641

Iterating backwards avoids the effect of erasing an element on the remaining elements to be traversed:

typedef list<item*> list_t;
for ( list_t::iterator it = items.end() ; it != items.begin() ; ) {
    --it;
    bool remove = <determine whether to remove>
    if ( remove ) {
        items.erase( it );
    }
}

PS: see this, e.g., regarding backward iteration.

PS2: I did not thoroughly tested if it handles well erasing elements at the ends.

Upvotes: 3

Jayhello
Jayhello

Reputation: 6602

I have sumup it, here is the three method with example:

1. using 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. using remove_if member funtion in list:

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. using std::remove_if funtion combining with erase member function:

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. using for loop , should note update the iterator:

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

Upvotes: 14

Alex Bagg
Alex Bagg

Reputation: 21

If you think of the std::list like a queue, then you can dequeue and enqueue all the items that you want to keep, but only dequeue (and not enqueue) the item you want to remove. Here's an example where I want to remove 5 from a list containing the numbers 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 will now only have numbers 1-4 and 6-10.

Upvotes: 2

J. Kalz
J. Kalz

Reputation: 19

You can write

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

You can write equivalent code with std::list::remove_if, which is less verbose and more explicit 

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

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

The std::vector::erase std::remove_if idiom should be used when items is a vector instead of a list to keep compexity at O(n) - or in case you write generic code and items might be a container with no effective way to erase single items (like a vector)

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

Upvotes: 1

David Cormack
David Cormack

Reputation: 326

Here's an example using a for loop that iterates the list and increments or revalidates the iterator in the event of an item being removed during traversal of the list.

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

Upvotes: 5

Marcin Skoczylas
Marcin Skoczylas

Reputation: 19

I think you have a bug there, I code this way:

for (std::list<CAudioChannel *>::iterator itAudioChannel = audioChannels.begin();
             itAudioChannel != audioChannels.end(); )
{
    CAudioChannel *audioChannel = *itAudioChannel;
    std::list<CAudioChannel *>::iterator itCurrentAudioChannel = itAudioChannel;
    itAudioChannel++;

    if (audioChannel->destroyMe)
    {
        audioChannels.erase(itCurrentAudioChannel);
        delete audioChannel;
        continue;
    }
    audioChannel->Mix(outBuffer, numSamples);
}

Upvotes: -4

Rafael Gago
Rafael Gago

Reputation: 145

The alternative for loop version to Kristo's answer.

You lose some efficiency, you go backwards and then forward again when deleting but in exchange for the extra iterator increment you can have the iterator declared in the loop scope and the code looking a bit cleaner. What to choose depends on priorities of the moment.

The answer was totally out of time, I know...

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

Upvotes: 5

anand
anand

Reputation: 11349

Removal invalidates only the iterators that point to the elements that are removed.

So in this case after removing *i , i is invalidated and you cannot do increment on it.

What you can do is first save the iterator of element that is to be removed , then increment the iterator and then remove the saved one.

Upvotes: 3

MSN
MSN

Reputation: 54634

You want to do:

i= items.erase(i);

That will correctly update the iterator to point to the location after the iterator you removed.

Upvotes: 163

Related Questions