Erase some of a vector's elements in a for-each loop without iterating the whole vector

Question

I have a vector and I am searching for an element in it while iterating over the vector with a for-each loop. If I find any invalid elements during the search, I would like to remove them from the vector.

Basically, I want to do something like this:

for (auto el : vec) {
    if (el == whatImLookingFor) {
        return el;
    } else if (isInvalid(el)) {
        vec.erase(el);
    }
}

I looked at some other questions like this and this, but both recommend using std::remove_if. That will iterate over the whole vector and remove all invalid elements, instead of iterating only until I find the element I'm looking for, and ignoring any elements after that.

What would be a good way to do this?

Answer 1

You should still use std::remove_if, just call std::find beforehand.

auto el = std::find(vec.begin(), vec.end(), whatImLookingFor);
auto p = std::remove_if(vec.begin(), el, isInvalid);

// returns the iterator, not the element itself.
// if the element is not found, el will be vec.end()
return vec.erase(p, el);

This will usually be more efficient than removing one element at a time.

Answer 2

I was curious about the performance of this, so I ran a quick naive benchmark comparing Benjamin's find then partial clean and hnefatl's for-loop. Benjamin's is indeed faster: 113x faster. Impressive.

But I was curious where most of the computation was going, as it was greater than the sum of remove_if and find, which are the only functions that actually iterate through the array. As it turns out, however, the vec.erase line in his code is actually pretty slow. This is because in remove_if he is cleaning the area from the start to the location of the found value, which results in a gap in the middle of the array from the invalid values. vec.erase must then copy the remaining values to fill the gap and finally resize the array.

I ran a third test with a full-sized remove_if/vec.erase followed by a find, so the gap happens at the end and no copy is necessary, just truncation. It turned out to be about 15% faster and leaves the whole vector clean. Note that this assumes that testing for validity is cheap. If it's more than a few simple comparisons, Benjamin's answer will win hands-down, as pointed out by Chris in the comments.

The code

auto p = std::remove_if(vec.begin(), vec.end(), isInvalid);
vec.erase(p, vec.end());
return std::find(vec.begin(), vec.end(), whatImLookingFor);

The Benchmark