Why is std::function not equality comparable?

Question

This question also applies to boost::function and std::tr1::function.

std::function is not equality comparable:

#include <functional>
void foo() { }

int main() {
    std::function<void()> f(foo), g(foo);
    bool are_equal(f == g); // Error:  f and g are not equality comparable
}

In C++11, the operator== and operator!= overloads just don't exist. In an early C++11 draft, the overloads were declared as deleted with the comment (N3092 §20.8.14.2):

// deleted overloads close possible hole in the type system

It does not say what the "possible hole in the type system" is. In TR1 and Boost, the overloads are declared but not defined. The TR1 specification comments (N1836 §3.7.2.6):

These member functions shall be left undefined.

[Note: the boolean-like conversion opens a loophole whereby two function instances can be compared via == or !=. These undefined void operators close the loophole and ensure a compile-time error. —end note]

My understanding of the "loophole" is that if we have a bool conversion function, that conversion may be used in equality comparisons (and in other circumstances):

struct S {
    operator bool() { return false; }
};

int main() {
    S a, b;
    bool are_equal(a == b); // Uses operator bool on a and b!  Oh no!
}

I was under the impression that the safe-bool idiom in C++03 and the use of an explicit conversion function in C++11 was used to avoid this "loophole." Boost and TR1 both use the safe-bool idiom in function and C++11 makes the bool conversion function explicit.

As an example of a class that has both, std::shared_ptr both has an explicit bool conversion function and is equality comparable.

Why is std::function not equality comparable? What is the "possible hole in the type system?" How is it different from std::shared_ptr?

Solution 1

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.

Solution 2

I may be wrong, but I think that equality of std::function objects is unfortunately not solvable in the generic sense. For example:

#include <boost/bind.hpp>
#include <boost/function.hpp>
#include <cstdio>

void f() {
    printf("hello\n");
}

int main() {
    boost::function<void()> f1 = f;
    boost::function<void()> f2 = boost::bind(f);

    f1();
    f2();
}

are f1 and f2 equal? What if I add an arbitrary number of function objects which simply wrap each other in various ways which eventually boils down to a call to f... still equal?

Solution 3

Why is std::function not equality comparable?

I think main reason is that if it were, then it couldn't be used with non equality comparable types, even if equality comparison is never performed.

I.e. code that performs comparison should be instantiated early - at the time when a callable object is stored into std::function, for instance in one of the constructors or assignment operators.

Such a limitation would greatly narrow the scope of application, and obviously not be acceptable for a "general-purpose polymorphic function wrapper".

---

It is important to note that it is possible to compare a boost::function with a callable object (but not with another boost::function)

Function object wrappers can be compared via == or != against any function object that can be stored within the wrapper.

This is possible, because function that performs such comparison is instantiated at point of comparison, based on known operand types.

Moreover, std::function has a target template member function, which can be used to perform similar comparison. In fact boost::function's comparison operators are implemented in terms of target member function.

So, there are no technical barriers which block implementation of function_comparable.

---

Among answers there is common "impossible in general" pattern:

• 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.

• I may be wrong, but I think that equality is of std::function objects is unfortunately not solvable in the generic sense.

• Because the equivalence of Turing machines is undecidable. Given two different function objects, you cannot possibly determine if they compute the same function or not. [That answer was deleted]

I completely disagree with this: it is not the job of std::function to perform comparison itself; its job is just to redirect request to comparison to underlying objects - that's all.

If underlying object type does not define comparison - it will be a compilation error; in any case, std::function is not required to deduce a comparison algorithm.

If the underlying object type defines comparison, but which works wrongly, or has some unusual semantic - it is not the problem of std::function itself either, but it is problem of the underlying type.

---

It is possible to implement function_comparable based on std::function.

Here is a proof-of-concept:

template<typename Callback,typename Function> inline
bool func_compare(const Function &lhs,const Function &rhs)
{
    typedef typename conditional
    <
        is_function<Callback>::value,
        typename add_pointer<Callback>::type,
        Callback
    >::type request_type;

    if (const request_type *lhs_internal = lhs.template target<request_type>())
        if (const request_type *rhs_internal = rhs.template target<request_type>())
            return *rhs_internal == *lhs_internal;
    return false;
}

#if USE_VARIADIC_TEMPLATES
    #define FUNC_SIG_TYPES typename ...Args
    #define FUNC_SIG_TYPES_PASS Args...
#else
    #define FUNC_SIG_TYPES typename function_signature
    #define FUNC_SIG_TYPES_PASS function_signature
#endif

template<FUNC_SIG_TYPES>
struct function_comparable: function<FUNC_SIG_TYPES_PASS>
{
    typedef function<FUNC_SIG_TYPES_PASS> Function;
    bool (*type_holder)(const Function &,const Function &);
public:
    function_comparable() {}
    template<typename Func> function_comparable(Func f)
        : Function(f), type_holder(func_compare<Func,Function>)
    {
    }
    template<typename Func> function_comparable &operator=(Func f)
    {
        Function::operator=(f);
        type_holder=func_compare<Func,Function>;
        return *this;
    }
    friend bool operator==(const Function &lhs,const function_comparable &rhs)
    {
        return rhs.type_holder(lhs,rhs);
    }
    friend bool operator==(const function_comparable &lhs,const Function &rhs)
    {
        return rhs==lhs;
    }
    friend void swap(function_comparable &lhs,function_comparable &rhs)// noexcept
    {
        lhs.swap(rhs);
        lhs.type_holder.swap(rhs.type_holder);
    }
};

There is a nice property - function_comparable can be compared against std::function too.

For instance, let's say we have vector of std::functions, and we want to give users register_callback and unregister_callback functions. Use of function_comparable is required only for unregister_callback parameter:

void register_callback(std::function<function_signature> callback);
void unregister_callback(function_comparable<function_signature> callback);

Live demo at Ideone

Source code of demo:

//             Copyright Evgeny Panasyuk 2012.
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)

#include <type_traits>
#include <functional>
#include <algorithm>
#include <stdexcept>
#include <iostream>
#include <typeinfo>
#include <utility>
#include <ostream>
#include <vector>
#include <string>

using namespace std;

// _____________________________Implementation__________________________________________

#define USE_VARIADIC_TEMPLATES 0

template<typename Callback,typename Function> inline
bool func_compare(const Function &lhs,const Function &rhs)
{
    typedef typename conditional
    <
        is_function<Callback>::value,
        typename add_pointer<Callback>::type,
        Callback
    >::type request_type;

    if (const request_type *lhs_internal = lhs.template target<request_type>())
        if (const request_type *rhs_internal = rhs.template target<request_type>())
            return *rhs_internal == *lhs_internal;
    return false;
}

#if USE_VARIADIC_TEMPLATES
    #define FUNC_SIG_TYPES typename ...Args
    #define FUNC_SIG_TYPES_PASS Args...
#else
    #define FUNC_SIG_TYPES typename function_signature
    #define FUNC_SIG_TYPES_PASS function_signature
#endif

template<FUNC_SIG_TYPES>
struct function_comparable: function<FUNC_SIG_TYPES_PASS>
{
    typedef function<FUNC_SIG_TYPES_PASS> Function;
    bool (*type_holder)(const Function &,const Function &);
public:
    function_comparable() {}
    template<typename Func> function_comparable(Func f)
        : Function(f), type_holder(func_compare<Func,Function>)
    {
    }
    template<typename Func> function_comparable &operator=(Func f)
    {
        Function::operator=(f);
        type_holder=func_compare<Func,Function>;
        return *this;
    }
    friend bool operator==(const Function &lhs,const function_comparable &rhs)
    {
        return rhs.type_holder(lhs,rhs);
    }
    friend bool operator==(const function_comparable &lhs,const Function &rhs)
    {
        return rhs==lhs;
    }
    // ...
    friend void swap(function_comparable &lhs,function_comparable &rhs)// noexcept
    {
        lhs.swap(rhs);
        lhs.type_holder.swap(rhs.type_holder);
    }
};

// ________________________________Example______________________________________________

typedef void (function_signature)();

void func1()
{
    cout << "func1" << endl;
}

void func3()
{
    cout << "func3" << endl;
}

class func2
{
    int data;
public:
    explicit func2(int n) : data(n) {}
    friend bool operator==(const func2 &lhs,const func2 &rhs)
    {
        return lhs.data==rhs.data;
    }
    void operator()()
    {
        cout << "func2, data=" << data << endl;
    }
};
struct Caller
{
    template<typename Func>
    void operator()(Func f)
    {
        f();
    }
};
class Callbacks
{
    vector<function<function_signature>> v;
public:
    void register_callback_comparator(function_comparable<function_signature> callback)
    {
        v.push_back(callback);
    }
    void register_callback(function<function_signature> callback)
    {
        v.push_back(callback);
    }
    void unregister_callback(function_comparable<function_signature> callback)
    {
        auto it=find(v.begin(),v.end(),callback);
        if(it!=v.end())
            v.erase(it);
        else
            throw runtime_error("not found");
    }
    void call_all()
    {
        for_each(v.begin(),v.end(),Caller());
        cout << string(16,'_') << endl;
    }
};

int main()
{
    Callbacks cb;
    function_comparable<function_signature> f;
    f=func1;
    cb.register_callback_comparator(f);

    cb.register_callback(func2(1));
    cb.register_callback(func2(2));
    cb.register_callback(func3);
    cb.call_all();

    cb.unregister_callback(func2(2));
    cb.call_all();
    cb.unregister_callback(func1);
    cb.call_all();
}

Output is:

func1
func2, data=1
func2, data=2
func3
________________
func1
func2, data=1
func3
________________
func2, data=1
func3
________________

P.S. It seems that with help of std::type_index, it is possible to implement something similar to function_comparable class, which also supports ordering (i.e. std::less) or even hashing. Not only ordering between different types, but also ordering within same type (this requires support from types, like LessThanComparable).

Solution 4

According to http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#1240:

The leading comment here is part of the history of std::function, which was introduced with N1402. During that time no explicit conversion functions existed, and the "safe-bool" idiom (based on pointers-to-member) was a popular technique. The only disadvantage of this idiom was that given two objects f1 and f2 of type std::function, the expression

f1 == f2;

was well-formed, just because the built-in operator== for pointer to member was considered after a single user-defined conversion. To fix this, an overload set of undefined comparison functions was added, such that overload resolution would prefer those ending up in a linkage error. The new language facility of deleted functions provided a much better diagnostic mechanism to fix this issue.

In C++11, the deleted functions are considered superfluous with the introduction of explicit conversion operators, so they will probably be removed for C++11.

The central point of this issue is, that with the replacement of the safe-bool idiom by explicit conversion to bool, the original "hole in the type system" does no longer exist and therefore the comment is wrong and the superfluous function definitions should be removed as well.

As for why you can't compare std::function objects, it's probably because they can possibly hold global/static functions, member functions, functors, etc, and to do that std::function "erases" some information about the underlying type. Implementing an equality operator would probably not be feasible because of that.

Solution 5

Actually, you can compare targets. It may work depends of what you want from comparison.

Here the code with inequality, but you can see how it works:

template <class Function>
struct Comparator
{
    bool operator()(const Function& f1, const Function& f2) const
    {
        auto ptr1 = f1.target<Function>();
        auto ptr2 = f2.target<Function>();
        return ptr1 < ptr2;
    }
};

typedef function<void(void)> Function;

set<Function, Comparator<Function>> setOfFunc;

void f11() {}

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "was inserted - " << setOfFunc.insert(bind(&f11)).second << endl;  // 1 - inserted
    cout << "was inserted - " << setOfFunc.insert(f11).second << endl;         // 0 - not inserted
    cout << "# of deleted is " << setOfFunc.erase(f11) << endl;

    return 0;
}

Ups, it is only valid since C++11.

View more solutions

Comments

[C. K. Young]

Right, but this (the original post, since fixed :-P) doesn't address the "why", only the "what". See the Boost.Function FAQ for the "why".

[James McNellis]

Thanks for the link. I should have checked the defects list; I just figured since it was specified the same in all three that it was intentional and not a defect.

[James McNellis]

Thanks. I was so focused on the "type system loophole" comments that I didn't think about the semantics. I'll accept this answer because in my opinion it most clearly answers the first and third parts, though the second part is explained best by In silico's answer.

[Matthieu M.]

+1 for an easy to grok example, standards and FAQ are great, but they are often a bit too abstract for people to just feel the reason.

[James McNellis]

Agreed with @Matthieu: that's a good, simple example of a problem I hadn't thought of.

[Evgeny Panasyuk]

Job of boost::function (if it would support comparison) - is not to deduce comparison algorithm, but just to redirect comparison invocation. If underlying object does not define comparison - then it is simply compile error. If underlying object defines wrong comparision - it is not problem of boost::function either.

[MSalters]

@EvgenyPanasyuk: You're forgetting type erasure. For a number of reasons including code bloat and performance, function may decide to replace the underlying object with another functionally indistinguishable object. Your proposal would restrict this ability. Furthermore, std::function will have multiple implementations so you'd have to be extra careful in specifying its behavior. (I.e. how does ADL work?)

[Evgeny Panasyuk]

@MSalters: 1. Why do you think I am forgetting about type erasure? 2. "replace the underlying object" - how that is possible? Especially in presense of ::target_type and ::target? Do you have any evidence? 3. "so you'd have to be extra careful in specifying its behavior" - of course everything that goes to ISO must be well-defined. Which problems with ADL do you think can be in this regard?

[MSalters]

@EvgenyPanasyuk: 1. because you assume the underlying object supports comparison 2. Because target_type is either void or T 3. You state comparison happen if "the underlying object defines comparison". Does that mean you call T::operator= (no ADL) or do you expect the lookup of f.__obj == g.__obj to succeed?

[Evgeny Panasyuk]

@MSalters, 1.Looks like you have not read my answer stackoverflow.com/a/13105074/1762344 and as the result you are making unsubstantiated assertions.First sentence in my A is "I think main reason is that if it would be, then it can't be used with non equality comparable types, even if equality comparison is never performed." 2.Could you please show any references to ISO or at least some article where std::function is allowed to "replace the underlying object"?3.I expect use of ADL,and I used ADL in my implementation.But,I dont see how this decision conceptually affects headline question

[monkey0506]

This doesn't do what you think it's doing. target<T> returns a T* that is not null IFF T matches the underlying function pointer/functor type/bind expression type. You are calling it as function<void(void)>::target<function<void(void)>>. The underlying type of function<void(void)> is void(void), not function<void(void)>. The two pointers obtained (ptr1 and ptr2) are both always nullptr, and nullptr < nullptr is always false, which is what prevents the second insertion. The first insertion only succeeds because the set is empty, so there's nothing to compare.

[monkey0506]

Live Demo showing that the set will only accept a maximum of one function.