Search code examples
c++vectoriteratorerase

vector::erase() not working as expected

  for(it1=prime.begin();it1<prime.end();it1++){
        for(it2=it1+1;it2<prime.end();it2++){

            if(*it2%*it1==0){

                prime.erase(it2);
            }

        }
        if(*it1<1000)
        prime.erase(it1);
    }

In above code snippet i am removing numbers that are multiples of number already existing in prime vector 2 to 9999(sieve of Eratosthenes).also I only what numbers that are more then 1000, but somehow these are not getting erased.

can someone please explain me why?

Thanks in advance.

Solution

  • Calling erase() invalidates the iterator. You should use the return value, which is an iterator to the value after the element that was deleted, e.g.

    it2 = prime.erase(it2);

    But if you make this change (which you must!), you need to remove ++it2 from the for loop. You also need to make both changes for it1. Here is some untested code:

    for (it1 = prime.begin(); it1 < prime.end();) {
    for(it2 = it1 + 1; it2 < prime.end();) {
        if (*it2 % *it1 == 0)
            it2 = prime.erase(it2);
        else
            ++it2;
    }
    if (*it1 < 1000)
        it1 = prime.erase(it1);
    else
        ++it1;
}

    Note that erasing it2 will not invalidate it1, because it occurs strictly before it2 due to the it2 = it1 + 1. So you don't need to concern yourself with that interference.