How to safely erase elements in a std::vector

Question

I'm getting segfault errors when I use the erase() method in a class vector container.

I'm comparing two vectors and, so I want to remove from one of them the elements that are not present in the another. To do so, I'm using iterators and erase() as follow:

#include <vector>

int main () {

std::vector<int> vector1 {6,7,5,44,3,10,9,17,1};
std::vector<int> vector2 {1,2,3,5,8};

for (std::vector<int>::iterator it (vector2.begin()); it != vector2.end(); ++it) {
    bool equal (false);
    for (std::vector<int>::iterator jt (vector1.begin()); jt != vector1.end(); ++jt) {
        if (*it == *jt) {
            equal = true;
            break       ;
        }
    }
    if (!equal) {
        vector2.erase(it);
    }
}

return 0;
}

What is causing the segfault is the deletion of the last element in vector2 (8), because erase() cannot succesfully move the iterator from the previous end() position (no longer existant) to a new one.

How can this be prevented? I'm aware that unordered_set could be a proper container for this operation, but here I'm interested in vector.

The standard way to do this is called the [erase-remove idiom](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom) — NathanOliver, Aug 18 '17 at 18:37
If you really want to do it the way you are trying to do it, I would iterate through vector1 in the outer loop, and vector 2 in the inner loop. That way you are not deleting from the vector in the outer loop and disturbing the validity of the iterators. — ttemple, Aug 18 '17 at 18:44

Edgar Rokjān · Accepted Answer · 2017-08-18T18:49:04.197

You can't remove like:

if (!equal) {
    vector2.erase(it);
}

erase operation invalidates it, so the next ++it is an error.

Instead of it, you might rewrite the outer cycle as:

for (std::vector<int>::iterator it (vector2.begin()); it != vector2.end();)

and change it inside the for loop:

if (!equal) {
    it = vector2.erase(it);
} else {
    ++it;
}

DEMO

Note, that you might use remove-erase idiom as well:

vector2.erase(
    std::remove_if(std::begin(vector2), std::end(vector2), [&vector1](const auto& e) {
        return std::find(std::cbegin(vector1), std::cend(vector1), e) == std::end(vector1);
    }),
    std::end(vector2)
);

which is a standard way to do the things like this.

Thank you! this solves the problem, and I understand better it now — elcortegano, Aug 18 '17 at 18:43

score 3 · Answer 2 · answered Aug 18 '17 at 18:41

The problem, as others have pointed out, is that erasing invalidates your iterator. But there's a more general issue here in using raw loops to do this sort of manipulation. It requires a lot of boilerplate code and is error prone. You can use the standard algorithms to avoid these pitfalls.

std::vector<int> result;
std::sort(vector1.begin(), vector1.end());
std::sort(vector2.begin(), vector2.end());
std::set_difference(
  vector2.begin(),
  vector2.end(),
  vector1.begin(),
  vector1.end(),
  std::back_inserter(result));

score 2 · Answer 3 · answered Aug 18 '17 at 18:36

The problem is that your iterators are invalidated after erasing. Change this:

vector2.erase(it);

to this:

it = vector2.erase(it);

And it would be a step toward solving the problem. Check the docs, and you'd see that the return value is the next valid iterator.

How to safely erase elements in a std::vector

3 Answers3