Why is std :: function not equivalently comparable?

Question

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

std::function not equivalent to equality:

 #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, operator== and operator!= Overloads simply don't exist. In an early C ++ 11 project, overloads were declared as deleted with a comment (N3092 §20.8.14.2):

 // deleted overloads close possible hole in the type system 

He does not say what a "possible hole in the type system is." In TR1 and Boost, congestion is declared but not defined. Specification specification TR1 (N1836 §3.7.2.6):

These member functions must be left undefined.

[Note: a logical conversion opens a loophole whereby two instances of a function can be compared using == or != . These undefined void statements close a loophole and provide a compile-time error. -end note]

My understanding of the “loophole” is that if we have a bool transform function, this transform can be used when comparing 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 had the impression that the safe-bool idiom in C ++ 03 and the use of the explicit conversion function in C ++ 11 were used to avoid this “loophole”. Boost and TR1 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 parameters, std::shared_ptr has an explicit bool conversion function and is comparable.

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

Answer 1

Why is std::function not comparable equality?

std::function is a wrapper for arbitrary called types, so in order to implement equality comparisons at all, you will need to require that all called types be comparable in level, placing a burden on someone implementing the function object. Even then you would get a narrow concept of equality, since equivalent functions would compare unequal ones if (for example) they were constructed by binding arguments in a different order. I believe that it is impossible to verify equivalence in the general case.

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

I would suggest that this means that it’s easier to remove the operators and know for sure that using them will never give valid code than to prove that there is no possibility of unwanted implicit conversions occurring in some previously undiscovered case with an angle.

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 empty or both non-empty and point to the same object.

Answer 2

This is discussed in detail in the Boost.Function Frequently Asked Questions. :-)

Answer 3

Perhaps I am mistaken, but I think that the equality of std::function objects, unfortunately, is not decidable in the general 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 that simply wrap each other in different ways, which ultimately boil down to calling f ... still equal?

Answer 4

Why is std :: function not equally comparable?

I think the main reason is that if that were the case, then it cannot be used with comparable types of equality, even if equality comparison is never performed.

those. the code that performs the comparison must be created earlier - at the moment when the called object is stored in std :: function, for example, in one of the constructors or assignment operators.

Such a limitation will significantly reduce the scope of application and, obviously, is unacceptable for a “universal polymorphic functional shell” .

---

It cannot be noticed that it is possible to compare boost :: function with the called object (but not with another boost :: function)

Shells of object objects can be compared using == or! = With any functional object that can be stored in the shell.

This is possible because the function that performs this comparison is instantly initialized at the comparison point, based on knowledge of the type of operand.

In addition, std :: function has a target member function , which can be used for similar comparisons. In fact, boost :: function comparison operators are implemented in terms of the target function.

Thus, there are no technical barriers that block the implementation of function_comparable .

---

Among the answers there is a general "impossible in general" pattern:

• Even then you would get a narrow concept of equality, since equivalent functions would compare unequal ones if (for example) they were constructed by binding arguments in a different order. I believe that it is impossible to verify equivalence in the general case.

• Perhaps I am mistaken, but I think that the equality of std :: function objects, unfortunately, is not decidable in the general sense.

• Because the equivalence of turing machines is insoluble. Given two different functional objects, you cannot determine whether they calculate the same function or not. [This answer has been deleted]

I completely disagree with this: it’s not that std :: function does the comparison itself, this task is just to redirect the request for comparison with basic objects - that’s all.

If the type of the base object does not determine the comparison, in any case it will be a compilation error, std :: function is not required to determine the comparison algorithm.

If the type of the base object determines the comparison, but which does not work correctly or has some unusual semantics, this is also not a problem of std :: function itself, but it is a problem of the base type .. p>

---

You can implement function_comparable based on std :: function.

Here is the 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 some nice property - function_comparable can be compared with std :: function .

For example, let's say we have a std :: function vector , and we want to give the user register_callback and unregister_callback . The use of function_comparable is required only for the unregister_callback parameter:

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

Live demo in Perfect

Download source package 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(); } 

Exit:

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

PS It seems that using std :: type_index can be implemented similarly to the class function_comparable , which also supports ordering (i.e. smaller) or even hashing. But not only ordering between different types, but also ordering within the same type (this requires support for types such as LessThanComparable).

Answer 5

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

The lead comment here is part of the std::function story, which was introduced with N1402. During this time, without explicit conversion functions and the "idiom" safe "(based on member pointers) was a popular technique. The only drawback of this idiom was that two objects f1 and f2 of type std :: function expression were given

f1 == f2;

was well-formed, only because the built-in == operator for a member pointer was considered after one user-defined conversion. To fix this, the overload set is undefined, comparison functions have been added that allow overload resolution that ends with a communication error. A new language tool to remove features is a much better diagnostic mechanism to fix this problem.

In C ++ 0x, remote functions are considered redundant with the introduction of explicit conversion operators, so they are likely to be removed for C ++ 0x.

The central point of this problem is that with the replacement of the safe-bool idiom by explicit conversion, the original "hole in the" system "type no longer exists and therefore the comment is incorrect and the definition of the redundant function should also be deleted.

As for why you cannot compare std::function objects, probably because they can contain global / static functions, member functions, functors, etc., and for that std::function "deletes" some basic type information. Because of this, the implementation of the equality operator would probably be impossible.

Answer 6

Actually, you can compare goals. This may depend on what you want from the comparison.

Here's 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 valid only with C ++ 11.

Answer 7

How to try something like the following, this works well for testing patterns.

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

Answer 8

the least that could be done is if std :: function stores the address of the function used to bind to the string, and string comparison is used instead.