STL map iteration & insertion conflict question
Michael Ortega
Hi everybody.
I have the following problem. I have a map (and a multimap,
but thats off the point) where I need to iterate
over all elements while I insert and delete some of them.
Thing is this
1) I start with empty map.
2) some inserts
3) get an iterator to the start
4) iterator gets advanced, some new items inserted, some delete.
5) iterator reaches the end by which time the container is empty.
In short, the container starts empty and finishes empty. I
never use the iterator to delete, instead I use a different iterator
to do the deletion. While the inserts/deletes are not concurrent,
they are however interleaved with accesses to the traversing iterator.
My question is if this is ok or not. I suspect that the iterator
will become invalid in face of inserts deletes.
My program however relies on this, one suggestion I heard was to
have a second container with iterators where I keps iterators
pointing to the "deleted" items. This is however not good for
me since in the end everything will be empty anyway. The goal
of the intermediate deletes is both correctness and efficiency.
At any given time, the number of entries will be small (100-1000)
but the whole of the data items that will go in and out of it
reaches the millions, so I don't want to do this trick.
Thanks, any help appreciated.
Michael Ortega
orte...@cs.uiuc.edu
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
P.J. Plauger
Michael Ortega <orte...@uiuc.edu> wrote in article
<6ltvvh$7...@netlab.cs.rpi.edu>...
> I have the following problem. I have a map (and a multimap,
> but thats off the point) where I need to iterate
> over all elements while I insert and delete some of them.
> Thing is this
>
> 1) I start with empty map.
> 2) some inserts
> 3) get an iterator to the start
> 4) iterator gets advanced, some new items inserted, some delete.
> 5) iterator reaches the end by which time the container is empty.
>
> In short, the container starts empty and finishes empty. I
> never use the iterator to delete, instead I use a different iterator
> to do the deletion. While the inserts/deletes are not concurrent,
> they are however interleaved with accesses to the traversing iterator.
>
> My question is if this is ok or not. I suspect that the iterator
> will become invalid in face of inserts deletes.
The iterator becomes invalid only if you delete (erase) the element
it designates. Otherwise, what you're doing sounds safe enough.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Christopher M. Gurnee
Michael Ortega wrote in message <6ltvvh$7...@netlab.cs.rpi.edu>...
>Hi everybody.
>I have the following problem. I have a map (and a multimap,
>but thats off the point) where I need to iterate
>over all elements while I insert and delete some of them.
>Thing is this
>
>1) I start with empty map.
>2) some inserts
>3) get an iterator to the start
>4) iterator gets advanced, some new items inserted, some delete.
>5) iterator reaches the end by which time the container is empty.
[rest of message deleted]
I'm not quite sure what your ultimate goal is, but I can describe what
happens when you interleave inserts and erases.
This applies to [multi]maps and [multi]sets. When you erase en
element, the *only* iterators that become invalidated are iterators
that used to point to the erased item. Other iterators continue to
point to the same items they used to. An insertion causes *no*
iterators to become invalidated. The new item is inserted into the
container in the appropriate position, possibly in between two
elements to which you have iterators pointing, and then life goes on.
This can cause iterators to point to different *positions* into the
container, the 6th instead of the 5th position, for example, but the
*item* that a given iterator points to doesn't change.
This means that if you are iterating through the container from
beginning to end, and inserting elements as you go along, some of
these elements may get inserted before the "cur" iterator if the
inserted element's key compares less than the (*cur)'s key. In order
to erase these new elements, you may need to start over again or
decrement the cur iterator, depending on what you are trying to do.
If you are trying to use the map as a priority queue (as it sounds
like you might be doing), you should take a look at STL's
priority_queue.
I hope I've been helpful without being too long-winded (it's raining
here in Mass, that tends to make me write longer messages :) )
-Chris Gurnee
Joe Gottman
Michael Ortega wrote:
> Hi everybody.
> I have the following problem. I have a map (and a multimap,
> but thats off the point) where I need to iterate
> over all elements while I insert and delete some of them.
> Thing is this
>
> 1) I start with empty map.
> 2) some inserts
> 3) get an iterator to the start
> 4) iterator gets advanced, some new items inserted, some delete.
> 5) iterator reaches the end by which time the container is empty.
>
> In short, the container starts empty and finishes empty. I
> never use the iterator to delete, instead I use a different iterator
> to do the deletion. While the inserts/deletes are not concurrent,
> they are however interleaved with accesses to the traversing iterator.
>
> My question is if this is ok or not. I suspect that the iterator
> will become invalid in face of inserts deletes.
> My program however relies on this, one suggestion I heard was to
> have a second container with iterators where I keps iterators
> pointing to the "deleted" items. This is however not good for
> me since in the end everything will be empty anyway. The goal
> of the intermediate deletes is both correctness and efficiency.
> At any given time, the number of entries will be small (100-1000)
> but the whole of the data items that will go in and out of it
> reaches the millions, so I don't want to do this trick.
>
> Thanks, any help appreciated.
> Michael Ortega
This should be fine, as long as you make sure that you never delete
the element your iterator is actually pointing to. The STL sets and
maps
(as well as the list) are defined to have "robust" iterators. Note that
this is manifestly NOT true of vectors and deques, both of whose
iterators
can be invalidated be insertions and deletions.
--
Joe Gottman
joego...@worldnet.att.net
J. Kanze
Joe Gottman <joego...@worldnet.att.net> writes:
|> This should be fine, as long as you make sure that you never
delete
|> the element your iterator is actually pointing to. The STL sets and
|> maps
|> (as well as the list) are defined to have "robust" iterators.
Strange definition of "robust". IMHO, a minimally robust iterator must
support at least the following code:
for ( SomeIterator i = c.begin() ; i != c.end() ; ++ i )
{
if ( someCondition( *i ) )
c.erase( i ) ;
}
Given this definition (and as I say, it is a minimum), none of the
standard containers have robust iterators.
--
James Kanze +33 (0)1 39 23 84 71 mailto: ka...@gabi-soft.fr
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orientée objet --
-- Beratung in objektorientierter Datenverarbeitung
jka...@otelo.ibmmail.com
In article <3585BD86...@ix.netcom.com>,
"Paul D. DeRocco" <pder...@ix.netcom.com> wrote:
>
> J. Kanze wrote:
> >
> > IMHO, a minimally robust iterator must
> > support at least the following code:
> >
> > for ( SomeIterator i = c.begin() ; i != c.end() ; ++ i )
> > {
> > if ( someCondition( *i ) )
> > c.erase( i ) ;
> > }
> >
> > Given this definition (and as I say, it is a minimum), none of the
> > standard containers have robust iterators.
>
> serious implementation restrictions on the iterator, perhaps requiring
> that it be implemented as a numeric index into the container.
Not at all. In fact, implementing it as a numeric index into the
container
doesn't work; the element immediatly following the erased element is
deleted.
I know of several solutions. In my own containers, elements in a
container
were kept in nodes; the erase destructed the element, but left the node
in place until it wasn't needed. In an earlier version, the iterators
were notified of the deletion, and attempted to reposition themselves
so that the next ++ gave the desired results. Other libraries I've seen
consider elements as reference counted objects: their logical presence
in the container is a use, is counted as such, and is decremented by
erase. The fact that an iterator selects them is also a use, so the
object continues to exist until the iterator leaves them.
All of these solutions have measurable overhead. Whether the overhead
is
affordable depends on the application, but I generally find that it is
better to have the safe solution as the default, and the rapid one
available
only if needed.
> The following should work, won't it?
>
> for (SomeIterator i = c.begin(); i != c.end(); ) {
> if (someCondition(*i)) c.erase(i++);
> else ++i;
> }
It does. Now imagine that instead of a simple if, you have a more
complex
processing, with many branches, some of which delete, and some which
don't.
Do you really think that it is as maintainable as my solution. (Of
course,
you really shouldn't write code this way anyway.)
> That is, C++ promises to increment i before calling erase, if my
> understanding of sequence points is correct.
It is. Of course, even this doesn't work for vector.
More generally, I think I would prefer something like;
Container::iterator next ;
for ( Container::iterator i = c.begin() ; i != c.end() ; i = next )
{
next = i + 1 ;
// ...
}
(Which still gives unexpected results for vector.)
--
James Kanze +33 (0)1 39 23 84 71 mailto: ka...@gabi-soft.fr
+49 (0)69 66 45 33 10 mailto: jka...@otelo.ibmmail.com
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orientée objet --
-- Beratung in objektorientierter Datenverarbeitung
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/ Now offering spam-free web-based newsreading
R. Allen Conway
Excuse my ignorance ... but what unexpected results do you get for vectors?
...
jka...@otelo.ibmmail.com a écrit dans le message
<6m6dj8$vkg$1...@nnrp1.dejanews.com>...
...
>
> Container::iterator next ;
> for ( Container::iterator i = c.begin() ; i != c.end() ; i = next )
> {
> next = i + 1 ;
> // ...
> }
>
>(Which still gives unexpected results for vector.)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
John Potter
"R. Allen Conway" <raco...@atos-group.com> wrote:
: Excuse my ignorance ... but what unexpected results do you get for
vectors?
James is teasing us. If you erase the last item of the vector, the
iterator will go past the end (which moves) producing an infinite
loop.
John