Topic: Modifying STL containers via an iterator
Author: jason@cygnus.com (Jason Merrill)
Date: 1995/11/15 Raw View
>>>>> 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. ]
Author: pal@xanadu.engr.sgi.com (Anil A. Pal)
Date: 1995/11/15 Raw View
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. ]
Author: James Kanze US/ESC 60/3/141 #40763 <kanze@lts.sel.alcatel.de>
Date: 1995/11/15 Raw View
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. ]
Author: John Max Skaller <maxtal@suphys.physics.su.oz.au>
Date: 1995/11/08 Raw View
"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. ]
Author: Dick Menninger <Dick.Menninger@daytonoh.attgis.com>
Date: 1995/11/10 Raw View
> ==========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. ]
Author: maeder@glue.CH (Thomas Maeder)
Date: 1995/11/13 Raw View
> 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. ]
Author: Alexander Stepanov <stepanov@murrow.corp.sgi.com>
Date: 1995/11/13 Raw View
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. ]