Re: [lmi] Difficulty writing a generic contains() function template

[Vadim Zeitlin]

On Tue, 04 May 2010 17:08:08 +0000 Greg Chicares <address@hidden> wrote:

GC> I'm stuck here ['icon_monger.cpp', line 45]:
GC> 
GC>     // SOMEDAY !! Write a "contains.hpp" header that implements this
GC>     // function for every standard container as well as std::string.
GC>     // Rationale: this usage represents half of our find() calls, and
GC>     // the idiom is verbose.
GC>     template<typename Key, typename Compare, typename Allocator>
GC>     bool contains(std::set<Key,Compare,Allocator> const& c, Key const& k)
GC>     {
GC>         return c.end() != c.find(k);
GC>     }
GC> 
GC> What's the best way to proceed?

 I think the best would be to check directly for find() method existence
instead of relying on key_type. IOW do something like this:

template<typename T>
bool contains(T const& container, typename T::key_type const& element,
              boost::enable_if< has_find_method<T>::value >::type * = 0)
{
    return container.end() != container.find(element);
}

Unfortunately the definition of has_find_method is tricky but it can be
done, see http://www.rsdn.ru/forum/cpp/2720363.aspx for example:

        template <class T>
        struct has_find_method {
            struct BaseFind { void find(); };
            struct Base : T, BaseFind {};

            template <typename FP, FP fp> struct Tester;

            template <class U>
            static char test(U *, Tester<void (BaseFind::*)(), &U::find>* = 0);
            static long test(...);

            static const bool value = sizeof(test(static_cast<Base *>(0))) != 1;
        };


 However this still leaves us with a problem with std::string. We could add
an extra disable_if<> to exclude it from the above overload but it starts
getting really ugly so IMHO it's easier to just provide separate overloads
for std::string (or std::basic_string but LMI doesn't use wstring anyhow).

 All in all, the attached version works for me with g++ 4.3 and MSVC 9.
And here is the diff with the changes:

--- generic_find.orig.cpp       2010-05-05 13:02:07.000000000 +0200
+++ generic_find.cpp    2010-05-05 15:33:58.000000000 +0200
@@ -4,30 +4,47 @@
 #include <set>
 #include <string>
 #include <vector>
+#include <boost/utility/enable_if.hpp>

-  // If a class has 'npos', assume it should behave like std::string.
-template<typename T>
-bool contains(T const& container, T const& element, typename T::size_type = 
T::npos)
+template <class T>
+struct has_find_method {
+    struct BaseFind { void find(); };
+    struct Base : T, BaseFind {};
+
+    template <typename FP, FP fp> struct Tester;
+
+    template <class U>
+    static char test(U *, Tester<void (BaseFind::*)(), &U::find>* = 0);
+    static long test(...);
+
+    static const bool value = sizeof(test(static_cast<Base *>(0))) != 1;
+};
+
+  // std::string has find() but it doesn't return an iterator so treat it
+  // specially
+bool contains(std::string const& container, std::string const& element)
 {
-    return T::npos != container.find(element);
+    return std::string::npos != container.find(element);
 }

 template<typename T>
-bool contains(T const& container, typename T::traits_type::char_type const* 
element)
+bool contains(std::string const& container, char const* element)
 {
-    return T::npos != container.find(element);
+    return std::string::npos != container.find(element);
 }

-  // If a class has 'key_type', assume it should behave like an associative 
container.
+  // If a class has find() method, assume it does the right thing.
 template<typename T>
-bool contains(T const& container, typename T::key_type const& element)
+bool contains(T const& container, typename T::key_type const& element,
+              typename boost::enable_if< has_find_method<T> >::type * = 0)
 {
     return container.end() != container.find(element);
 }

   // Otherwise, std::find() is the best we can do.
 template<typename T>
-bool contains(T const& container, typename T::value_type const& element)
+bool contains(T const& container, typename T::value_type const& element,
+              typename boost::disable_if< has_find_method<T> >::type * = 0)
 {
     return container.end() != std::find(container.begin(), container.end(), 
element);
 }


 Whether it's really better than just defining a traits type and
specializing it for all the container types is open to discussion. Notice
that it took me more than half an hour to get this right...

 Regards,
VZ
#include <algorithm> // std::find()
#include <cassert>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <boost/utility/enable_if.hpp>

template <class T>
struct has_find_method {
    struct BaseFind { void find(); };
    struct Base : T, BaseFind {};

    template <typename FP, FP fp> struct Tester;

    template <class U>
    static char test(U *, Tester<void (BaseFind::*)(), &U::find>* = 0);
    static long test(...);

    static const bool value = sizeof(test(static_cast<Base *>(0))) != 1;
};

  // std::string has find() but it doesn't return an iterator so treat it
  // specially
bool contains(std::string const& container, std::string const& element)
{
    return std::string::npos != container.find(element);
}

template<typename T>
bool contains(std::string const& container, char const* element)
{
    return std::string::npos != container.find(element);
}

  // If a class has find() method, assume it does the right thing.
template<typename T>
bool contains(T const& container, typename T::key_type const& element,
              typename boost::enable_if< has_find_method<T> >::type * = 0)
{
    return container.end() != container.find(element);
}

  // Otherwise, std::find() is the best we can do.
template<typename T>
bool contains(T const& container, typename T::value_type const& element,
              typename boost::disable_if< has_find_method<T> >::type * = 0)
{
    return container.end() != std::find(container.begin(), container.end(), 
element);
}

int main()
{
    std::string s("etaoin shrdlu");
    std::string t("alpha omega");
    assert( contains(s, s));
    assert(!contains(s, t));
    assert( contains(s, "eta"));
    assert(!contains(s, "epsilon"));
#if 1 // It compiles if I change this to '#if 0'...
    std::set<std::string> u;
    u.insert("one");
    assert( contains(u, "one"));
    assert(!contains(u, "two"));
#endif // 1
    std::map<std::string, int> m;
    m["one"] = 1;
    assert( contains(m, "one"));
    assert(!contains(m, "two"));

    std::vector<double> v;
    v.push_back(3.14);
    assert( contains(v, 3.14));
    assert(!contains(v, 0.00));
}