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?

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. — ShadowRanger, Aug 08 '16 at 22:55
No, the side effects would not alter the vector. The side effects are actually writing some things to a file. — Solaraeus, Aug 08 '16 at 22:57
I think weather or not it does is moot. Do all of the side effects, then do the remove. — Mooing Duck, Aug 08 '16 at 23:00
Answer: make processing not have side effects. Do those separate. — Mooing Duck, Aug 08 '16 at 23:15

Nicol Bolas · Accepted Answer · 2021-12-07T20:29:44.000

11

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

edited Dec 07 '21 at 20:29

answered Aug 08 '16 at 23:00

Nicol Bolas

449,505
63
781
982

Yeah, I reread the question to doublecheck myself, then deleted the comment. Still: Why not simply do `erase_if`, followed by a `for_each`? – Mooing Duck Aug 08 '16 at 23:05
1

@MooingDuck: Because `erase_if` does not guarantee that it *moves* anything to the "empty" slots at the end of the range. `stable_partition` does. – Nicol Bolas Aug 08 '16 at 23:06

score 0 · Answer 2 · answered Dec 07 '22 at 18:39

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

Remy Lebeau · Answer 3 · 2016-08-08T23:57:43.107

-2

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.

edited Aug 08 '16 at 23:57

answered Aug 08 '16 at 23:02

Remy Lebeau

555,201
31
458
770

5

Where in the standard does it guarantee in-order processing? – Nicol Bolas Aug 08 '16 at 23:03
@DafangCao: yeah. My bad. Forgot that `erase` doesn't guarantee anything in the second "partition", which allows it to use a simpler algorithm. – Mooing Duck Aug 08 '16 at 23:42
@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](http://en.cppreference.com/w/cpp/algorithm/remove)). 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. – Remy Lebeau Aug 08 '16 at 23:57

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

3 Answers3