C++ : deleting multiple elements of a list while iterating the list

Question

I know how do erase elements of a list, and that erase return a valid iterater. My problem is, that I want to remove not just one element but multiple.

Actuall my code is like

 for(list<Treenode*>::iterator it=currentLevel->begin(); it!=currentLevel->end(); ++it){
     if(something(*it))  {
         for(list<Treenode*>::iterator it2=currentNewLevel->begin();it2!=currentNewLevel->end();){
             if (somethingDifferent(*it2)) {
                 it2=currentLevel->erase(it2);
             } else {
                 ++it2;
             }
         }
     }
 }

of course this could not work, because it is not changed. I don't know how to change the iterator but stay on this iteration-step.

Thank you for reading. I hope someone know the answer.

Maybe I am simple minded: if(it2 == it) adjust it, too, after erase — user2249683
– user2249683, Commented Aug 18, 2013 at 9:12

juanchopanza · Accepted Answer · 2013-08-18 09:13:48Z

4

In general, the way to remove elements from a list based depending on a condition is to use the std::list::remove_if member function.

bool pred(const Treenode* t) { .... }
currentNewLevel.remove_if(pred);

The predicate can be a functor, so it can keep any state that is required to implement the removal criteria:

#include <algorithm> // for std::find_if
#include <list>

// unary predicate functor. Returns true if an element of a reference
// list satisfies "something" and the functor call argument satisfies "somethingDifferent"
struct Pred
{
  Pred(const std::list<Treenode*>& nodes) : nodes_(nodes) {}
  bool (const Treenode* t) const
  {
    return std::find_if(nodes_.begin(), nodes_.end(), something) != nodes_.end() &&
           somethingDifferent(t);
  }
 private:
  const std::list<Treenode*>& nodes_;
};

then

Pred p(currentLevel);
currentLevel.remove_if(p);

edited Aug 18, 2013 at 9:13

answered Aug 18, 2013 at 8:39

juanchopanza

228k35 gold badges421 silver badges493 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Name Over a year ago

Thank you. The problem is I do some other stuff in the outer loop. I could use your way for the inner loop but than the iterator of the outer loop would not be valid.

juanchopanza Over a year ago

@user2693497 you could write a functor that uses currentLevel. And I don't really see the problem with the outer loop iterator. You should probably explain what you are trying to achieve.

juanchopanza Over a year ago

@Name I added an example with a functor. It does what I think your original code was trying to do.

Name Over a year ago

thank you again. the "if(SomethinDifferent){...} " part is just a little part of what I do for each list-entry. I do a lot of stuff that change the other list-entrys eventually. the changed list-entrys should not be visited by the iterator. So I want to remove them from currentLevel. So I really need the outer loop. I thougt wenn removing elements from a list I iterate I get a segmentation-fault. But this is only true when removing the element the iterator shows at at the moment. So I only have to make sure I do not remove this element. Thanks for help!

Oliver Stieber · Accepted Answer · 2020-07-12 19:38:49Z

0

do while loop. it's mostly ++ too so the performance should be good.

std::vector<PdfTextRegion*>::const_iterator textRegion = m_pdfTextRegions.begin();
    while(textRegion != m_pdfTextRegions.end())        
    {
        if ((*textRegion)->glyphs.empty())
        {
            m_pdfTextRegions.erase(textRegion);
            textRegion = m_pdfTextRegions.begin();
        }
        else
            textRegion++;
    }

edited Jul 12, 2020 at 19:38

answered Jul 12, 2020 at 19:19

Oliver Stieber

113 bronze badges

1 Comment

Useless Over a year ago

The performance can easily be horrible - worst case O(n**2), since it starts from the beginning every time. The remove_if version, which swaps the targeted elements to the end, is guaranteed linear time and single-pass. It's better in absolutely every way.

Collectives™ on Stack Overflow

C++ : deleting multiple elements of a list while iterating the list

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related