Expression SFINAE: how to select template version based on whether type contains a function with one or more arguments

Question

I'm trying to select at compile time between different template implementations depending on whether or not the argument implements a particular function. This is a common question (see this S.O. question and this example referenced by this article. The common answer is "use expression SFINAE".

Most of the examples show how expression SFINAE can be used to select based on the presence of a zero-argument function. I've tried to adapt these to my 1-argument use case by using declval (loosely based off of this example), but I cannot seem to get it to work.

I'm sure I'm doing something wrong in the example below, but I can't figure out what it is. The example is trying to define two versions of a template bool Util::Container::Contains(container, value) which will use the container's built-in find(value) method if it exists, and otherwise fall back to a linear search using std::find(...)

Please note: I know I can make this work by just overloading Contains() for unordered_map, unordered_set, etc., but instead I'd like to figure out this pattern-based approach so that it will automatically delegate to any container's find(value) without requiring an overload to be added.

#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <string>

namespace Util::Container {

    namespace Detail
    {
        template <typename T>
        class HasFindMethod
        {
        private:
            typedef char YesType[1];
            typedef char NoType[2];

            // This is how the examples show it being done for a 0-arg function
            //template <typename C> static YesType& Test(decltype(&C::find));

            // Here's my attempt to make it match a 1-arg function
            template <typename C> static YesType& 
                Test(decltype(std::declval<C>().find(std::declval<const C::value_type&>())));

            template <typename C> static NoType& Test(...);

        public:
            enum { value = sizeof(Test<T>(0)) == sizeof(YesType) };
        };
    }

    // Fallback: uses std::find() to do the lookup if no type-specific T::find(value) exists
    template<typename T>
    bool Contains(const T& in_container, const typename T::value_type& in_item)
    {
        const auto& result = std::find(in_container.cbegin(), in_container.cend(), in_item);
        return (result != in_container.cend());
    }

    // Preferred: use T::find() to do the lookup if possible
    template<typename T>
    inline typename std::enable_if<Detail::HasFindMethod<T>::value, bool>::type 
        Contains(const T& in_container, const typename T::value_type& in_item)
    {
        return (in_container.find(in_item) != in_container.end());
    }
}

int main()
{
    const std::vector<int> v { 1, 2, 3 };
    const std::unordered_map<int, std::string> m { {1,"1" }, {2,"2"} };
    const std::unordered_set<std::string> s { "1" , "2" };

    // These should use the std::find()-based version of Contains() since vector and unordered_map
    // have no find(value_type) method. And they do.
    const bool r_v = Util::Container::Contains(v, 2);
    const bool r_m = Util::Container::Contains(m, { 2, "2" });

    // !!!!!! 
    // 
    // This should use the T::find(value_type)-based version of Contains() since
    // unordered_set has a find(value_type) method.
    //
    // But it doesn't --- that's the issue I'm trying to solve.
    // 
    const bool r_s = Util::Container::Contains(s, "2");
}

If anyone can show me how to fix this, I'd very much appreciate it.

FWIW, I'm attempting to implement this in Visual Studio 2017 v15.8

For the record, to compile under gcc/clang (or rather, be standard compliant), you further need an `#include ` and a `const typename C::value_type&`. Not that this matters for getting it to work in MSVC. — Max Langhof, Oct 18 '18 at 16:15
Are you familiar with [void_t](https://en.cppreference.com/w/cpp/types/void_t) utility? If not, see the examples provided there. — r3mus n0x, Oct 18 '18 at 16:23
Two problems: The parameter to to `Test` is `decltype(...)` to which you pass a literal 0 when you initialize `value`. That parameter presumably should be a pointer, so add `*` right after the `decltype`. The next problem is that `unordered_map` doesn't have a `find` method that takes its `value_type`, only its `key_type`, so the expression won't substitute. See the below answers for a better solution. — David G, Oct 18 '18 at 16:33
Good point about the unordered_map find() method; that's my error. I'll fix the example — Chris Kline, Oct 18 '18 at 16:40

Jarod42 · Answer 1 · 2018-10-18T17:15:54.250

An easy way with decltype is

template<typename C, typename V>
auto Contains(const C& c, const V& value)
-> decltype(std::find(c.cbegin(), c.cend(), value) != c.cend())
{
    return std::find(c.cbegin(), c.cend(), value) != c.cend();
}

template <typename C, typename Key>
auto Contains(const C& c, const Key& key)
-> decltype(c.find(key) != c.end())
{
    return c.find(key) != c.end();
}

but then when both function are possible you would have ambiguous call.

So just add extra parameter to prioritize the overload:

struct low_priority {};
struct high_priority : low_priority {};


template<typename C, typename V>
auto ContainsImpl(low_priority, const C& c, const V& value)
-> decltype(std::find(c.cbegin(), c.cend(), value) != c.cend())
{
    return std::find(c.cbegin(), c.cend(), value) != c.cend();
}

template <typename C, typename Key>
auto ContainsImpl(high_priority, const C& c, const Key& key)
-> decltype(c.find(key) != c.end())
{
    return c.find(key) != c.end();
}

template <typename C, typename T>
auto Contains(const C& c, const T& t)
-> decltype(ContainsImpl(high_priority{}, c, t))
{
    return ContainsImpl(high_priority{}, c, t);
}

Now about your version, you have several issues

The last one:

// Expected Fallback: uses std::find() to do the lookup if no type-specific T::find(value) exists
template<typename T>
bool Contains(const T&, const typename T::value_type&);

// Expected Preferred: use T::find() to do the lookup if possible
template<typename T>
typename std::enable_if<Detail::HasFindMethod<T>::value, bool>::type 
Contains(const T&, const typename T::value_type&);

SFINAE allows to discard overload, but not to prioritize them. You have to use priority, as shown above, or create exclusive set of overload:

template<typename T>
typename std::enable_if<!Detail::HasFindMethod<T>::value, bool>::type 
Contains(const T&, const typename T::value_type&);

template<typename T>
typename std::enable_if<Detail::HasFindMethod<T>::value, bool>::type 
Contains(const T&, const typename T::value_type&);

In addition to that, as mentioned in comment map family would use key_type and not value_type.

Then your detection code is buggy,

// This is how the examples show it being done for a 0-arg function //template static YesType& Test(decltype(&C::find));

No, this detects if C has a method find (without overload).

template <typename C> static YesType& 
Test(decltype(std::declval<C>().find(std::declval<const C::value_type&>())));

Here, you use SFINAE, but final type would be the (const_)iterator, and Test<C>(0) won't take that overload (unless iterator can be build from 0 which is not the regular case). Adding extra * is a possibility, then you have pointer on iterator which might be initialized by 0.

Else you might use code provided in your provided link:

namespace detail{
  template<class T, typename ... Args>
  static auto test_find(int)
      -> sfinae_true<decltype(std::declval<T>().find(std::declval<const Arg&>()...))>;
  template<class, class ...>
  static auto test_find(long) -> std::false_type;
} // detail::

template<class C, typename ... Args>
struct has_find : decltype(detail::test_find<T, Args...>(0)){};
// int has higher priority than long for overload resolution

and then use your traits with std::enable_if has_find<Container, Key>::value.

If you use a custom type for priority, going all-out doesn't cost much more: `template struct Priority : Priority {}; template <> struct Priority<0> {};`. Otherwise, Standard integer-types are enough. — Deduplicator, Oct 18 '18 at 16:37
@Deduplicator: I found `int` vs `long` vs `...` not clear/readable. I generally use the template Priority though. — Jarod42, Oct 18 '18 at 16:41
@Jarod42 this is a great solution to the problem. The only reason I didn't select it as the answer is because your original answer (before you edited it to contain more info) didn't answer my actual question (i.e. why my approach wasn't working), and in the meantime I selected Max Langhof's answer. But thank you for your answer! — Chris Kline, Oct 18 '18 at 16:51

Max Langhof · Accepted Answer · 2018-10-18T16:49:06.197

The immediate problem is that the argument you are passing to Test is not compatible with the YesType version.

For example, Detail::HasFindMethod<std::unordered_set<int>> will result in the following two Test signatures (because find would return an iterator):

        static YesType& Test(std::unordered_set<int>::iterator);

        static NoType& Test(...);

You try to call Test with the argument 0, which is not convertible to iterator. Hence, the second one is picked.

As a solution, use a pointer:

        template <typename C> static YesType& 
            Test(decltype(std::declval<C>().find(std::declval<const C::value_type&>()))*);
        //                                                                             ^

Then do the check with a nullptr argument:

        enum { value = sizeof(Test<T>(nullptr)) == sizeof(YesType) };

Now we would have ambiguity (the Test(...) would also match), so we can make that one a worse match:

        template <typename C, class ... Args> static NoType& Test(void*, Args...);

As shown in the other answers, this is still a comparatively convoluted solution (and there are more issues that prevent it from working in your instance, such as ambiguity between the overloads when the enable_if does work). Just explaining the particular stopper in your attempt here.

Thank you, this was an exceptionally clear explanation of the question I was asking. And it also helped me understand this general idiom better. Great answer. — Chris Kline, Oct 18 '18 at 16:48

r3mus n0x · Answer 3 · 2018-10-18T17:09:34.577

A simpler (in my opinion) and more readable solution can be achieved using void_t utility:

template <typename T, typename Dummy = void>
struct has_member_find : std::false_type { };

template <typename T>
struct has_member_find<T,
    std::void_t<decltype(std::declval<T>().find(std::declval<typename T::value_type &>()))>>
    : std::true_type { };

template<typename T>
std::enable_if_t<!has_member_find<T>::value, bool>
Contains(const T& in_container, const typename T::value_type& in_item)
{
    const auto& result = std::find(in_container.cbegin(), in_container.cend(), in_item);
    return (result != in_container.cend());
}

template<typename T>
std::enable_if_t<has_member_find<T>::value, bool>
Contains(const T& in_container, const typename T::value_type& in_item)
{
    return (in_container.find(in_item) != in_container.end());
}

Note that void_t is only available since C++17, however it you don't have a full C++17 support you can define it yourself since it's definition is ridiculously simple:

template< class... >
using void_t = void;

You can learn more about this utility and the pattern it introduces in this paper.

For some C++11 compilers, `void_t` might require inner struct: `template struct void_t_impl { using type = void;}; template using void_t = typename void_t_impl::type;`. — Jarod42, Oct 18 '18 at 17:13

Expression SFINAE: how to select template version based on whether type contains a function with one or more arguments

3 Answers3