Why Is Std::Function Not Equality Comparable

Why is std::function not equality comparable?

Why is std::function not equality comparable?

std::function is a wrapper for arbitrary callable types, so in order to implement equality comparison at all, you'd have to require that all callable types be equality-comparible, placing a burden on anyone implementing a function object. Even then, you'd get a narrow concept of equality, as equivalent functions would compare unequal if (for example) they were constructed by binding arguments in a different order. I believe it's impossible to test for equivalence in the general case.

What is the "possible hole in the type system?"

I would guess this means it's easier to delete the operators, and know for certain that using them will never give valid code, than to prove there's no possibility of unwanted implicit conversions occurring in some previously undiscovered corner case.

How is it different from std::shared_ptr?

std::shared_ptr has well-defined equality semantics; two pointers are equal if and only if they are either both empty, or both non-empty and pointing to the same object.

Why does std::equality_comparable not work for std::vector

A concepts only checks that the declaration is well formed, it doesn't check the definition.

The comparison operators for std::vector are not SFINAE friendly, i.e. they are unconditionally declared, meaning that operator==(vector<T>, vector<T>) always exists, even if operator==(T, T) doesn't exists. That's why equality_comparable<std::vector<T>> is always satisfied and you get an error on v == v inside the function.

For it to work properly the vector comparison operators should be constrained, i.e.:

template< class T, class Alloc >
    requires std::equality_comparable<T>
constexpr ret_type operator==( const std::vector<T,Alloc>& lhs,
                                       const std::vector<T,Alloc>& rhs );

Comparing std::functions for equality?

operator== for std::function compares a std::function with a null pointer, as far as I can tell the standard does not provide any details as to why.

Although, this boost FAQ entry, Why can't I compare boost::function objects with operator== or operator!=? provides a rationale and as far as I can tell should be applicable to std::function as well. Quoting the FAQ:

Comparison between boost::function objects cannot be implemented "well", and therefore will not be implemented. [...]

it then outlines requested solutions similar to Preet's and goes on to say:

The problem occurs when the type of the function objects stored by both f and g doesn't have an operator==[...]

and explains why this has to has to be dealt with in either the assignment operator or constructor and then goes on to say:

All of these problems translate into failures in the boost::function constructors or assignment operator, even if the user never invokes operator==. We can't do that to users.

Update

Found a standards rationale in Accessing the target of a tr1::function object, which is pretty old but is consistent with the boost FAQ and says:

operator== is unimplementable for tr1::function within the C++ language, because we do not have a reliable way to detect if a given type T is Equality Comparable without user assistance.

concept std::equality_comparable_with not working for user-defined equality operator

Equality means more than just operator== is valid and returns true. And the standard library concepts require this.

equality_comparable defines symmetric comparison (equality comparing between the same type). In terms of syntax, this means that t1==t2 has to be a boolean. But there are also semantic requirements that types are expected to provide.

One could define equality between t1 and t2 as follows. If they are equal, then for any (pure) function f which acts on a T, f(t1) == f(t2).

But for equality between types, this definition is conceptually insufficient. After all, a function f which takes a T may not take a U.

To deal with this fact, C++20 defines equality between T and U in terms of a hypothetical third type C. C could be T, U, or some actual other type. But the main thing C++20 asymmetric equality requires is that there is a type C (which allows symmetric equality testing) to which references to T and U can be implicitly converted. This is the common_reference type.

This allows the standard to define asymmetric equality in terms of C. That is, for any function f which takes a C, if t == u, then f(t) == f(u).

Consider string and string_view. A string is implicitly convertible to a string_view. As such, when doing asymmetric comparisons, the comparison conceptually acts as if any string were converted to a string_view before doing the comparison. That is, string_view acts as the type C.

This provision is here specifically to stop code of the form you're trying to write. Conceptually, your struct A has no equivalence relationship with string_view. A function that takes a string_view couldn't take an A of equal value at all, even if string_view were the common reference between them.

Why isn't std::variant allowed to equal compare with one of its alternative types?

It is an arbitrary decision by the standards committee.

Ok, not quite arbitrary. The point is you have a scale^* of strictness of comparison, with points such as:

• Most-strict: Only variants can equal each other, and they need to match both in the sequence-of-alternatives (i.e. the type), the actual alternative (the index, really, since you can have multiple identical-type alternatives) and in value.
• Less-Strict: Equality of both the variant alternative, as a type and the value, but not of the sequence-of-alternatives, nor the index within that sequence (so the same value within two distinct alternatives of the same type would be equal).
• Most-relaxed: Equality of the value in the active alternative, with implicit conversion of one of the elements if relevant.

These are all valid choices. the C++ committee made the decision based on all sorts of extrinsic criteria. Try looking up the std::variant proposal, as perhaps it says what these criteria are.

_{(*) - A lattice actually.}

Why does std::optional have a special equality operator for operand of the type std::nullopt

You are looking at the C++20 draft. Drafts no later than N4820 had all the equality operators. They were later removed [likely] because of the introduction of rewritten candidates.

How to work around the fact that std::function has no operator==?

As others have said, you don't need comparison of std::functions for this. Using standard C++ facilities this can be efficiently (with linear complexity) implemented in two lines:

bool Test(TesterSet_t &candidates, int foo)
{
    candidates.erase(std::remove_if(candidates.begin(), candidates.end(),
        [foo](Tester_t& f){ return !f(foo); }), candidates.end());
    return !candidates.empty();
}

Why does std::sort work when the comparison function uses greater-than ( ), but not greater-than-or-equal ( =)?

This is just how it is required to work. You need strict weak ordering.

For the rationale, I believe that the sufficient explanation is that this enables you to determine whether those elements are equal (useful for e.g. std::sets). <= or >= can't do that.

<= or >= can also do that, but it seems like it was just decided to use < instead of any other relation. With this decision in mind, standard library facilities are implemented and they heavily rely on it.

Will std::sort always compare equal values?

Will std::sort always compare equal values or sometimes it can skip comparing them and therefore duplicate values will not be found?

Yes, some equal value elements will always be compared if duplicates do exist.

Let us assume the opposite: initial array of elements {e} for sorting contains a subset of elements having the same value and a valid sorting algorithm does not call comparison operator < for any pair of the elements from the subset.

Then we construct same sized array of tuples {e,k}, with the first tuple value from the initial array and arbitrary selected second tuple value k, and apply the same sorting algorithm using the lexicographic comparison operator for the tuples. The order of tuples after sorting can deviate from the order of sorted elements {e} only for same value elements, where in the case of array of tuples it will depend on second tuple value k.

Since we assumed that the sorting algorithm does not compare any pair of same value elements, then it will not compare the tuples with the same first tuple value, so the algorithm will be unable to sort them properly. This contradicts our assumptions and proves that some equal value elements (if they exist in the array) will always be compared during sorting.

---

Related Topics