Why is std::function not equality comparable?

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 lef开发者_高级运维t 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?

---

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.

---

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?

---

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

---

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.

---

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.

---

How about trying something like the following, this works well for testing templates.

if (std::is_same<T1, T2>::value)
{
    ...
}

---

the least that could be done is if std::function saves the address of the function used for binding to a string and used string comparison instead.