12
\$\begingroup\$

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";
}
\$\endgroup\$
  • \$\begingroup\$ Are you strictly looking for c++11 answers or would you be interested in options that would require newer features, such as c++17's if constexpr? \$\endgroup\$ – Josiah Apr 17 '18 at 7:29
  • \$\begingroup\$ hi @Josiah ... yes that would be great if it has c++17 features \$\endgroup\$ – MORTAL Apr 17 '18 at 7:37
  • 3
    \$\begingroup\$ Did you mean to tag this c++14? (auto return type deduction, trait helpers) \$\endgroup\$ – Snowhawk Apr 17 '18 at 7:57
  • 2
    \$\begingroup\$ That came up already: contains() algorithm for std::vector \$\endgroup\$ – Deduplicator Apr 17 '18 at 10:07
  • \$\begingroup\$ It's The C++ Standard Library, explicitly not the STL. \$\endgroup\$ – Pharap Apr 17 '18 at 16:45
15
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ I must be one of the few people who vastly prefers overloading to if constexpr for readability. \$\endgroup\$ – Konrad Rudolph Apr 17 '18 at 16:50
  • \$\begingroup\$ @KonradRudolph, I agree with you, but only when number of cases is > 2. Tag dispatch rarely adds readability, if the template argument/function argument name is not chosen well. \$\endgroup\$ – Incomputable Apr 17 '18 at 16:56
  • \$\begingroup\$ @KonradRudolph It depends on the case. IMO, overloading is much more readable when what you are doing is overloading functions. if constexpr is much more readable when what you are doing is if constexpr. Basically, if there's an order with which you want to try functions in, if constexpr is often more readable, but sometimes boost::hana::overload_linearly is nicer. \$\endgroup\$ – Justin Apr 17 '18 at 17:55
10
\$\begingroup\$

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).

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. So instead of using void_t = void;, use template <typename... Ts> struct voider { using type = void; }; template <typename... Ts> using void_t = voider<Ts...>::type; \$\endgroup\$ – Snowhawk Apr 17 '18 at 19:03
  • \$\begingroup\$ @Snowhawk, done, thanks. By the way, are changes already applied? \$\endgroup\$ – Incomputable Apr 17 '18 at 19:09
  • \$\begingroup\$ C++17 addressed them. \$\endgroup\$ – Snowhawk Apr 17 '18 at 19:25
  • \$\begingroup\$ See Possible Implementation at cppreference. \$\endgroup\$ – JDługosz Apr 18 '18 at 5:38
10
\$\begingroup\$

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>());
}
\$\endgroup\$
  • \$\begingroup\$ i did used the detection idiom but it getting long .. here my attempt of detection idiom gist.github.com/MORTAL2000/… \$\endgroup\$ – MORTAL Apr 17 '18 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.