4

I'm writing a contains() utility function and have come up with this. My question is: Is there a nicer way to select the right function to handle the call?

template <class Container>
inline auto contains(Container const& c,
  typename Container::key_type const& key, int) noexcept(
    noexcept(c.end(), c.find(key))) ->
  decltype(c.find(key), true)
{
  return c.end() != c.find(key);
}

template <class Container>
inline auto contains(Container const& c,
  typename Container::value_type const& key, long) noexcept(
    noexcept(c.end(), ::std::find(c.begin(), c.end(), key))
)
{
  auto const cend(c.cend());

  return cend != ::std::find(c.cbegin(), cend, key);
}

template <class Container, typename T>
inline auto contains(Container const& c, T const& key) noexcept(
  noexcept(contains(c, key, 0))
)
{
  return contains(c, key, 0);
}
user1095108
  • 14,119
  • 9
  • 58
  • 116

4 Answers4

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

this takes a template and arguments, and tells you if you can apply it.

template<class T, class...Args>
using dot_find_r = decltype(std::declval<T>().find(std::declval<Args>()...));

template<class T, class...Args>
constexpr can_apply<dot_find_r, T, Args...> can_dot_find{};

we now tag dispatch on myfind:

template<class C>
using iterator = decltype( ::std::begin(std::declval<C>()) );

namespace details {
  template<class Container, class Key>
  iterator<Container const&> myfind(
    std::false_type can_dot_find,
    Container const& c,
    Key const& key
  )
  noexcept(
    noexcept( ::std::find(::std::begin(c), ::std::end(c), key) )
  )
  {
    return ::std::find( ::std::begin(c), ::std::end(c), key );
  }

  template <class Container, class Key>
  iterator<Container const&> myfind(
    std::true_type can_dot_find,
    Container const& c,
    Key const& key
  ) noexcept(
    noexcept( c.find(key) )
  )
  {
    return c.find(key);
  }
}
template<class Container, class Key>
iterator<Container const&> myfind(
  Container const& c,
  Key const& k
) noexcept (
  details::myfind( can_dot_find<Container const&, Key const&>, c, k )
)
{
  return details::myfind( can_dot_find<Container const&, Key const&>, c, k );
}
template<class Container, class Key>
bool contains(
  Container const& c,
  Key const& k
) noexcept (
  noexcept( ::std::end(c), myfind( c, k ) )
)
{
  return myfind(c, k) != ::std::end(c);
}

As a bonus, the above version works with raw C style arrays.

The next enhancement I'd do would be an auto-ADL std::begin to make begin extensions work in the non-dot_find case.

My personal equivalent returns a std::optional<iterator> of the appropriate type. This both provides a quick "is it there", and gives easy access to the iterator if not not there.

if (auto oit = search_for( container, key )) {
  // use *oit here as the iterator to the element, guaranteed not to be `end`
}

or

if (search_for( container, key )) {
  // key was there
}

but that is neither here nor there.

Walter
  • 44,150
  • 20
  • 113
  • 196
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
5

For the record, you could write:

#include "magic.h"

template <typename T, typename... Us>
using has_find = decltype(std::declval<T>().find(std::declval<Us>()...));

template <class Container, typename T>
auto contains(const Container& c, const T& key)
{
    return static_if<detect<has_find, decltype(c), decltype(key)>{}>
    (
        [&] (auto& cont) { return cont.end() != cont.find(key); },
        [&] (auto& cont) { return cont.end() != std::find(cont.begin(), cont.end(), key); }
    )(c);
}

where magic.h contains:

#include <type_traits>

template <bool> struct tag {};

template <typename T, typename F>
auto static_if(tag<true>, T t, F f) { return t; }

template <typename T, typename F>
auto static_if(tag<false>, T t, F f) { return f; }

template <bool B, typename T, typename F>
auto static_if(T t, F f) { return static_if(tag<B>{}, t, f); }

template <bool B, typename T>
auto static_if(T t) { return static_if(tag<B>{}, t, [](auto&&...){}); }

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

template <typename AlwaysVoid, template <typename...> class Operation, typename... Args>
struct detect_impl : std::false_type {};

template <template <typename...> class Operation, typename... Args>
struct detect_impl<void_t<Operation<Args...>>, Operation, Args...> : std::true_type {};

template <template <typename...> class Operation, typename... Args>
using detect = detect_impl<void, Operation, Args...>;

DEMO

Piotr Skotnicki
  • 46,953
  • 7
  • 118
  • 160
  • I'd replace `template struct tag{}` with `template using bool_t = std::integral_constant;` or somesuch myself. – Yakk - Adam Nevraumont May 27 '16 at 17:18
  • I like `static_if` -- where is that from? Don't you want perfect forwarding for that, though (in general, not just in this example)? – Walter May 27 '16 at 17:29
  • @Walter `static_if` implemented by means of lambda expressions appears often on stackoverflow and isocpp.org (it's also in the proposal for the [`constexpr_if`](http://open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0128r1.html)). I could add perfect forwarding, but that would make code less readable. and I prefer when function objects are lightweight (the standard library also takes them *by value* anyway) – Piotr Skotnicki May 27 '16 at 17:53
1

So you want to call c.find if possible else std::find. But also being wary of type ambiguity as in std::set.

Here is the code to solve that (with the verbose and micro-optimization removed in favor of readability):

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <type_traits>
#include <set>
#include <cstdarg>

using namespace std;

template <typename T, typename Ret>
struct dummy {
    typedef Ret type;
};

template <class Container>
auto contains(const Container &c, typename Container::key_type const &key) ->
    typename dummy<decltype(c.find(key)), bool>::type {
    cout << "c.find" << endl;

    return c.end() != c.find(key);
}

template <class Container, typename ...T>
 typename std::enable_if<sizeof...(T)==1, bool>::type contains(const Container &c, const T&... args) {
    typename Container::value_type const &val = std::get<0>(std::tuple<const T&...>(args...));
    cout << "std::find" << endl;

    return c.cend() != find(c.cbegin(), c.cend(), val);
}

int main() {
    vector<int> v = {1,2,3};
    cout << contains(v,4) << contains(v,2) << endl;

    map<int, int> m;
    m[1] = 1;
    m[2] = 2;
    m[3] = 3;
    cout << contains(m,4) << contains(m,2) << endl;

    set<int> s;
    cout << contains(s,4) << contains(s,2) << endl;

    return 0;
}

What I did:

  • I made the first contains function dependent on c.find() being callable. When it's not, the compiler doesn't see the function, and no issues arise
  • I resolved ambiguity when key_type and value_type are the same, by introducing the function using std::find with its second mandatory argument as a variadic template. I also forced the variadic template of being of size 1.

If you just assume that key_type existing means that container.find exists as in OP, then you can simplify the code and remove the dummy structure:

template <class Container>
bool contains(const Container &c, typename Container::key_type const &key)
{
    return c.end() != c.find(key);
}

template <class Container, typename ...T>
 typename std::enable_if<sizeof...(T)==1, bool>::type contains(const Container &c, const T&... args) {
    typename Container::value_type const &val = std::get<0>(std::tuple<const T&...>(args...));
    return c.cend() != find(c.cbegin(), c.cend(), val);
}

Instead of having to resolve ambiguity that way, it's possible to disable the second function altogether if Container::find does exist. This and That answer both show different ways of knowing so. Then using std::enable_if<! (Does Container have the find method?) , bool>::type as the return type of the second function will work.

Community
  • 1
  • 1
coyotte508
  • 9,175
  • 6
  • 44
  • 63
  • I don't get why you use `...`. it makes no difference – Piotr Skotnicki May 27 '16 at 15:09
  • @PiotrSkotnicki Functions can't be overloaded on template parameters or return types only: after the compiler instantiates both function templates, they would both have the same declaration. So the `...` is there as a simple way to overload the functions (could also be an empty tag with a default parameter) – KABoissonneault May 27 '16 at 17:36
  • @KABoissonneault these are already different overloads, since one takes `Container::key_type`, and another takes `Container::value_type` – Piotr Skotnicki May 27 '16 at 17:40
  • @PiotrSkotnicki Right! Didn't notice that subtle difference. But can't these typedefs refer to the same type, sometimes? Like a `map`? – KABoissonneault May 27 '16 at 17:44
  • @KABoissonneault `map::value_type` is `std::pair`, while `map::key_type` is `int` – Piotr Skotnicki May 27 '16 at 17:45
  • @PiotrSkotnicki Right... always mix up `value_type` and `mapped_type` – KABoissonneault May 27 '16 at 17:50
  • @KABoissonneault they could be equal for `std::set`, but still, `...` doesn't help the compiler pick the right overload – Piotr Skotnicki May 27 '16 at 18:05
  • @PiotrSkotnicki Edited my answer. As for why I used `...` previously, it's because of a fuzzy memory wrongly interpreted, actually the correct principle is used in my edited answer with variadic templates instead. – coyotte508 May 28 '16 at 03:08
1

since find is exist in associative containers then you can explicitly make them as true types.

meta-functions:

template <class> struct has_find_impl:std::false_type{};
template <class T, class... Args> struct has_find_impl<std::set<T, Args...>>:std::true_type{};
template <class T, class... Args> struct has_find_impl<std::map<T, Args...>>:std::true_type{};
template <class T, class... Args> struct has_find_impl<std::multiset<T, Args...>>:std::true_type{};
template <class T, class... Args> struct has_find_impl<std::multimap<T, Args...>>:std::true_type{};
template <class T> using has_find = has_find_impl<typename std::decay<T>::type>;

and use it like so:

template <class Container>
bool contains_impl(const Container& c, const typename Container::key_type& key, std::true_type)
{
    return c.find(key) != c.cend();
}

template <class Container>
 bool contains_impl(const Container& c, typename Container::const_reference key, std::false_type)
{
    return std::find(c.cbegin(), c.cend(), key) != c.cend();
}

template <class Container, class T>
bool contains(const Container& c, const T& key)
{
    return contains_impl(c, key, has_find<Container>{});
}

or used it with SFINAE. here a complete example:

#include <iostream>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <vector>
#include <array>
#include <type_traits>


template <class> struct has_find_impl:std::false_type{};
template <class T, class... Args> struct has_find_impl<std::set<T, Args...>>:std::true_type{};
template <class T, class... Args> struct has_find_impl<std::map<T, Args...>>:std::true_type{};
template <class T, class... Args> struct has_find_impl<std::multiset<T, Args...>>:std::true_type{};
template <class T, class... Args> struct has_find_impl<std::multimap<T, Args...>>:std::true_type{};
template <class T> using has_find = has_find_impl<typename std::decay<T>::type>;


template <class Container>
typename std::enable_if<has_find<Container>::value, bool>::type
contains_impl(const Container& c, const typename Container::key_type& key)
{
    return c.find(key) != c.cend();
}

template <class Container>
typename std::enable_if<!has_find<Container>::value, bool>::type
contains_impl(const Container& c, typename Container::const_reference key)
{
    return std::find(c.cbegin(), c.cend(), key) != c.cend();
}

template <class Container, class T>
bool contains(const Container& c, const T& key)
{
    return contains_impl(c, key);
}

int main()
{
    std::cout << std::boolalpha;

    std::array<int, 3> a = {{ 1, 2, 3 }};
    std::cout << contains(a, 0) << "\n";
    std::cout << contains(a, 1) << "\n\n";

    std::vector<int> v = { 1, 2, 3 };
    std::cout << contains(v, 0) << "\n";
    std::cout << contains(v, 1) << "\n\n";

    std::set<int> s = { 1, 2, 3 };
    std::cout << contains(s, 0) << "\n";
    std::cout << contains(s, 1) << "\n\n";

    std::map<int, int> m = { { 1, 1}, { 2, 2}, { 3, 3} };
    std::cout << contains(m, 0) << "\n";
    std::cout << contains(m, 1) << "\n\n";
}
MORTAL
  • 383
  • 2
  • 10