A question about the argument types to the comp predicate in std::lower_bound

Question

Reference: std::lower_bound

Excerpt:

comp - binary predicate which returns ​true if the first argument is less than (i.e. is ordered before) the second.

The signature of the predicate function should be equivalent to the following:

bool pred(const Type1 &a, const Type2 &b);

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)).

What I would like to clarify in the above excerpt with respect to the type mandate is the following:

nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)

I presume Type1& is not allowed as that could potentially allow the predicate to modify the objects passed in; but why is Type1 not allowed? Is it only due to optimization, taking cues from the precondition that Type1 is allowed if a move is equivalent to copy? Or is there more to it than that?

Answer 1

Type1& is not allowed because as the description says, the function must accepts values of all value categories. A non-const lvalue reference can only bind to lvalues, not to xvalues or prvalues. For example:

void take(int&);
void take_const(const int&);
void take_value(int);

int main() {
    int x;
    take(x); // OK, can accept lvalues
    take(std::move(x)); // error, lvalue reference cannot bind to xvalues
    take(0); // error, lvalue reference cannot bind to prvalues

    take_const(x); // OK
    take_const(std::move(x)); // OK
    take_const(0); // OK, performs temporary materialization

    take_value(x); // OK
    take_value(std::move(x)); // OK, move is equivalent to copy for int
    take_value(0); // OK
}

Type1 is allowed because it satisifes the requirement; you can pass any value category to it. Also, if an lvalue is passed to it, then it performs a copy, which makes it easy to ensure that it doesn't modify the original.

Answer 2

but why is Type1 not allowed? Is it only due to optimization, taking cues from the precondition that Type1 is allowed if a move is equivalent to copy? Or is there more to it than that?

It is the same reason as with the non-const lvalue, it is not allowed to modify the original. The iterator (see std::move_iterator) could return an rvalue reference, which would then be consumed if Type1 has a move constructor that does something different than its copy constructor.

This could lead to all compared elements ending up empty. Not good! :-)