how to iterator and delete elements in std::set

[zl2k]

hi, there

Here is what I want to do: I have a set of objects. I need to iterate
each of them to ask if it needs to be eliminated. If yes, I'll erase
it from the set. I don't know which needs to be erased before I touch
it.

std::set<Obj> objs;
....
for (auto obj_iterator = objs.begin(); obj_iterator != objs.end(); +
+obj_iterator){
if (obj_iterator.do_you_want_to_be_erased() == true){
objs.erase(*obj_iterator);
}
}

Now I have the trouble since the iterator is destroyed after the first
erase. What is the proper way to do the job? Thanks.

zl2k

 

[Andrea Crotti]

hi, there

Here is what I want to do: I have a set of objects. I need to iterate
each of them to ask if it needs to be eliminated. If yes, I'll erase
it from the set. I don't know which needs to be erased before I touch
it.

std::set<Obj> objs;
...
for (auto obj_iterator = objs.begin(); obj_iterator != objs.end(); +
+obj_iterator){
if (obj_iterator.do_you_want_to_be_erased() == true){
objs.erase(*obj_iterator);
}
}

Now I have the trouble since the iterator is destroyed after the first
erase. What is the proper way to do the job? Thanks.

zl2k

I might be wrong but maybe something like
for (auto obj_iterator = objs.begin(); obj_iterator != objs.end(); +
+obj_iterator){
if (obj_iterator.do_you_want_to_be_erased() == true){
Obj *tmp = *obj_iterator;
objs.erase(tmp);
}
}

could work?

 

[Spike]

I might be wrong but maybe something like
for (auto obj_iterator = objs.begin(); obj_iterator != objs.end(); +
+obj_iterator){
if (obj_iterator.do_you_want_to_be_erased() == true){
Obj *tmp = *obj_iterator;
objs.erase(tmp);
}
}

could work?

No, it doesn't work, it is *UB* because erasing the element invalidates
the iterator.
Actually it is the operation of removing an element from the container
that invalidates the iterator to it, not calling erase *on* the iterator.
The only way to get rid of the UB is to increment the iterator before
calling erase (i.e. using post-increment operator).

Besides objs is a std::set of Obj not of Obj*, so the expression "Obj
*tmp = *obj_iterator;" doesn't compile.

 

[Bogdan]

hi, there

Here is what I want to do: I have a set of objects. I need to iterate
each of them to ask if it needs to be eliminated. If yes, I'll erase
it from the set. I don't know which needs to be erased before I touch
it.

std::set<Obj> objs;
...
for (auto obj_iterator = objs.begin(); obj_iterator != objs.end(); +
+obj_iterator){
    if (obj_iterator.do_you_want_to_be_erased() == true){
       objs.erase(*obj_iterator);
    }

}

Now I have the trouble since the iterator is destroyed after the first
erase. What is the proper way to do the job? Thanks.

zl2k

It was some time ago a discussion on this list about this issue.
Indeed, it seems strange to erase the object to which the iterator
points to, but running your snippet exactly as is still produces the
right answer.

 

[Victor Bazarov]

std::set<Obj> objs;
...
for (auto obj_iterator = objs.begin(); obj_iterator != objs.end(){
if (obj_iterator->do_you_want_to_be_erased())
objs.erase(obj_iterator++);
else
++obj_iterator;
}

To expand the answer:

In the new Standard all 'erase' members return the iterator immediately
following the one being erased or 'end()', so with the compliant
compiler you could write

if (obj_iterator->do_...
obj_iterator = objs.erase(obj_iterator);
else
++obj_iterator;

(not sure if it's better in any way, though).

V

 

[Bogdan]

No it doesn't.  See else-thread for the right answer.

/Leigh

Maybe I am wrong, but erasing one element from the set doesn't mean
that the heap memory is freed ? That location though remains unused
till some other object is inserted into the set. So I really don't see
what's wrong with this snippet:

for (auto it = my_set.begin(); it != my_set.end();++it)
{
if (it->IsDeletable())
{
my_set.erase(*it);
}
}

as long as one is trying to iterate over the entire set without
inserting a new element, only erasing the existing ones.

 

[Michael Doubez]

I would use std::remove_if

http://www.sgi.com/tech/stl/remove_if.html

Would you ? Please, try it out before answering.

std::remove_if() copies the elements in the range such as removing the
unwanted value and returns the iterator to one past the last copied.

It doesn't work with std::set<> for two reason:
- the value are const and elements cannot be copied (in general)
- the internal structure is likely to be a RB-tree. copying the
values would make it a mess.