Re: Deleting items from an std::list , is this code correct?
In article
<c2d30ddb-efea-4c07-be42-b34304602329@z24g2000prf.googlegroups.com>,
Greg Herlihy <greghe@mac.com> wrote:
On Apr 26, 2:34 am, Carl Barron <cbarron...@adelphia.net> wrote:
In article
<6eaa63d2-cb20-432a-a500-dc610e9f8...@u12g2000prd.googlegroups.com>,
Greg Herlihy <gre...@mac.com> 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.
List provides remove/remove_if members because the operations are
'cheap' and only involve internal pointer manipuation to modify the
list. Further this can be done without invoking a copy ctor. Both
good reasons for implementation in std::list<T,A>.
For what its worth , this shows what I said is true and the iterators
in [ints,begin(),last) are all valid.
run this:
<code>
#include <list>
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
inline bool is_even(int x) { return x%2 == 0;}
int main()
{
std::list<int> ints;
std::vector<std::list<int>::iterator> its;
for(int i=0;i!=10;++i) ints.push_back(i);
for(std::list<int>::iterator i=ints.begin();i!=ints.end();++i)
its.push_back(i);
std::list<int>::iterator last = std::remove_if
(ints.begin(),ints.end(),is_even);
std::copy(ints.begin(),last,std::ostream_iterator<int>(std::cout,"\n"));
std::cout << "\nvalues of original iterators:\n";
for(std::vector<std::list<int>::iterator>::iterator it =
its.begin();it != its.end();++it)
{
std::cout << **it << '\n';
};
std::cout << "\nvalues of incrementing original iterators:\n";
for(std::vector<std::list<int>::iterator>::iterator it =
its.begin();it != its.end();++it)
{
std::list<int>::iterator p = *it;
if(p==ints.end()) continue;
++p;
std::cout << *p << '\n';
}
}
</code>
<ans>
1
3
5
7
9
values of original iterators:
1
3
5
7
9
5
6
7
8
9
values of incrementing original iterators:
3
5
7
9
5
6
7
8
9
</ans>
looks like iterators pointing into [ints.begin(),last) all are valid
and they increment properly. iterators pointing to the removed but
not erased point to the same values and increment correctly to me.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]