Re: Iterator Invalidation Confusion
On Sep 30, 2:27 am, TxCHLInstructor <instruc...@chl-tx.com> wrote:
I got a question regarding iterator invalidation from a co-worker today,
and when I tried to explain it, I realized that my understanding of the
topic was incomplete.
From page 205 of The C++ Standard Library (Josuttis)
Here is an example of the correct way to remove elements to which an
iterator refers:
// remove all elements having a certain value
for ( pos = c.begin(); pos!= c.end(); )
{
if ( pos->second == value )
c.erase( pos++ ) // post-increment important
else
++pos;
}
In this example, c is a map or multimap.
However, for vectors, the situation appears to be more complicated. On
page 242: "for vectors and deques, erase() might invalidate iterators
and references to other elements in the container"
I have had enough problems with iterator invalidation (using MSVC9) that
I now always reset an iterator (typically, use begin(), then advance()
using a separately maintained counter) whenever I do an insert or an
erase, regardless of the type of container, but according to Josuttis,
this is not necessary for maps or multimaps. Is that really so?
Looks like it. You see, post-increment is equivalent to:
TYPE operator++(int)
{
TYPE temp(this);
++(*this);
return temp;
}
So... in erase(iterator++), your iterator is advanced first, then,
it's old value is passed to erase. Life is good.
The problem with a vector is that when you insert, it might re-
allocate space, which could invalidate "incremented" iterator. I think
that invalidation does not not happen for an erase, but I think that's
not guaranteed by the standard.
However... "Iterator" erase variants return a valid iterator that
"points" to the "next" element, so I think following:
while(pos!=container.end())
{
if (*pos == value) // Or some other condition
pos = container.erase(pos);
else
++pos;
}
should work with any container in your removal case.
Goran.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]