Why does std::remove_if create so many closures?

Question

In this example, a foo instance does nothing but print whether it's copy- or move-constructed.

#include <iostream>
#include <algorithm>
#include <vector>

struct foo {
    foo()=default;
    foo(foo &&) { std::cout << "move constructed\n"; }
    foo(const foo &) { std::cout << "copy constructed\n"; }
};

int main()
{
    foo x;
    std::vector<int> v; // empty

    std::remove_if(v.begin(), v.end(),
                   [x=std::move(x)](int i){ return false; });
}

This produces the following output:

move constructed
copy constructed
move constructed
move constructed
copy constructed
copy constructed

Questions:

• Why does std::remove_if create so many closures ?
• Even if multiple intermediate instances are necessary, one would expect they are all rvalues; so why are some of them copy-constructed ?

Compiler is gcc 8.1.1

Answer 1

If we take a look at the implementation of std::remove_if in gcc's libstdc++-v3 we notice that the predicate is passed down the call chain (by value, at times) a few steps before reaching the lowermost __find_if function (used by remove_if).

Let's count the moves and copies:

1. move constructed when the predicate (including the captured x) is sent by value, but as a non-lvalue, to std::remove_if entry point

2. copy constructed when passed on to the __gnu_cxx::__ops::__pred_iter(...) function, which in turn:

3. invokes the _GLIBCXX_MOVE macro, thus the move constructed,

4. which moves the predicate over to the _Iter_pred ctor which moves it (move constructed) into the _M_pred member.

5. The call from std::remove_if to std::__remove_if seems to be optimized, as the _Iter_pred is not an lvalue, I guess, but __remove_if in turn pass on the wrapped predicate, by value, to std::__find_if, for another copy constructed invocation.

6. std::__find_if, in turn, forwards the wrapped predicate, by value, to another __find_if overload, which is finally the sink of this call chain, and the final copy constructed.

It can be interesting to compare with e.g. clang's implementation of std::remove_if, as clang (6.0.1) do not produce this move-copy chain for OP's std::remove_if example. A quick glance shows that It seems as if clang use traits on the predicates type to make sure to pass the predicate as an lvalue reference.

Both clang and gcc produce the same move/copy chains for the contrived example that follows, which shows a similar chain to gcc's implementation:

#include <iostream>
#include <utility>

struct foo {
    foo() = default;
    foo(foo &&) { std::cout << "move constructed\n"; }
    foo(const foo &) { std::cout << "copy constructed\n"; }
};

template <typename Pred>
struct IterPred {
    Pred m_pred;
    explicit IterPred(Pred pred) : m_pred(std::move(pred)) {}
};

template <typename T>
inline IterPred<T> wrap_in_iterpred (T l) { 
    return IterPred<T>(std::move(l)); 
}

template <typename T>
void find_if_overload(T l) {
    (void)l;
}

template <typename T>
void find_if_entrypoint(T l) { 
    find_if_overload(l);
}

template <typename T>
void remove_if_entrypoint(T l) { 
    find_if_entrypoint(
        wrap_in_iterpred(l));
}

int main()
{
    foo x;
    remove_if_entrypoint([x=std::move(x)](int){ return false; });
}

Where both gcc (8.2.0) and clang (6.0.1) produces the following chain:

move constructed
copy constructed
move constructed
move constructed
copy constructed