How do I enable a function template if a class has a specific member function?

Question

I wrote the following template function, which checks whether an arbitary container contains a specific element:

template<template<class, class...> class container_t, class item_t, class... rest_t>
bool contains(const container_t<item_t, rest_t...> &_container, const item_t &_item) {
    for(const item_t &otherItem : _container) {
        if(otherItem == _item) { return true; }
    }
    return false;
}

This works well for most containers. However for all kinds of sets (and maps) it is sub optimal since there we could use:

template<template<class, class...> class set_t, class item_t, class... rest_t>
bool contains(const set_t<item_t, rest_t...> &_set, const item_t &_item) {
    return _set.count(_item) > 0;
}

Obviously we can't use both templates simultaneously because of ambiguity. Now I am looking for a way to use std::enable_if to enable the to first template if container_t does not provide a count member function and the second template if it does. However I can't figure out how to check for a specif member function (using C++11).

Translative

If you are willing to add boost as a dependency then boost.TTI has what you are looking for in the BOOST_TTI_HAS_MEMBER_FUNCTION macro – Nanete

Are you totally sure you want to do this? In the standard library they make you spell out exactly which find form you want to use to make it explicitly clear when you're doing a linear search and when you're using a more efficient mechanism. As a side note if you really do want to do this, definitely use find instead of count, it's just avoiding premature pessimization. – Dietz

@SimonGibbons: Thanks, it looks like what I need. However I would prefer not to depend on boost at the moment. – Translative

@MarkB: As far as I understand std::find also uses different algorithms depending on whether or not we have an ordered container, doesn't it? At least en.cppreference.com/w/cpp/algorithm/find writes that the complexity is at most linear, i.e. can be less than linear for suitable containers. However correct me if I am wrong. – Translative

@Translative The standard just says "at most last-first comparisons", so the assumption is that it's linear for all container types. – Dietz

Answer 1

C++14 feature, reimplemented:

template<class...>struct voider{using type=void;};
template<class...Ts>using void_t=typename voider<Ts...>::type;

A mini metaprogramming library:

template<class...>struct types{using type=types;};
namespace details {
  template<template<class...>class Z, class types, class=void>
  struct can_apply : std::false_type {};
  template<template<class...>class Z, class...Ts>
  struct can_apply< Z, types<Ts...>, void_t< Z<Ts...> > >:
    std::true_type
  {};
}
template<template<class...>class Z, class...Ts>
using can_apply = details::can_apply<Z,types<Ts...>>;

can_apply< some_template, args... > inherits from true_type iff some_template<args...> is a valid expression (in the immediate context).

Now for your problem:

template<class T, class I>
using dot_count_type = decltype( std::declval<T>().count(std::declval<I>()) );

template<class T, class I>
using has_dot_count = can_apply<dot_count_type, T, I>;

and has_dot_count is a traits class that inherits from true_type iff T.count(I) is a valid expression.

namespace details {
  template<class C, class I>
  bool contains(std::false_type, C const& c, I const& i) {
    for(auto&& x:c) {
      if(x == i) { return true; }
    }
    return false;
  }
  template<class C, class I>
  bool contains(std::true_type, C const& c, I const& i) {
    return c.count(i) != 0;
  }
}
template<class C, class I>
bool contains( C const& c, I const& i ) {
  return details::contains( has_dot_count<C const&,I const&>{}, c, i );
}

which uses tag dispatching instead of SFINAE.

Using find seems like a better idea than .count as an aside. In fact, in one case you should use .find the other find. In both cases you should use using std::end; auto e = end(c);.

As an aside, MSVC 2013 (I don't know about 2015) doesn't handle this kind of SFINAE used above. They call it "expression SFINAE". They have custom extensions to detect the existence of a member function. But that is because they are far from C++11 standard compliant.

Nowell

VS 2015 (at least preview version) doesn't support it as well – Digitoxin

Interesting approach. Works well for me (GCC 4.8). Thank you very much. – Translative

Answer 2

C++20

// helper concept
template <typename Container, typename Item>
concept containing = requires (const Container& container, const Item& item) {
    { container.contains(item) } -> std::convertible_to<bool>;
};

// first overload, using std::ranges::contains from <algorithm>
template<std::ranges::input_range Container, typename Item>
bool contains(const Container &container, const Item &item) {
    return std::ranges::contains(container, item);
}

// if possible, use the .contains() member function directly
template<std::ranges::input_range Container, typename Item>
requires containing<Container, Item>
bool contains(const Container &container, const Item &item) {
    // note: in C++20, the old .count() technique has been obsoleted
    //       by a proper .contains() member function
    return container.contains(item);
}

The second overload will win in overload resolution because it is more constrained.

C++11

In C++11, you can write the following, using tag dispatch:

// Create tags for tag dispatch
struct contains_find_t {};
struct contains_count_t : contains_find_t {};

// fallback with no SFINAE
template<typename Container, typename Item>
bool do_contains(const Container &container, const Item &item, contains_find_t) {
    return std::find(container.begin(), container.end(), item) != container.end();
}

// preferred funtion template, with SFINAE in trailing return type
template<typename Container, typename Item>
auto do_contains(const Container &container, const Item &item, contains_count_t)
  -> decltype(container.count(item) != 0) {
    return container.count(item) != 0;
}

template<typename Container, typename Item>
bool contains(const Container &container, const Item &item) {
    return do_contains(container, item, contains_count_t{});
}

The inheritance hierarchy of contains_find_t and contains_count_t ensures that the second overload is a better match. The decltype-based SFINAE eliminates the second overload if the container does not support count().

Choragus