Iterate & Erase
Par Benoît Dejean le dimanche, 22 avril 2007, 00:51 - Lien permanent
I have discovered a nice bug in my code. I had some stuff about iterating a std::list<> and removing some elements at the same time. Like the following :
std::list<> l;
iterator it(l.begin());
while (it != l.end()) {
if (...)
it = l.erase(it);
else
++it;
}
Then i moved from std::list<> to std::set<> (ordered set). The code didn't compile as is because std::set<>::erase returns void. The STL documentation says Erasing an element from a set also does not invalidate any iterators...
. OK then, no return value.
std::set<> s;
iterator it(s.begin());
while (it != s.end()) {
if (...)
s.erase(it);
++it;
}
It worked nicely for a long time. But once i got a double free crash. In order to debug it, i added many print. For example {1 2 3 5 6 7} - {3} shoud have printed {1 2 5 6 7} but instead i got {1 2 2 5 6 7} or {1 5 6 7 2} !
So i read again the documentation : Erasing an element from a set also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.
. Bon sang !
The correct way to do it :
std::set<> s;
iterator it(s.begin())
while (it != s.end()) {
iterator next(it);
++next;
if (...)
s.erase(it);
it = next;
}
Commentaires
s.begin() points to the first element of s.
when you do ++next _before_ the if, you never look at the first element.
++next should be after the if.
I am using next only at the end of the loop to move forward. Incrementing next doesn't increment it. I look at the current element using it, not next.
The following should also work.
<pre>
while (it != s.end()) { if (...) s.erase(it++); else ++it; }</pre>
erase() has a return value that should point to the next element.
murrayc > "void erase(iterator pos) Associative Container Erases the element pointed to by pos." http://www.sgi.com/tech/stl/set.htm...
Oskar > yep, may be it's even nicer.