Let's consider a hypothetical C++ template function which accepts, as a template parameter, some type of container, which it will search for a particular value. It will return true if that value is found and false otherwise. A basic implementation might look like this:
template <typename T, typename C>
bool exists(const C& cont, const T& value)
{
return std::find(cont.begin(), cont.end(), value) != cont.end();
}
The STL's find function is a straightforward linear search. What if the container type is a map? A binary search would be much more effective. We could handle this by providing an explicit specialization for maps:
template <typename K, typename T>
bool exists(const std::map<K, T>& cont, const K& key)
{
return cont.find(key) != cont.end();
}
That works for map, but what about set, multimap, multiset, unordered_map, unordered_set, and so forth? Trying to anticipate all of the possible container types is generally not feasible.
What we would like to do would be to provide one specialization that can handle all containers which provide a find() method with a similar signature to that of std::map.
A bit of Googling found this solution by Aleksey Gurtovoy posted on the boost mailing list, which works in pre-C++11 compilers:
typedef char (&no_tag)[1];
typedef char (&yes_tag)[2];
template< typename T > no_tag has_member_foo_helper(...);
template< typename T >
yes_tag has_member_foo_helper(int, void (T::*)() = &T::foo);
template< typename T >
struct has_member_foo
{
BOOST_STATIC_CONSTANT(bool
, value = sizeof(has_member_foo_helper<T>(0)) == sizeof(yes_tag)
);
};
struct my {};
struct her { void foo(); };
int main()
{
BOOST_STATIC_ASSERT(!has_member_foo<my>::value);
BOOST_STATIC_ASSERT(has_member_foo<her>::value);
return 0;
}
We can generalize this into a macro which can be used to generate has_xxx_member metafunctions for methods marked const and taking one parameter:
#define DEF_HAS_MEMBER_CONST_1(X) \
template <typename T, typename R, typename A> \
struct has_##X##_method_const \
{ \
typedef char (&no_tag)[1]; \
typedef char (&yes_tag)[2]; \
template <typename T_, typename R_, typename A_> \
static no_tag test(...); \
template <typename T_, typename R_, typename A_> \
static yes_tag test(int, R_ (T_::*)(A_) const = &T_::##X); \
static const bool value = \
sizeof(test<T, R, A>(0)) == sizeof(yes_tag); \
};
DEF_HAS_MEMBER_CONST_1(find)
The idea is that if T::foo doesn't exist, SFNAE will cause the no_tag function to be instantiated. Unfortunately, possibly due to a bug in Visual C++ 2010, this doesn't happen. While it correctly evaluates to true when a foo() method is available, it causes a compiler error in all other cases:
error C2065: 'foo' : undeclared identifier
I believe the correct behavior would be for that error to trigger SFNAE instead of preventing compilation. In any case, this solution isn't usable.
There are a few other problems with this approach. It requires us to know in advance the return value - for this use case, that's no problem, but for others it can be a dealbreaker. It also requires us to specific the cv-qualifiers on the method.
In compilers implementing partial C++11 support (specifically, decltype) a more robust solution is possible:
#define DEF_HAS_METHOD_1(x) \
template <typename T, typename A> \
struct has_##x##_method \
{ \
typedef char (&yes_tag)[1]; \
typedef char (&no_tag)[2]; \
template <typename U> \
static yes_tag test(U&&, decltype(declval<U>().##x(declval<A>()))* dummy = 0); \
static no_tag test(...); \
static const bool value = sizeof(test(declval<T>())) == sizeof(yes_tag); \
};
DEF_HAS_METHOD_1(find)
Note: if declval is available in your STL (it's missing in VC++2010), you'll want to add:
using std::declval;
Otherwise, add:
template <typename T> static typename boost::add_rvalue_reference<T>::type declval();
This implementation has a few advantages over the earlier one. It's not necessary to specify the return type, or be extremely specific about the parameter types. If the actual method parameters are implicitly convertible from the type parameters to has_xxx_method, it will match.
Armed with this implementation, we can now implement our specializations:
template <typename T, typename U>
typename boost::disable_if<has_find_method<T, const U&>, bool>::type
exists(const T& collection, const U& value)
{
std::cout << "Using global find" << std::endl;
return std::find(collection.cbegin(), collection.cend(), value) != collection.cend();
}
template <typename T, typename U>
typename boost::enable_if<has_find_method<T, const U&>, bool>::type
exists(const T& collection, const U& value)
{
std::cout << "Using method find" << std::endl;
return collection.find(value) != collection.cend();
}
Note that it's necessary to disable the first specialization when the find method is available, otherwise both specializations would be active and the call would be ambiguous for any type implementing a find() method.
Let's test it out:
int main()
{
std::vector<int> a;
exists(a, 0);
std::list<int> b;
exists(b, 0);
std::map<int, int> c;
exists(c, 0);
std::multimap<int, int> d;
exists(d, 0);
return 0;
}
And the output:
Using global find Using global find Using method find Using method find
The requirement to explicitly disable the global find specialization can quickly get out of hand if we have a lot of other specializations. One idiom for dealing with this is to wrap all of the requirements in a metafunction. Let's imagine we have three variants: one to use a find() method (which is the highest priority if available), another to use an at() method (second highest priority) and a third to use the global std::find function.
namespace detail
{
template <typename T, typename A>
struct use_find_method
{
static const bool value = has_find_method<T, A>::value;
}
template <typename T, typename A>
struct use_at_method
{
static const bool value = !use_find_method<T, A>::value &&
has_at_method<T, A>::value;
}
template <typename T, typename A>
struct use_global_find
{
static const bool value = !use_find_method<T, A>::value &&
!use_at_method<T, A>::value;
};
}
We can then implement the functions as follows:
template <typename T, typename U>
auto exists(const T& collection, const U& key)
-> typename boost::enable_if<detail::use_find_method<T, U>, bool>::type
{
// ...
}
template <typename T, typename U>
auto exists(const T& collection, const U& key)
-> typename boost::enable_if<detail::use_at_method<T, U>, bool>::type
{
// ...
}
template <typename T, typename U>
auto exists(const T& collection, const U& key)
-> typename boost::enable_if<detail::use_global_find<T, U>, bool>::type
{
// ...
}
Although it doesn't come close to the full power that concepts would have provided, it's still a useful idiom for dealing with multiple specializations which must be selected based on the interface provided by a type.
No comments:
Post a Comment