c++ iterators double loops

Question

I'm trying to do something like the following:

myvec is a vector of Couple objects (formed each with an EntityA and an EntityB). I'm trying to remove the duplicate couples.. Anyway sometimes the following code crashes with an out of bound it2. The condition is fine, the iterators seems not

if(myvec.size()>1)
for(vector<Couple>::iterator it1 = myvec.begin(); it1+1 !=myvec.end();){
    for(vector<Couple>::iterator it2 = it1+1; it2 !=myvec.end();){
        if((it1->EntityA!=it2->EntityA&&it1->EntityA!=it2->EntityB)||
            (it1->EntityB!=it2->EntityA&&it1->EntityB!=it2->EntityB)){
                it2++;
        }
        else{
            myvec.erase(it2);
        }
    }
    it1++;
}

Any solution/alternative?

Why not just use `std::unique`? Or if they aren't necessarily consecutive, `std::remove_if`? — Chad, Jul 12 '12 at 20:47
when you erase an iterator it's no longer valid to say it2++ try `erase(it2++)`. — andre, Jul 12 '12 at 20:48

score 3 · Answer 1 · edited May 23 '17 at 12:27

Use the existing library functions whenever possible. You will need to provide a binary predicate function, or provide an operator< and operator== for your Couples object.

std::sort(myvec.begin(), myvec.end());
myvec.erase(std::unique(myvec.begin(), myvec.end()), myvec.end());

However, it may be better for you to have a container that will automatically avoid duplicates like std::set. This is a related question, with an excellent answer.

score 2 · Accepted Answer · answered Jul 12 '12 at 20:49

if(myvec.size()>1)
for(vector<Couple>::iterator it1 = myvec.begin(); it1+1 !=myvec.end();){
    for(vector<Couple>::iterator it2 = it1+1; it2 !=myvec.end();){
        if((it1->EntityA!=it2->EntityA&&it1->EntityA!=it2->EntityB)||
            (it1->EntityB!=it2->EntityA&&it1->EntityB!=it2->EntityB)){
                it2++;
        }
        else{
            it2 = myvec.erase(it2);
        }
    }
    it1++;
}

Return value A random access iterator pointing to the new location of the element that followed the last element erased by the function call, which is the vector end if the operation erased the last element in the sequence.

http://cplusplus.com/reference/stl/vector/erase/

score 1 · Answer 3 · answered Jul 12 '12 at 20:52

It is not a good idea to modify the vector (to move around components and changing the vectors length in this case) you are iterating over. That is the problem with your code. When you remove one component in the middle of the vector, the ones at the end are shifted to the left, so the end of the vector moves. That messes up your break condition.

Instead of modifying your existing vector, you could create a new vector empty vector, and add to it every component you want to keep. That could consume more memory (if your vector is large, that might be of interest), but it should save you much cpu-time, because removing a component in the middle of the vector is not a cheap operation. All components right of it have to be moved, again and again, one position at a time (there exist containers in stl that don't have this problem). So building a new vector and adding to it should be better altogether.

c++ iterators double loops

3 Answers3