CODEWITHSUNDEEP
c++vectorerase
user1544128
user1544128

Reputation: 582

Does vector::erase() change positions?

Here is my question, I have a vector of double and I need eliminate some of them under a certain condition. Here is a code example:

 vector <double> appo;
 for(int i=0;i<appo.size();i++){
       for(int j=i+1;j<appo.size();j++){
         if( condition(appo[i],appo[j]) ){
           appo.erase(appo.begin()+j);
           j--;
         }
       }
    }

Since after the erase() my size decrease by 1 and all the elements got left shifted by left, is correct to decrease j?

Ok I decide to don't use the removeif because it's a small program and I don't care right now about performance, but I got segmentation fault. Here is the code:

vector <double> *point;
for(int i=0;i<point->size();i+=3){
     for(int j=i+3;j<point->size();j+=3){
       if(distance((*point)[i],(*point)[i+1],(*point)[i+2],(*point)[j],(*point)[j+1],(*point)[j+2]) < treshold){
         point->erase(point->begin()+j,point->begin()+j*3);
         j-=3;
       }
     }
  }

point is a vector of coordinates so something like (x1,y1,z1,x2,y2,z3,...,xn,yn,zn). Any idea?

Upvotes: 2

Views: 3284

Answers (1)

Steve Jessop
Steve Jessop

Reputation: 279245

It is correct to decrement j, because after erasing the element at index j, the element that previously was at j+1 is now at j, so you want to repeat the loop again with the same value of j. Decrementing it has that effect, since the loop itself increments it.

You could also consider using an iterator instead of an index:

vector<double>::iterator j = appo.begin() + i + 1;
while (j != appo.end()) {
    if (condition(appo[i], *j)) {
        j = appo.erase(j);
    } else {
        ++j;
    }
}

Having done that, you could use an iterator for i as well.

As "eq-" says in a comment, there's a standard algorithm that can help you. Take your pick whether you prefer it to the loop in terms of usability, but it's generally more efficient because repeatedly calling "erase" shuffles each element along one step at a time, whereas remove_if keeps track of a "read position" and a "write position", so it only copies each element at most once.

appo.erase(
    appo.remove_if(
        appo.begin() + i + 1,
        appo.end(),
        ShouldRemove(appo[i])
    ),
    appo.end()
);

In C++03 you have to define ShouldRemove similar to:

struct ShouldRemove {
    double lhs;
    ShouldRemove(double d) : lhs(d) {}
    bool operator()(double rhs) {
        return condition(lhs, rhs);
    }
};

In C++11 you can use a lambda instead of ShouldRemove:

appo.erase(
    appo.remove_if(
        appo.begin() + i + 1,
        appo.end(),
        [&](double d) { return condition(appo[i], d); }
    ),
    appo.end()
);

You also have some options using std::bind1st or boost::bind (in C++03) or std::bind (in C++11), but those are quite tricky to understand properly.

Upvotes: 6

Related Questions