SFINAE not solvable overload

user_6040181 0
Viewed 106

Context

I want to check whether an element is present inside a container or not.

I would like to write a generic function which exploits the structure of the container.

In particular, the function should pick the method count() for those data structures which support that (e.g., std::set, std::unordered_set, ...).

In C++17 we can write something like:

#include <algorithm>
#include <iterator>

template <typename Container, typename Element>
constexpr bool hasElement(const Container& c, const Element& e) {
  if constexpr (hasCount<Container>::value) {
    return c.count(e);
  } else {
    return std::find(std::cbegin(c), std::cend(c), e) != std::cend(c);
  }
}

All right! Now we need to implement hasCount<T> trait.

With SFINAE (and std::void_t in C++17) we can write something like:

#include <type_traits>

template <typename T, typename = std::void_t<>>
struct hasCount: std::false_type {};

template <typename T>
struct hasCount<T, std::void_t<decltype(&T::count)>> : std::true_type {};

This approach works quite well. For instance, the following snippet compiles (with previous definitions, of course):

struct Foo {
  int count();
};

struct Bar {};

static_assert(hasCount<Foo>::value);
static_assert(!hasCount<Bar>::value);

Problem

Of course, I am going to use hasCount on STL data structure, such as std::vector, and std::set. Here the problem!

Since C++14, std::set<T>::count has a template overload.

Therefore static_assert(hasCount<std::set<int>>::value); fails!

That's because decltype(&std::set<int>::count) cannot be automatically deduced due to the overload.

Question

Given the context:

  • is there a way to solve the automatic overload?
  • if not, is there another way to write a better hasCount trait? (C++20 Concepts are not available).

External dependencies (libraries, such as boost) should be avoided.

typetraits c++17 template-meta-programming sfinae c++
3 Answers

is there a way to solve the automatic overload?

Yes, if you know the types of the arguments to pass to the method. In your case, if I understand correctly, Element.

Your answer show how to solve the problem modifying your original code. Next I propose a solution based on declared-only constexpr functions

is there another way to write a better hasCount trait?

I don't know if better, but usually I prefer use constexpr functions.

Something as follows (caution: code not tested tested directly from the OP)

template <typename...>
constexpr std::false_type hasCountF (...);

template <typename T, typename ... As>
constexpr auto hasCountF (int)
   -> decltype( std::declval<T>().count(std::declval<As>()...), std::true_type{});

template <typename ... Ts>
using has_count = decltype(hasCountF<Ts...>(1));

and maybe also (only from C++14)

template <typename ... Ts>
constexpr auto has_count_v = has_count<Ts...>::value:

and you can call it as follows

if constexpr ( has_count_v<Container, Element> )

In your case, using the Container c and Element e in your function, you can make it simpler (avoiding a lot of std::declval()'s) and you can try with a couple of functions as follows

template <typename...>
constexpr std::false_type hasCountF (...);

template <typename C, typename ... As>
constexpr auto hasCountF (C const & c, As const & ... as)
   -> decltype( c.count(as...), std::true_type{});

calling it as follows

if constexpr ( decltype(hasCountF(c, e))::value )

but I prefer the preceding solution because require more typewriting but is more flexible.

user_60226560

From question comment, the right approach is to check the "call expression" (rather than the existence of the method).

Therefore, an improvement of the trait struct may be the following:

#include <type_traits>

template <typename T, typename U, typename = std::void_t<>>
struct hasCount : std::false_type {};

template <typename T, typename U>
struct hasCount<T, U, std::void_t<decltype(std::declval<T>().count(std::declval<U>()))>> : 
  std::true_type {};

Given two instance t and u of types respectively T and U, it checks whether the expression t.count(u) is valid or not.

Therefore the following code is valid:

static_assert(hasCount<std::set<int>, int>::value);

Solving the problem in the question.

Additional Notes

The generic algorithm now can be implemented with:

#include <algorithm>
#include <iterator>

template <typename Container, typename Element>
constexpr bool hasElement(const Container& c, const Element& e) {
  if constexpr (hasCount<Container, Element>::value) {
    return c.count(e);
  } else {
    return std::find(std::cbegin(c), std::cend(c), e) != std::cend(c);
  }
}
user_60401810

It's helpful in places like this to simply defer to a separate overload set that has a fallback:

template <typename Container, typename Element>
constexpr auto hasElement_impl(int, const Container& c, const Element& e) 
    -> decltype(c.count(e))
{
    return c.count(e);
}

template <typename Container, typename Element>
constexpr bool hasElement_impl(long, const Container& c, const Element& e) 
{
    return std::find(c.begin(), c.end(), e) != c.end();
}

template <typename Container, typename Element>
constexpr bool hasElement(const Container& c, const Element& e) 
{
    return hasElement_impl(0, c, e);
}

If you can do c.count(e), do that. Otherwise, fallback to find(). You don't need to write a type trait in this case, and indeed the question itself demonstrates the problem with trying to go that route. Much simpler not to.

Alternatively, using something like Boost.HOF:

constexpr inline auto hasElement = boost::hof::first_of(
    [](auto const& cnt, auto const& elem) BOOST_HOF_RETURNS(cnt.count(elem)),
    [](auto const& cnt, auto const& elem) {
        return std::find(cnt.begin(), cnt.end(), elem) != cnt.end();
    }
);

In C++20, this sort of algorithm refinement will be a lot easier thanks to concepts:

template <AssociativeContainer C, typename E>
bool hasElement(const C& c, const E& e) { return c.count(e); }

template <typename C, typename E>
bool hasElement(const C& c, const E& e) { return std::find(c.begin(), c.end(), e) != c.end(); }
user_20690640
Related