Reduce code duplication when defining a commutative operation

Question

I have an overload set of a commutative binary function called overlap that takes two different types:

 class A a; class B b; bool overlap(A, B); bool overlap(B, A); 

My overlap function returns true if and only if one form overlaps another - this is one common example used when discussing multimethods .

Since overlap(a, b) equivalent to overlap(b, a) , I only need to implement one “side” of the relationship. One recurring solution is to write something like this:

 bool overlap(A a, B b) { /* check for overlap */ } bool overlap(B b, A a) { return overlap(a, b); } 

But I would rather not write extra N! / 2 N! / 2 trivial versions of the same function, allowing them to be generated instead using the template.

 template <typename T, typename U> bool overlap(T&& t, U&& u) { return overlap(std::forward<U>(u), std::forward<T>(t)); } 

Unfortunately, this is subject to infinite recursion, which is unacceptable: see http://coliru.stacked-crooked.com/a/20851835593bd557

How can I prevent such infinite recursion? Did I get the problem right?

Answer 1

Here's a simple fix:

 template <typename T, typename U> void overlap(T t, U u) { void overlap(U, T); overlap(u, t); } 

The template itself declares an objective function, which will be preferable to recursion, because it is an exact match (do not forget to take care of the constant and the reference characteristic in your real case). If the function has not been implemented, you get a linker error:

 /tmp/cc7zinK8.o: In function `void overlap<C, D>(C, D)': main.cpp:(.text._Z7overlapI1C1DEvT_T0_[_Z7overlapI1C1DEvT_T0_]+0x20): undefined reference to `overlap(D, C)' collect2: error: ld returned 1 exit status 

... which points directly to the missing function :)

Answer 2

As a wise man once said, there are no problems that you cannot solve with an extra layer of indirection, with the exception of too many layers of indirection.

So, use SFINAE and some indirectness to do this:

 template<class A, class B> auto overlap(A&& a, B&& b) -> decltype(overlap_impl('\0', std::forward<A>(a), std::forward<B>(b))) { return overlap_impl('\0', std::forward<A>(a), std::forward<B>(b)); } template<class A, class B> auto overlap_impl(int, A&& a, B&& b) -> decltype(do_overlap(std::forward<A>(a), std::forward<B>(b))) { return do_overlap(std::forward<A>(a), std::forward<B>(b)); } template<class A, class B> auto overlap_impl(long, B&& b, A&& a) -> decltype(do_overlap(std::forward<A>(a), std::forward<B>(b))) { return do_overlap(std::forward<A>(a), std::forward<B>(b)); } // You can provide more choices if you want, for example to use member-functions. // Implement `do_overlap(A, B)`, maybe with references, in at least one direction. 

Answer 3

You can rename the actual method to something like overlap_impl and call it inside the template. I will break the recursion:

 bool overlap_impl(A a, B b) { /* check for overlap */ } template <typename T, typename U> bool overlap(T&& t, U&& u) { return overlap_impl(std::forward<U>(u), std::forward<T>(t)); } template<> bool overlap(A&& t, B&& u) { return overlap_impl(std::forward<A>(t), std::forward<B>(u)); }