On Apr 26, 2:34 am, Carl Barron <cbarron...@[EMAIL PROTECTED]
> wrote:
> In article
> <6eaa63d2-cb20-432a-a500-dc610e9f8...@[EMAIL PROTECTED]
>,
> Greg Herlihy <gre...@[EMAIL PROTECTED]
> wrote:
> > Calling std::remove_if() on a std::list can invalidate the list's
> > iterators (meaning that after the call to remove_if() - each iterator
> > in the list might no longer reference the same value bas it did before
> > the call)
>
> True the iterators of the 'removed' items are invalid, but the
> iterators to the remaining ones are valid.
>
> bool is_even(int);
> std::list<int> foo;
> for(int i=0;i!=10;++i) foo.push_back(i); // list = {0,1,2,3,4,5,..9{
> std::list<int>::iterator last =
std::remove_if(foo.begin(),foo.end(),
> is_even);
>
> list is now {1,3,5,7,9,j,k,k,k,k} still 10 entries but only first 5
> [last points to j] are in the sequence. all iterators in
> [foo.begin(),last) are valid.
No, none of the list's original iterators - including all five
iterators whose values remove_if() did not delete - is still valid.
After the call to std::remove_if() in the example above, the iterators
for the values 1, 3, 5, 7, 9 - either wind up referring to a different
value or referring to no existing value in the list at all (and in
either case - an iterator that no longer points to the same
(undeleted) value in the list - is - as far as both the programmer
and the C++ Standard is concerned - an invalidated iterator.
In contrast, calling list::remove_if() instead of std::remove_if()
will guarantee that only those iterators whose values were removed
from the list will have become invalid after the call. Otherwise, each
of the iterators to the values that remain in the list, will continue
to refer to the same, exact value that the iterator refered to before
the call - as it does after the call.
In fact the only reason why std::list provides its own versions of
routines like remove_if(), reverse() and sort() - is precisely to
guarantee the stability of the list's iterators. Because as surprising
as it might seem at first, list::sort() sorts the contents of the list
without swapping or copying any of the elements in the list. In other
words, every one of the list's iterators after the sort, is guaranteed
to refer to the same element as it did before the list was sorted.
Calling std::sort() would not of course provide any such guarantee.
And in fact, the next C++ Standard will no longer require that types
stored in a std::list be copyable. So there will be longer be possile
to call std::remove_if() for any type of std::list in the future.
> If you want the garbage [denote as j or k above] then call erase with
> two iterators or better still use the list::remove_if() member function
> and the items will be physically removed from the list in one pass that
> is foo.remove_if(is_even); will make foo.size() == 5 while
> std::remove_if(...) will leave foo.size()==10,
Yes, the fact that std::list's remove_if() routine actually removes
the items from the container - while std::remove_if() does seem a
little surprising - to put it charitably.
Greg
--
[ See http://www.gotw.ca/resources/clcm.htm
for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
