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?

Aurelia

To be clear, would the side-effects alter the vector itself? That would invalidate the iterators being used in any event, so it's good to make sure of that first. I'd also be wary of any side-effects that could affect the values in the vector, since during execution of remove_if, the exact location of any given item in the vector is not guaranteed. – Drus

No, the side effects would not alter the vector. The side effects are actually writing some things to a file. – Aurelia

I think weather or not it does is moot. Do all of the side effects, then do the remove. – Fideicommissary

No, there's no such guarantee. – Eponymous

Answer: make processing not have side effects. Do those separate. – Fideicommissary

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));
}

Mllly

Yeah, I reread the question to doublecheck myself, then deleted the comment. Still: Why not simply do erase_if, followed by a for_each? – Fideicommissary

@MooingDuck: Because erase_if does not guarantee that it moves anything to the "empty" slots at the end of the range. stable_partition does. – Mllly

Answer 2

A bit late to the party, but here's my take:

While the order is not specified, it will involve jumping through hoops to implement an order different from first-to-last, due to the following:

• The complexity is specified to be "exactly std::distance(first, last) applications of the predicate", which requires visiting each element exactly once.
• The iterators are ForwardIterators, which means that they can only be incremented.
• [C++17 and above] To prevent parallel processing, one can use the version that accepts an execution policy, and pass std::execution::seq.

Given the above, I believe that a (non-parallel) implementation that follows a different order will be convoluted and have no advantages over the straightforward case.

Source: https://en.cppreference.com/w/cpp/algorithm/remove

Mathildamathilde

Answer 3

They should be processed in order, but it is not guaranteed.

std::remove_if() moves "removed" items to the end of the container, they are not actually removed from the container until erase() is called. Both operations will potentially invalidate existing iterators in a std::vector.

Langelo

Where in the standard does it guarantee in-order processing? – Mllly

@NicolBolas: I did not say it was guaranteed to be processed in order, I said it should be processed in order (see the "Possible implementation" on cppreference.com). However, the standard does say this for remove_if() in § 25.3.8: "Complexity: Exactly last - first applications of the corresponding predicate." So it can't pass an item to the predicate more than once (like a sort can). But I guess that does not prevent the algorithm from working last-to-first instead of first-to-last, though the latter is more likely. – Langelo