Is std::remove_if guaranteed to call predicate in order?

Question

Will std::remove_if always call the predicate on each element in order (according to the iterator's order) or could it be called out of order?

Here is a toy example of what I would like to do:

void processVector(std::vector<int> values)
{
    values.erase(std::remove_if(values.begin(), values.end(), [](int v)
    {
        if (v % 2 == 0)
        {
            std::cout << v << "\n";
            return true;
        }
        return false;
    }));
}

I need to process and remove all elements of a vector that meet certain criteria, and erase + remove_if seems perfect for that. However, the processing I will do has side effects, and I need to make sure that processing happens in order (in the toy example, suppose that I want to print the values in the order they appear in the original vector).

Is it safe to assume that my predicate will be called on each item in order?

I assume that C++17's execution policies would disambiguate this, but since C++17 isn't out yet that obviously doesn't help me.

Edit: Also, is this a good idea? Or is there a better way to accomplish this?

Answer 1

The standard makes no guarantees on the order of calling the predicate.

What you ought to use is stable_partition. You partition the sequence based on your predicate. Then you can walk the partitioned sequence to perform whatever "side effect" you wanted to do, since stable_partition ensures the relative order of both sets of data. Then you can erase the elements from the vector.

stable_partition has to be used here because erase_if leaves the contents of the "erased" elements undefined.

In code:

void processVector(std::vector<int> &values)
{
    auto it = std::stable_partition(begin(values), end(values), [](int v) {return v % 2 != 0;});

    std::for_each(it, end(values), [](int v) {std::cout << v << "\n";});

    values.erase(it, end(values));
}