Delete items from set of pointers in nested for loop

Question

i have the following problem ahead of me: I have a set containing pointers to vertices. If two vertices are similar, i want to delete one of them out of the set.

I do this check via nested for loop:

set<Vertex*> vertexSet;
set<Vertex*> vertexSet2;

for(...) { // outer loop

    ...  //vertexSet gets filled externally    
    vertexSet2 = vertexSet; //copying vertexSet, to not delete from it, while iterating over it.

    for(it = vertexSet.begin(); it != vertexSet.end(); ++it) {
        for(jt = next(it); jt != vertexSet.end(); ++jt) {
            if((*it)->value == (*jt)->value) { //check if similar/equal
                vertexSet2.erase(jt); //erase the similar vertex out of the second set
            }
        }
    }

vertexSet2.clear();
vertexSet.clear(); //clear both sets for next outer loop iteration

} //end of outer loop

This works just fine for the first iteration of the outerloop. The problem is, when the program reaches the step of copying the content of vertexSet to vertexSet2 the second time, it crashes.

I don't get that, because i'm clearing both sets and they both have size() == 0 afterwards.

Any ideas what the problem could be?

EDIT: I now changed my code accordingly. I am using only 1 set and changed the point where i increment my jt iterator.

set<Vertex*> vertexSet;

for(...) { // outer loop

    ...  //vertexSet gets filled externally 

    for(it = vertexSet.begin(); it != vertexSet.end(); ++it) {
        for(jt = next(it); jt != vertexSet.end();) { //REMOVED INCREMENT OF JT HERE

            set<Vertex*>::iterator temp = jt++; //AND MOVED IT HERE
            if((*it)->value == (*temp)->value) { //check if similar/equal
                vertexSet.erase(temp); //erase the similar vertex out of the second set
            }
        }
    }

vertexSet.clear(); //clear set

} //end of outer loop

[Deleting elements from STL set while iterating](http://stackoverflow.com/q/2874441/3953764) — Piotr Skotnicki, Sep 01 '15 at 08:47
And for further reading: [Iterator invalidation rules](http://stackoverflow.com/q/6438086/3953764) — Piotr Skotnicki, Sep 01 '15 at 08:47
I implemented the solution based on Alex' solution and Piotr's links. I looked at them yesterday already, but was confused what to do with the outer iterator it.. — stainless, Sep 01 '15 at 09:09
@stainless note that now you are skipping one item. You start from `jt = next (it)` but then you increase `jt` once again before the compare. Use `temp` inside the compare instead of `jt` — Alex Lop., Sep 01 '15 at 09:13
Oh yeah, this is just due the simplification of my code, i actually get all the data for the comparison before introducing the temp iterator :) But thanks for your answer anyway, i will fix it in the code. — stainless, Sep 01 '15 at 11:15

score 1 · Accepted Answer · answered Sep 01 '15 at 08:52

1

The problem is in the inner loop

vertexSet2.erase(jt);

This makes jt invalid. You need to save jt to some temp iterator, then increase jt before the erase command.

temp = jt++;
vertexSet2.erase(temp);

answered Sep 01 '15 at 08:52

Alex Lop.

6,810
1
26
45

You should see those links too. – LogicStuff Sep 01 '15 at 08:58
Well he wasn't wrong. This is pretty much what the first link said. – stainless Sep 01 '15 at 09:02
@LogicStuff Why? Please clarify. – Alex Lop. Sep 01 '15 at 09:17
I thought this was about `std::vector`, sorry I should read properly. – LogicStuff Sep 01 '15 at 09:21

Delete items from set of pointers in nested for loop

1 Answers1