Home > Back-end >  SFINAE doesn't pick the right overload resolution
SFINAE doesn't pick the right overload resolution

Time:09-17

I am trying to solve a relatively easy excursive involving SFINAE.
My goal is to find best way of sorting for particular type T.
There are 3 cases for me:

  1. type T supports `sort` function
  2. type T supports range i.e. have begin and end functions (lets not include comparability at this point)
  3. type T is not sortable (doesn't support ranges and doesn't have sort function)

So I wrote basic template overload and trying to benefit from SFINAE

#include <iostream>
#include <vector>

struct HaveSort { char c; };
struct HaveRange { char c; HaveSort s; };
struct HaveNone { char c; HaveRange r; };

template<typename T>
HaveSort test_sort(decltype(&T::sort), decltype(&T::sort));

template<typename T>
HaveRange test_sort(decltype(&T::begin), decltype(&T::end));

template<typename T>
HaveNone test_sort(...);

template<typename T, int N>
struct sort_helper;

template<typename T>
struct sort_helper<T, sizeof(HaveSort)>
{
    static void fsort(T& x)
    {
        std::cout << "Type " << typeid(x).name() << " supports sort" << std::endl;
        x.sort();
    }
};

template<typename T>
struct sort_helper<T, sizeof(HaveRange)>
{
    static void fsort(T& x)
    {
        std::cout << "Type " << typeid(x).name() << " supports range" << std::endl;
        std::sort(x.begin(), x.end());
    }
};

template<typename T>
struct sort_helper<T, sizeof(HaveNone)>
{
    static void fsort(T& x)
    {
        std::cout << "Type " << typeid(x).name() << " supports nothing" << std::endl;
    }
};

template<typename T>
void fast_sort(T& x)
{
    sort_helper<T, sizeof(test_sort<T>(NULL, NULL))>::fsort(x);
}


class A {};
class B { void sort() {} };

int main()
{
    static_assert(sizeof(HaveSort) != sizeof(HaveRange), "Find other way to handle HaveSort and HaveRange\n");
    static_assert(sizeof(HaveRange) != sizeof(HaveNone), "Find other way to handle HaveRange and HaveNone\n");

    std::vector<int> V{ 1,9,5,3 };
    A a;
    B b;
    fast_sort(V);
    fast_sort(a);
    fast_sort(b);
}

This outputs

Type class std::vector<int,class std::allocator<int> > supports nothing
Type class A supports nothing
Type class B supports nothing

For all three classes - vector<int>, A, B.

Does anyone know why SFINAE doesn't pick up right overload here?
Thanks in advance.

CodePudding user response:

Actually SFINAE apply to all of your types:

  • A doesn't have sort()/begin()/end()
  • B doesn't have begin()/end() and doesn't have public sort().
  • std::vector<int> doesn't have sort(), and &std::vector<int>::begin (similar for end) is ambiguous, as there are several overloads (const and non-const method).

I would do something like that:

template <std::size_t N> struct overload_priority : overload_priority<N - 1> {};
template <> struct overload_priority<0> {}; // lowest priority


template<typename T>
auto fsort(T& x, overload_priority<2>) -> decltype(x.sort(), void())
{
    std::cout << "Type " << typeid(x).name() << " supports sort" << std::endl;
    x.sort();
}

template<typename T>
auto fsort(T& x, overload_priority<1>) -> decltype(std::sort(x.begin(), x.end()), void())
{
    std::cout << "Type " << typeid(x).name() << " supports range" << std::endl;
    std::sort(x.begin(), x.end());
}

template<typename T>
void fsort(T& x, overload_priority<0>)
{
    std::cout << "Type " << typeid(x).name() << " supports nothing" << std::endl;
}

template<typename T>
void fast_sort(T& x)
{
    fsort(x, overload_priority<5>{}); // big enough
}

Demo

CodePudding user response:

Reasons for your SFINAE failure:

  • The member function sort() is private

  • &T::begin has multiple overloads so taking its address fails.

Instead of taking addresses and comparing sizes I would use bools and some SFINAE helpers.

template<class T>
struct has_sort { // check if T has a (public) member function called sort()
    template<class> static auto Test(...) -> std::false_type;

    template<class TT>
    static auto Test(int) -> 
        decltype( std::declval<TT&>().sort(), std::true_type() );

    static constexpr bool value = decltype(Test<T>(0))::value;
};

template<class T> inline static constexpr bool has_sort_v = has_sort<T>::value;
template<class T>
struct has_range {  // check if T supports `std::begin` and `std::end`
    template<class> static auto Test(...) -> std::false_type;

    template<class TT>
    static auto Test(int) ->
        decltype( std::begin(std::declval<TT&>()),
                  std::end(std::declval<TT&>()),
                  std::true_type() );

    static constexpr bool value = decltype(Test<T>(0))::value;
};

template<class T> inline static constexpr bool has_range_v = has_range<T>::value;

Your fast_sort function could then look like this:

#include <algorithm>
#include <iostream>
#include <vector>

template<typename T>
void fast_sort(T& x) {
    if constexpr(has_sort_v<T>) {
        std::cout << "has_sort\n";
        x.sort();

    } else if constexpr(has_range_v<T>) {
        std::cout << "has_range\n";
        std::sort(std::begin(x), std::end(x));

    } else {
        std::cout << "bohoo\n";
    }
}

class A {};
class B { public: void sort() {} }; // note: sort() made public

int main() {
    std::vector<int> V{ 1,9,5,3 };
    A a;
    B b;
    fast_sort(V);
    fast_sort(a);
    fast_sort(b);
}

Output:

has_range
bohoo
has_sort

Demo

  • Related