Why do I need a const lambda when calling std::partition

Question

I have this function which uses std::partition to split a container into two based on a predicate.

template<class Container, class Predicate>
void split_partition(Container& src, Container& dest, Predicate p)
{

    auto ends = std::partition_copy(
        std::make_move_iterator( src.begin() ), std::make_move_iterator( src.end() ),
        src.begin(), std::back_inserter(dest), p
    ); 

    src.erase(ends.first, src.end());

}

I tried calling it with

split_partition(a, b, [](auto& t) {return t.i > 4; });

but it didn't even compile, now if use const it does work.

split_partition(a, b, [](const auto& t) {return t.i > 4; });

Why is that?

Edit:

std::vector<Thing> a = { {0, "foo"}, {1, "bar"}, {5, "what"}, {8, "yo"}, {2, ""} };
std::vector<Thing> b;

Answer 1

You are calling std::partition with a moved-from range:

std::make_move_iterator( src.begin() ), std::make_move_iterator( src.end() )

This means that the lambda you have is going to be invoked with some Object&& or const Object&&. const auto& can bind to it in either case. const auto& is universal in the sense that it can bind to any value category (lvalue, xvalue, prvalue).

For example:

#include <utility>

// Calls to opaque copy constructor should be visible in ASM.
// This would let us spot accidental copies/moves, if they took place.
struct S { S(const S&); };

void test(const S x, S y) {
    const auto& r0 = x;            // bind to lvalue const S
    const auto& r1 = std::move(x); // bind to xvalue const S
    const auto& r2 = y;            // bind to lvalue S
    const auto& r3 = std::move(y); // bind to xvalue S
}

This code compiles to

test(S, S):
        ret

This means that no constructor of S was called, const& simply binds to anything. Since you're using std::move_iterator (which is pointless for the purpose of comparison), your case is either r1 or r3.

auto& isn't quite so powerful: a non-const lvalue reference cannot bind to a const xvalue. This would be r3, and that's the case you're running into.

Otherwise [if the reference isn't bound to an lvalue of the same/to a compatible type], if the reference is an lvalue reference to a type that is not const-qualified or is volatile-qualified, the program is ill-formed.

- [dcl.init.ref] p5.2

Solution

Just accept const auto& in your lambda. It's more correct since you're just comparing elements without modifying them anyway.