"contains" function for STL containers

Question

I have made a simple program that tests if the given element exists in any STL container. The program tests if the container has a find member function. It will use it if it does. Otherwise, it will call the STL find function instead. I would like to know how I can improve it further?

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

template <typename C> decltype(std::declval<C>().find(0), std::true_type{}) test(int);
template <typename C> std::false_type test(...);
template <typename C> using has_find = decltype(test<C>(0));

template <bool B, typename T, typename F>
std::enable_if_t<std::integral_constant<bool, B>::value, T>
conditional(T&& t, F&&)
{
    return std::forward<T>(t);
}

template <bool B, typename T, typename F>
std::enable_if_t<!std::integral_constant<bool, B>::value, F>
conditional(T&&, F&& f)
{
    return std::forward<F>(f);
}

template <typename C, typename T>
auto contains(const C& container, const T& key)
{
    static auto first = [] (auto&& c, auto&& k)
    {
        return c.end() != c.find(k);
    };

    static auto second = [] (auto&& c, auto&& k)
    {
        return c.end() != std::find(c.begin(), c.end(), k);
    };

    auto op = conditional<has_find<C>::value>(first, second);

    return op(container, 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";
}

Answer 1

If you like new features, and even experimental features, you can make your code a lot cleaner.

Concepts

A lot of those arcane SFINAE techniques will be obsolete once concepts are out, and concepts are already available in an experimental state with the last versions of gcc (enable them with the -fconcepts option):

template <typename Container, typename Value>
concept bool HasFindFunction = requires(Container c, Value v) {
    c.find(v);
};

... and that's it for your trait.

if constexpr

To specialize the contains function, you can rely on C++17 if constexpr. It's a compile-time if, in which only the chosen branch has to be well-formed. So, here's what you could write:

template <typename Container, typename Value>
auto find(Container&& cont, Value&& val) {
    if constexpr (HasFindFunction<Container, Value>) {
        std::cout << "member find\n";
        return cont.find(val);
        }
    else { 
        std::cout << "algorithm find\n";
        return std::find(std::begin(cont), std::end(cont), val);
    }
}

I replace contains by find, because I find it a pity to make a hard won information (the item position) go to waste. You can then write contains on top of it.

Complete working example (g++ prog.cc -Wall -Wextra -std=gnu++2a -fconcepts)

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

template <typename Container, typename Value>
concept bool HasFindFunction = requires(Container c, Value v) {
    c.find(v);
};

template <typename Container, typename Value>
auto find(Container&& cont, Value&& val) {
    if constexpr (HasFindFunction<Container, Value>) {
        std::cout << "member find\n";
        return cont.find(val);
        }
    else {
        std::cout << "algorithm find\n";
        return std::find(std::begin(cont), std::end(cont), val);
    }
}

template <typename Container, typename Value>
auto contains(Container&& c, Value&& v) {
    return std::end(c) != find(c, std::forward<Value>(v));
}

int main() {
    std::map<int, int> map;
    std::vector<int> vector;

    find(map, 5);
    contains(vector, 5);
}

Answer 2

Wrong usage

One shouldn't be afraid of manual SFINAE, but one should also use it appropriately. I'm in no way professional in this question, but guidelines are roughly the following for SFINAE and tag based dispatch (prefixing/postfixing input arguments with the argument one wants to disambiguate):

• SFINAE

  Specialize for some case. Making more than one specialization often becomes painful.

• Tag based dispatch

  Choose one and only one alternative over the others. (This is the case in question)

Rewrite:

template <typename T, typename F>
T&& conditional(std::true_type, T&& t, F&& f)
{
    return std::forward<T>(t);
}

template <typename T, typename F>
F&& conditional(std::false_type, T&& t, F&& f)
{
    return std::forward<F>(f);
}

Not all general practices are good

Although one letter template arguments are used often, it is not a good idea to write them everywhere, especially in multiple argument templates. Choose descriptive names (they're not necessarily long, but almost never one letter).

Also, by naming it correctly, one also implicitly names a concept. May be somebody will come up with clang-tidy solution to automate transition from manual SFINAE to concepts, but the chances are almost zero due to complexity.

Hide unnecessary stuff

test functions are in global scope. They have high chances to cause name collision. It is better to hide them in a struct and expose only has_find.

Not so useful

One needs to know what arguments member find() is callable with in order to determine if it has one. This is quite big problem if additional restrictions are not imposed on the Container.

---

Side note: some people postfix tag in tagged dispatch. It turns to be a problem with variadic templates, but are a boon in case one can infer it from the arguments.

---

Classic detection idiom (partially broken, read below)

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

template <typename Container, typename = void_t<>>
struct has_member_find : std::false_type {};

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

By @Snowhawk:

The classic detection algorithm showed a defect in the standard that unused params in an alias template were not guaranteed to ensure SFINAE and could possibly be ignored. Instead use:

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

template <typename... Ts> using void_t = voider<Ts...>::type;

The code above is valid only after C++17, otherwise it is unspecified (both versions).

Answer 3

Rather than writing your detection from scratch, use the detection idiom, either in the compiler's header if you have it, or a copy of the published definitions otherwise.

template<typename T, typename K>
using has_find_t = decltype(std::declval<T&>().find(std::declval<K&>()));

or something like that, modulo typos.

Then, instead of having the auto op indirection in the code where you want to find something, hide that in a smart find function. You are exposing the conditional mechanism to the caller and at the same time limiting it to just this pair of functions.

That is, write two versions of your own find as a non-member, and they forward to the member or the std::find_if as determined. (Or if in C++17, one function with if constexpr in the body.)

Then you are doing what you hope the standard library vendor had already done for you: provide optimal special implementations for specific containers. Only it works for your own collections now, presuming the existence of a find member means the right thing.

// tagged versions

template<typename Container, typename Key)
auto find (Container&& c, Key&& k, std::true_type)
{
return c.find(k);  // not showing all the perfect forwarding stuff
}

template<typename Container, typename Key)
auto find (Container&& c, Key&& k, std::false_type)
{
return std::find_if(c.begin(), c.end(), k);  // not showing all the perfect forwarding stuff
}

// dispatching form

template<typename Container, typename Key)
auto smart_find (Container&& c, Key&& k)
{
return find (c, k, is_detected_t<has_find_t,Container,Key>());
}