On 05 Mar 99 12:27:26 GMT, Juergen Landwehr ATS/E #

>  list<int> l; // LINE1
>  list<int>::iterator it;
>
>  for (int x=0; x<10; x++) l.push_back (x); // LINE2
>
>  for (it=l.begin(); it != l.end(); it++) // LINE3
>  {
>    if ((*it) == 2) l.erase (it); // LINE4
>  }

After erasing 'it' in LINE4, the statement "++it" or "it++" on LINE3
is a memory access violation.  Ie, "++it" does "it.ptr=it.ptr->next"
and 'it.ptr' points to memory that has been deallocated.

   typedef std::list<int>::iterator Iter; // LINE3
   const Iter end=l.end();
   Iter iter=l.begin();
   while (iter!=end) {
      Iter now=iter;
      ++iter;
      if (*now==2) l.erase(now);
   };


But as this operation is so common, there is a templated member
function remove_if.

struct IsTwo { bool operator()(int x) const { return x==2; } };

int main()
{
   std::list<int> list;
   for (int x=0; x<10; x++) l.push_back (x);
   list.remove_if(IsTwo());
}


--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <36DF92E7.D37A9F72@navd.alcatel.de>,
Juergen Landwehr ATS/E #  <landwehr@navd.alcatel.de> wrote:

> I wonder if deleting elements within a STL container as follows is a
> normal/allowed way:

>   list<int> l;
>   list<int>::iterator it;

>   for (int x=0; x<10; x++) l.push_back (x);

>   for (it=l.begin(); it != l.end(); it++)
>   {
>     if ((*it) == 2) l.erase (it);
>   }

> It seems to be that (at least the implementation of the STL I use) has a
> problem with it

Yes indeed.  When you execute l.erase(it), that invalidates the iterator
it, so executing it++ is undefined behavior.  You should write

 it = l.begin();
 while (it != l.end()) {
  if (*it == 2)
   it = l.erase(it);
  else
   ++it;
 }

This uses the fact that erasing an element from a list returns an iterator
that refers to the element after the one that was erased.  This technique
works with vectors and deques, also.
--
    Andrew Koenig
    ark@research.att.com
    http://www.research.att.com/info/ark



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <slrn7e06bp.o2k.sbnaran@localhost.localdomain>,
  sbnaran@uiuc.edu wrote:
>
> On 05 Mar 99 12:27:26 GMT, Juergen Landwehr ATS/E #
>
> >  list<int> l; // LINE1
> >  list<int>::iterator it;
> >
> >  for (int x=0; x<10; x++) l.push_back (x); // LINE2
> >
> >  for (it=l.begin(); it != l.end(); it++) // LINE3
> >  {
> >    if ((*it) == 2) l.erase (it); // LINE4
> >  }
>
> After erasing 'it' in LINE4, the statement "++it" or "it++" on LINE3
> is a memory access violation.  Ie, "++it" does "it.ptr=it.ptr->next"
> and 'it.ptr' points to memory that has been deallocated.

Conceptually, yes, but the standard makes no mention of how it is defined or
should be implemented so "it.ptr=it.ptr->next" is not a requirement here.
All that you can really say is that it is no longer valid after a call to
erase(it).

>    typedef std::list<int>::iterator Iter; // LINE3
>    const Iter end=l.end();
>    Iter iter=l.begin();
>    while (iter!=end) {
>       Iter now=iter;
>       ++iter;
>       if (*now==2) l.erase(now);
>    };

The use of a temporary "now" iterator is uneeded, as others have pointed out,
since erase will return an iterator to the next element.

> But as this operation is so common, there is a templated member
> function remove_if.
>
> struct IsTwo { bool operator()(int x) const { return x==2; } };
>
> int main()
> {
>    std::list<int> list;
>    for (int x=0; x<10; x++) l.push_back (x);
>    list.remove_if(IsTwo());
> }

It is overkill to use remove_if, since a simple remove will achieve the same
thing in this case.

list.remove(2);

This also has the added benefit of working on compilers that can't handle
templated member functions (VC++ for instance).  Also, for containers that
don't support remove (or remove_if) you could apply the algorithm versions
instead (this would be a good idea in any event to allow for later changes to
a different container type).

list.erase(remove(list.begin(), list.end(), 2));

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hello there,

I wonder if deleting elements within a STL container as follows is a
normal/allowed way:

  list<int> l;
  list<int>::iterator it;

  for (int x=0; x<10; x++) l.push_back (x);

  for (it=l.begin(); it != l.end(); it++)
  {
    if ((*it) == 2) l.erase (it);
  }

It seems to be that (at least the implementation of the STL I use) has a
problem with it
Using purify I get the error "Free Memory Read" and in a more complex
example I also
managed ot crash the program.

So my question here is if it is just not allowed to delete an element in
the container and
still use the iterator pointed to it or if this is a bug in the STL
implementation I use

Thanks,

Juergen



--
--------------------------------------o00o----------------------
 Juergen Landwehr                     (mailto:landwehr@navd.alcatel.de)
 Alcatel ANS - Department ATS/E22     (Tel:   0711/821-43107 (Germany))
 Lorenzstrasse 10 - 70435 Stuttgart
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Definately wrong! By the time your loop continues to i++ you have already
invalidated i.  One of many ways to do it would be:
for ( it = i.begin(); it != i.end; ) {
   if ( *it == 2 )
      lst.erase(it++);
   else
      ++it
}

Juergen Landwehr ATS/E # <landwehr@navd.alcatel.de> wrote in message
news:36DF92E7.D37A9F72@navd.alcatel.de...
>Hello there,
>
>I wonder if deleting elements within a STL container as follows is a
>normal/allowed way:
>
>  list<int> l;
>  list<int>::iterator it;
>
>  for (int x=0; x<10; x++) l.push_back (x);
>
>  for (it=l.begin(); it != l.end(); it++)
>  {
>    if ((*it) == 2) l.erase (it);
>  }
>
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <36DF92E7.D37A9F72@navd.alcatel.de>,
  Juergen Landwehr ATS/E # <landwehr@navd.alcatel.de> wrote:
> Hello there,
>
> I wonder if deleting elements within a STL container as follows is a
> normal/allowed way:
>
>   list<int> l;
>   list<int>::iterator it;
>
>   for (int x=0; x<10; x++) l.push_back (x);
>
>   for (it=l.begin(); it != l.end(); it++)
>   {
>     if ((*it) == 2) l.erase (it);
>   }
>
> It seems to be that (at least the implementation of the STL I use) has a
> problem with it
> Using purify I get the error "Free Memory Read" and in a more complex
> example I also
> managed ot crash the program.
>
> So my question here is if it is just not allowed to delete an element in
> the container and
> still use the iterator pointed to it or if this is a bug in the STL
> implementation I use

Once it's been erased, an iterator is no longer valid.  This is why the erase
method returns an iterator to the next "position" within  the container.  You
can rewrite like this:

for (it=l.begin(); it != l.end(); )
{
   if ((*it) == 2)
      it = l.erase (it);
   else
      ++it;
}

Note, however, that for this specific example you'd be better off using the
algorithm that exists for this: remove_if.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Juergen Landwehr ATS/E # wrote in message
<36DF92E7.D37A9F72@navd.alcatel.de>...
>Hello there,
>
>I wonder if deleting elements within a STL container as follows is a
>normal/allowed way:
>
>  list<int> l;
>  list<int>::iterator it;
>
>  for (int x=0; x<10; x++) l.push_back (x);
>
>  for (it=l.begin(); it != l.end(); it++)
>  {
>    if ((*it) == 2) l.erase (it);
>  }
>
>It seems to be that (at least the implementation of the STL I use) has a
>problem with it
>Using purify I get the error "Free Memory Read" and in a more complex
>example I also
>managed ot crash the program.
>
>So my question here is if it is just not allowed to delete an element in
>the container and
>still use the iterator pointed to it or if this is a bug in the STL
>implementation I use

The iterator itself is invalidated, so the above code is faulty.

There is a another problem with that loop too - even if the iterator was
valid after erase, it would go haywire if the last element in the container
satisfied the condition.  After the l.erase(it) line, it would be l.end(),
and it would then be incremented in the for loop, giving undefined results,
and then compared with l.end(), which will almost certianly be false, even
if the universe didnt collapse when you increment the end iterator.  So it
*will* collapse shortly thereafter:)

cheers,
ian mcculloch



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]