set<>::erase(iterator) question

H

Harald Grossauer

Usually STL containers have something like "iterator
container<>::erase(iterator)" which erases the element the iterator points
to and returns another valid iterator. Set does not have this, set::erase()
returns void and "invalidates" the iterator.

Now I have the following code:

while(!some_set.empty()) {
for(it = some_set.begin(); it != some_set.end(); it++)
{
...
if (something == true) some_set.erase(it);
...
}
}

And it always worked (using GCC3.2). Now running the same program using the
same test data on another machine (GCC3.3) it is caught in an endless loop.
What could be going on here?
 
W

WW

Harald said:
Usually STL containers have something like "iterator
container<>::erase(iterator)" which erases the element the iterator
points to and returns another valid iterator. Set does not have this,
set::erase() returns void and "invalidates" the iterator.
[SNIP]

Get Effective STL from Scott Meyers.

// This is not necessary: while(!some_set.empty()) {
for(it = some_set.begin(); it != some_set.end(); ) // Change
{
...
if (something == true) some_set.erase(it++); // Change
else ++it; // Change
...
}

You need to get the valid iterator *before* the erase runs.
 
R

Ron Natalie

Harald Grossauer said:
Usually STL containers have something like "iterator
container<>::erase(iterator)" which erases the element the iterator points
to and returns another valid iterator.

That's true for sequences.
Set does not have this, set::erase() returns void and "invalidates" the iterator.

That's the way associative containers are, unfortuantely. However, the nice thing
is that they only invalidate the erased iterator.
for(it = some_set.begin(); it != some_set.end(); it++)
{
...
if (something == true) some_set.erase(it);
...
}
You have two chocies:
1. remember the next iterator somewhere
2. use post increment to accomplish the same thing

next_it = it+1;
if(something == true) some_set.erase(it);
it = next_it;

or
if(something == true) some_set.erase(it++);
else ++it;
 
K

keanu

WW wrote in said:
Harald said:
Usually STL containers have something like "iterator
container<>::erase(iterator)" which erases the element the iterator
points to and returns another valid iterator. Set does not have this,
set::erase() returns void and "invalidates" the iterator.
[SNIP]

Get Effective STL from Scott Meyers.

// This is not necessary: while(!some_set.empty()) {
for(it = some_set.begin(); it != some_set.end(); ) // Change
{
...
if (something == true) some_set.erase(it++); // Change
else ++it; // Change
...
}

You need to get the valid iterator *before* the erase runs.

if i'm not mistaken erase returns the next valid iterator, so:
for(it = some_set.begin(); it != some_set.end(); ) // Change
{
...
if (something == true)
it = some_set.erase(it++);
...

should do the trick?
 
R

Ron Natalie

keanu said:
if i'm not mistaken erase returns the next valid iterator, so:

Yoiu are mistaken. Did you even read the original post? The erase on
associative containers do not, unfortunately, return anything.
if (something == true)
it = some_set.erase(it++);
...

That won't even work on containers where erase DOES return something. It's
undefined behavior in that case. You can do on sequences

if(something)
it = some_sequence.erase(it);
else ++it;

or on associative containers
if(something)
some_set(it++);
else ++it;
 
K

Kevin Goodsell

keanu said:
if i'm not mistaken erase returns the next valid iterator, so:

Not for associative containers. That's sort of the point of the thread.

-Kevin
 
K

Kevin Goodsell

Ron said:
That won't even work on containers where erase DOES return something. It's
undefined behavior in that case.

Why is it undefined behavior? The increment is 'finished' before the
function call (sequence point immediately before a function call) and
the assignment occurs after, right?

-Kevin
 
K

keanu

That won't even work on containers where erase DOES return something.
It's
undefined behavior in that case. You can do on sequences

if(something)
it = some_sequence.erase(it);
else ++it;

this is what i meant, the ++ was a left over from the copy paste + no sleep

for some reason i thought erase returns the next iterator for every
container
 
R

Ron Natalie

Why is it undefined behavior? The increment is 'finished' before the
function call (sequence point immediately before a function call) and
the assignment occurs after, right?

Yeah, I guess you're right. I was thinking that the side effect could be delayed
but there is an inherent sequence point after the function args are evaluated and
again on return.
 
H

Harald Grossauer

Ron Natalie wrote:

You have two chocies:
1. remember the next iterator somewhere
2. use post increment to accomplish the same thing

next_it = it+1;
if(something == true) some_set.erase(it);
it = next_it;

That's how I did it then. I just thought there might be a "nicer" version
without introducing another "dummy iterator".
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,905
Latest member
Kristy_Poole

Latest Threads

Top