CODEWITHSUNDEEP
c++vectoreraseerase-remove-idiom
OGH
OGH

Reputation: 550

Erasing elements in a vector

So I have a vector of unsigned ints (vector<unsigned int> is called vector1). I have another vector of a struct I created (vector<struct> is called vector2). vector<int> holds an integer that is the index of the vector<struct>. For example, let's say that vector<int = {5, 17, 18, 19}. That means vector2.at(5) == vector2.at(vector1.at(0)).

In the struct, I have a bool variable called var. In most cases, var is false. I want to delete all of the elements in vector1 that have var = true.

What I did was:

for (unsigned int i = 0; i < vector1.size(); i++)
{
   if (vector2.at(vector1.at(i)).var)
    vector1.erase(vector.begin() + i);
}

The only problem with this is that it does not delete all of the true elements. I have run the for loop multiple times for all values to be delete. Is this the correct behavior? If it is not, where did I go wrong?

Upvotes: 0

Views: 377

Answers (3)

Christian Rau
Christian Rau

Reputation: 45948

You are erasing elements in the vector while at the same time iterating over it. So when erasing an element, you always jump over the next element, since you increase i while having just shortened the vector at i (it would be even worse, had you used a proper iterator loop instead of an index loop). The best way to do this would be to seperate both opretions, first "marking" (or rather reordering) the elements for removal and then erasing them from the vector.

This is in practice best done using the erase-remove idiom (vector.erarse(std::remove(...), vector.end())), which first uses std::remove(_if) to reorganize the data with the non-removed elements at the beginning and returns the new end of the range, which can then be used to really delete those removed elements from the range (effectively just shortening the whole vector), using std::vector::erase. Using a C++11 lambda, the removal condition can be expressed quite easily:

vector1.erase(std::remove_if(                        //erase range starting here
                  vector1.begin(), vector1.end(),    //iterate over whole vector
                  [&vector2](unsigned int i)         //call this for each element
                      { return vector2.at(i).var; }),  //return true to remove
              vector1.end());                        //erase up to old end

EDIT: And by the way, as always be sure if you really need std::vector::at instead of just [] and keep in mind the implications of both (in particular the overhead of the former and "maybe insecurity" of the latter).

Upvotes: 1

ogzd
ogzd

Reputation: 5692

You can keep a temporary vector, copy of vector1 and iterate over it in the for loop and delete from vector1.

Upvotes: 1

Tony The Lion
Tony The Lion

Reputation: 63200

You have to use the erase-remove idiom to delete elements from a vector.

v.erase(std::remove(v.begin(), v.end(), value), v.begin);

std::remove moves the elements to the end of the vector and erase will erase the element from the vector.

Upvotes: 3

Related Questions