🚀 go-pugleaf

"brian (b.c.) white" <bcwhite@bnr.ca> wrote:
>Does the STL define the case where a container is modified while
>iterating through it?

Yes. In general "all iterators are invalidated
by insertion or deletion". However, it depends
on the container. 

For example, for a list,
the ONLY operation that can stuff things up
is deleting an element to which another
iterator points. (Make sure you don't cache
list.end())

For a vector, if you say "reserve(enough_space)"
you can do whatever would work for an array of
enough_space elements.

-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

> ==========b.c., 11/6/95==========
> 
> Does the STL define the case where a container is modified while
> iterating through it?
> 
> Example:  (forgive me if the syntax isn't perfect...)
> 
>           class X x;
> 
>           for (X::iterator ix=x.begin(); ix != x.end(); ix++) {
>                     ix.erase();
>           }
> 
>                                         Brian
>                                  ( bcwhite@bnr.ca )
> 
> -----------------------------------------------------------------

This assumes that ix does not change during erase()
and so that the range is the same.  This form is
inherently problematic.  So, lets try a better form for the
problem.

        class X x;
        for ( X::iterator ix=x.begin(); ix != x.end(); ix.erase() );

where ix.erase() changes ix to continue to "point to" a
valid value or to x.end() when none are left.

How about this case?

Good Day
Dick
Dick.Menninger@DaytonOH.ATTGIS.COM


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

> Does the STL define the case where a container is modified while
> iterating through it?
Depends on the type of container.

> Example:  (forgive me if the syntax isn't perfect...)
> 
> 		class X x;
> 
> 		for (X::iterator ix=x.begin(); ix != x.end(); ix++) {
> 				ix.erase();
> 		}
> 

I quote from the documentation to the free HP implementation (somebody
please correct if this doesn't match the draft):

vector:
erase invalidates all the iterators and references after the point of
the erase.
Thus your code won't work for vectors since ix always references the
element after the point of the erase.

list:
erase invalidates only the iterators and references to the erased
elements.
Your code works.

deque:
erase [and pop] invalidate all the iterators and refrecnces to the
deque.
Your code doesn't work.

Nothing is said for the associative containers, though.

Thomas


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

maeder@glue.CH (Thomas Maeder) wrote:
>
..
>
>Nothing is said for the associative containers, though.

My copy of the STL document (7th paragraph of section 8.2 "Associative
Containers") says:
"erase invalidates only  the iterators and references to the erased elements."

>
>Thomas
-- 
Alexander Stepanov
stepanov@mti.sgi.com


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <9511122227.AA22118@eniac.glue.ch> maeder@glue.CH (Thomas
Maeder) writes:

|> > Does the STL define the case where a container is modified while
|> > iterating through it?
|> Depends on the type of container.

|> > Example:  (forgive me if the syntax isn't perfect...)
|> > 
|> > 		class X x;
|> > 
|> > 		for (X::iterator ix=x.begin(); ix != x.end(); ix++) {
|> > 				ix.erase();

There is no function erase in the iterator.  This should be:

                                x.erase( ix ) ;

|> > 		}
|> > 

|> I quote from the documentation to the free HP implementation (somebody
|> please correct if this doesn't match the draft):

|> list:
|> erase invalidates only the iterators and references to the erased
|> elements.
|> Your code works.

Since the iterator ix references the erased object, it becomes
invalid.

Whether the code works or not depends on what is meant by
`invalidates'.  I think, in fact, that invalidates implies that *all*
further operations on the iterator are illegal. If this is the case,
then the comparison with x.end() after the x.erase( ix ) is illegal.

I seem to recall having heard somewhere that in the actual STL
implementation, the iterator to a vector is just a simple pointer.  If
that is true, the above erase every other element, and if the initial
number of elements were odd, will result in an endless loop (with
erase being called with illegal pointer values).

One of the most useful idioms I've found with lists looks something
like the following (with my list class):

	GB_DLListOf< T >    list ;
	for ( GB_DLListOf::Index i( list ) ; ! i.finished() ; ++ i )
	{
	    if ( someCondition( list[ i ] ) )
	        list.remove( i ) ;
	}

I hope the function names are clear enough without explination.  My
"iterators" are called Index, and have index semantics instead of
pointer semantics.  They are completely safe: removing the object
referenced by the iterator causes all further attempts to dereference
the iterator to fail, but does not otherwise invalidate the iterator,
nor change its position; incrementing it will cause it to point at the
object which followed the removed object, as one would naively expect.

To do the same with STL requires something like the following:

	list< T >           myList ;
	list< T >::iterator i( myList.begin() ) ;
	while ( i != myList.end() )
	{
	    list< T >::iterator      curr( i ++ ) ;
	    if ( someCondition( *curr ) )
	        myList.erase( curr ) ;
	}

The incrementation *must* take place before the erase in order to work
correctly.
--

--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils, études et réalisations en logiciel orienté objet --
                -- A la recherche d'une activité dans une region francophone



---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

>>>>> 40763  <James> writes:

> One of the most useful idioms I've found with lists looks something
> like the following (with my list class):

> 	GB_DLListOf< T >    list ;
> 	for ( GB_DLListOf::Index i( list ) ; ! i.finished() ; ++ i )
> 	{
> 	    if ( someCondition( list[ i ] ) )
> 	        list.remove( i ) ;
> 	}

> To do the same with STL requires something like the following:

> 	list< T >           myList ;
> 	list< T >::iterator i( myList.begin() ) ;
> 	while ( i != myList.end() )
> 	{
> 	    list< T >::iterator      curr( i ++ ) ;
> 	    if ( someCondition( *curr ) )
> 	        myList.erase( curr ) ;
> 	}

> The incrementation *must* take place before the erase in order to work
> correctly.

This should work:

	list< T >           myList ;
	for ( list< T >::iterator i( myList.begin() ); i != myList.end(); )
	{
	    if ( someCondition( *i ) )
	        myList.erase( i++ ) ;
	}

Looks pretty similar, doesn't it?  Note that operator++ increments i
before it returns a value to be used in the erase.

Jason
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <u9ka52iwn4.fsf@yorick.cygnus.com>, jason@cygnus.com (Jason Merrill) writes:
|> This should work:
|> 
|> 	list< T >           myList ;
|> 	for ( list< T >::iterator i( myList.begin() ); i != myList.end(); )
|> 	{
|> 	    if ( someCondition( *i ) )
|> 	        myList.erase( i++ ) ;
|> 	}
|> 
|> Looks pretty similar, doesn't it?  Note that operator++ increments i
|> before it returns a value to be used in the erase.

Well, if someCondition doesn't hold, then i doesn't get incremented, and you
spend quite a long time in the loop :-)

I think you need to add an

	else {
	    ++i;
	}

to the if statement.

-- 
Anil A. Pal
pal@sgi.com	(415)-933-5279


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <u9ka52iwn4.fsf@yorick.cygnus.com> jason@cygnus.com (Jason
Merrill) writes:

|> >>>>> 40763  <James> writes:

|> > One of the most useful idioms I've found with lists looks something
|> > like the following (with my list class):

|> > 	GB_DLListOf< T >    list ;
|> > 	for ( GB_DLListOf::Index i( list ) ; ! i.finished() ; ++ i )
|> > 	{
|> > 	    if ( someCondition( list[ i ] ) )
|> > 	        list.remove( i ) ;
|> > 	}

|> > To do the same with STL requires something like the following:

|> > 	list< T >           myList ;
|> > 	list< T >::iterator i( myList.begin() ) ;
|> > 	while ( i != myList.end() )
|> > 	{
|> > 	    list< T >::iterator      curr( i ++ ) ;
|> > 	    if ( someCondition( *curr ) )
|> > 	        myList.erase( curr ) ;
|> > 	}

|> > The incrementation *must* take place before the erase in order to work
|> > correctly.

|> This should work:

|> 	list< T >           myList ;
|> 	for ( list< T >::iterator i( myList.begin() ); i != myList.end(); )
|> 	{
|> 	    if ( someCondition( *i ) )
|> 	        myList.erase( i++ ) ;
|> 	}

|> Looks pretty similar, doesn't it?  Note that operator++ increments i
|> before it returns a value to be used in the erase.

This is the way I first wrote it, too.  So what happens when
someCondition is false.  (Presumably, it will be sometimes.
Otherwise, you would just write ``myList = list< T >() ;''.)

The correct body would become:

	if ( someCondition( *i ) )
	    myList.erase( i ++ ) ;
	else
	    ++ i ;

This looks like a maintenance nightmare to me.  Incrementing the
iterator in two separate places certainly makes it more difficult to
ensure that the iterator *does* get incremented (in all cases).  As
this is such an important part of the loop control structure (and the
guarantee that the loop terminates in finite time), I really want to
see it in the for statement.  Failing that, it should be in *one*
easily found place.

Note that my version using the STL really only contains one more
statement than my version using the fully safe iterators.  There is a
trade-off involved; my iterator *must* be a full class object, and its
construction involves registration with the container.  Even simple
indexation is more expensive, since it has to cope with the case where
the object under the iterator has been deleted.  This cost is present
even in programs which don't delete objects under the iterator.

In my opinion, the added cost is minimal, and well worth it.  But I
believe that the authors of the STL were aware of this alternative;
the current situation is the result of a concious choice, and not
simply a result of oversight or some such.

--
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils, études et réalisations en logiciel orienté objet --
                -- A la recherche d'une activité dans une region francophone


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]