[RESOLVED] Removing items from a std:: list within a loop

[AdamDH]

std::list<ClassA*> m_List;
std::list<ClassA*>::iterator l_Iter;

m_list.push_back(new ClassA(1));
m_list.push_back(new ClassA(2));
m_list.push_back(new ClassA(3));
m_list.push_back(new ClassA(4));
m_list.push_back(new ClassA(5));
m_list.push_back(new ClassA(6));

for (l_Iter = m_List.begin(); l_Iter != m_List.end(); l_Iter++)
{
if ((*l_Iter)->IsOdd())
{
// Delete classes that have odd numbers
delete (*l_Iter);

m_List.erase(l_Iter);

// QUESTION: How should I adjust the iterator to be valid?
}
}



In the case above I am deleting all ClassA's that have odd numbers assigned to them. When one is found the ClassA object is deleted from memory and the iterm is removed from the list. Once this happens the iterator being used in the for loop is no longer valid and must be adjusted so that the loop can continue. What's the best way to do this?

Instead of a loop, I've thought about using remove_if with a predicate that looks for ClassA's with odd numbers, and using the returned ForwardIterator to end() to delte the ClassA's it found. I have seen list has it's own remove_if function but it does NOT return a ForwardIterator so I cannot rely on this. Is the STL remove_if valid for a std::list?

I'm sure there is a simple solution to this, I am just not seeing it.

I am assuming I could also do something like this as well:


for (l_Iter = m_List.begin(); l_Iter != m_List.end(); l_Iter++)
{
if ((*l_Iter)->IsOdd())
{
// save the item in the list before this one
std::list<ClassA*>::iterator l_TempIter = l_Iter--;

// Delete classes that have odd numbers
delete (*l_Iter);

m_List.erase(l_Iter);

l_Iter = l_TempIter;

}
}



Thanks for your input,
Adam

[wildfrog]

MSDN (http://msdn2.microsoft.com/en-us/library/9fyx5kx8(VS.80).aspx) has a sample of std::list and remove_if.

- petter

[AdamDH]

I should have read the full description of list::erase(). Erase returns an iterator to the next element. I can do this:


for (l_Iter = m_List.begin(); l_Iter != m_List.end(); l_Iter++)
{
if ((*l_Iter)->IsOdd())
{

// Delete classes that have odd numbers
delete (*l_Iter);

l_Iter = m_List.erase(l_Iter)--;

}
}


Correct?

[TheCPUWizard]

I believe that should work. I prefer a safer methodology which will work for ALL types of collections, regardless of the type or operation.

1) Iterate through collection, insert items to be deleted into a different temporary collection.

2) Iterate throug temporary collection, removing items from the real collection.

3) Delete temportary collection.

This does have some overhead associated. For large collections it may become an issue [this is determined after implementing it and measuring the performance with typical and maximal data to see if it impacts performance at the application level]. In my experience 90%+ of the time it does not.

The only time I have seen is where I am starting with a VERY large collection, and I am going to be removing the majority of the items. In this case

1) Iterate through collection, insert items to be KEPT into a different temporary collection.

2) Replace real collection with temportary collection.

[AdamDH]

Thanks for your reply.

I do agree that it is much safer not to monkey around with the loop iterator while inside the loop. I never like doing this. I think I'll go with your method.

I've seen a lot of my coworkers decrement a for loop iterator when removing something from the middle of a vector knowing that everything will get shifted and copied down in memory (why not use a list). I've never been comfortable with that implementation and I've always found another way: like saving off the element to be erased, breaking from the loop or letting it end, and then removing it from the vector (of course for this work with a range of elements to be deleted one would have to follow your suggestion).

There ought to be a way to write a template function for this sort of thing because I do it all the time.

[Philip Nicoletti]

1) if possible, use remove_if member function for lists (and std::remove_if
for vectors/deques/strings).

2) Here are two accepted methods for erasing while iterating. One for
sequence containers and one for associative containers)


// for sequence containers
for (l_Iter = m_List.begin(); l_Iter != m_List.end(); /* nothing here */ )
{
if ((*l_Iter)->IsOdd())
{

// Delete classes that have odd numbers
delete (*l_Iter);

l_Iter = m_List.erase(l_Iter);

}
else
{
++l_iter;
}
}

// for associative containers (and list)
for (l_Iter = m_List.begin(); l_Iter != m_List.end(); /* nothing here */ )
{
if ((*l_Iter)->IsOdd())
{

// Delete classes that have odd numbers
delete (*l_Iter);

m_List.erase(l_Iter++);

}
else
{
++l_iter;
}
}


See :

1) "Effective STL" by Meyers (Item 9 : Choose carefully among erasing options)

2) "The Standard C++ Library" by Josuttis (page 205 in my edition).

[TheCPUWizard]

if possible, use remove_if member function for lists (and std::remove_if
for vectors/deques/strings).

I have nothing against using remove_if per se.

One thing that influences many of my architectural designs is that I very often need to implement some type of "rollback" capability. For UI's this is typically for undo/redo, for other applications it is for wrapping all actions into some type of "transaction".

The use of a temporrary collection (placed into the "command queue") facilitates this. It also allows for the addition of "validations" after the items to be removed are ALL identified, but before any of them are actually removed. Finally, for certain cases, the time to determine which items need to be removed may be non-trivial. In a multi-threaded situation, in conjunction with reader/writer locks, the time period where the collection must be exclusively locked can be reduced.

There is always a tradeoff between implementations. My main foci are re-usability and consistancy (along with maintainability and testability, but that is a diffrent topic). As a result I tend to choose implementations that meet the most general cases. When implemented as a template and/or functor, becomes very attractive in meeting these goals.