Petaflop: templates

Showing posts with label templates. Show all posts

Thursday, 1 May 2014

Solving SFINAE issues when you have overlapping conditions

Sometimes we have function templates which we want to use SFINAE on, but some of them have overlapping conditions, creating ambiguity

template<unsigned N, enable_if_t<is_multiple_of<N, 3>>...>
void print_fizzbuzz(){ std::cout << "fizz\n"; }

template<unsigned N, enable_if_t<is_multiple_of<N, 5>>...>
void print_fizzbuzz(){ std::cout << "buzz\n"; }

template<unsigned N, enable_if_t<is_multiple_of<N, 15>>...> // this is ambiguous
void print_fizzbuzz(){ std::cout << "fizzbuzz\n"; }

By using derived-to-base conversions we can create a total ordering for selecting SFINAE overloads.

That is, we resolve ambiguity by using the following inheritance hierarchy:

template<unsigned I> struct choice : choice<I+1>{};

choice<0> has a higher ordering than choice<1>, and we can therefore use choice<0> as a function parameter to make is_multiple_of<N, 15> a better overload, thereby resolving the ambiguity.

The complete fizzbuzz example:

#include <type_traits>

#include <iostream>

template<class C, class T = int>
using enable_if_t = typename std::enable_if<C::value, T>::type;

template<int N, int M>
struct is_multiple_of : std::integral_constant<bool, N % M == 0>{};

//-------------------------------

template<unsigned I> struct choice : choice<I+1>{};
template<> struct choice<10>{}; // suitably high terminating condition

struct otherwise{ otherwise(...){} };

struct select_overload : choice<0>{};

//-------------------------------

template<unsigned N, enable_if_t< is_multiple_of<N, 15> >...>
void print_fizzbuzz(choice<0>) { std::cout << "fizzbuzz\n"; }

template<unsigned N, enable_if_t< is_multiple_of<N, 3> >...>
void print_fizzbuzz(choice<1>) { std::cout << "fizz\n"; }

template<unsigned N, enable_if_t< is_multiple_of<N, 5> >...>
void print_fizzbuzz(choice<2>) { std::cout << "buzz\n"; }

template<unsigned N>
void print_fizzbuzz(otherwise){ std::cout << N << "\n"; }

template<unsigned N = 1>
void do_fizzbuzz()
{
print_fizzbuzz<N>(select_overload{});
do_fizzbuzz<N+1>();
}

template<>
void do_fizzbuzz<50>()
{
print_fizzbuzz<50>(select_overload{});
}

//-------------------------------

int main()
{
do_fizzbuzz();
}

This excellent technique by Xeo, as described here

Using function template default parameters to elegantly create SFINAE overloads

Having read Remastered enable_if, some implementation was left as an exercise for the reader.

The article explains how to make use of function template default parameters to elegantly create SFINAE overloads.

Below is my implementation.

#include <iostream>
#include <type_traits>

// true iff all conditions ::values are true
template <typename Head, typename... Tail>
struct all
{
static constexpr bool value = Head::value && all<Tail...>::value;
};
template <typename Head>
struct all<Head>
{
static constexpr bool value = Head::value;
};
//---------------------------------

// scoped enum to allow for differentiation between enable/disable
namespace detail { enum class enabler {}; }

template <typename... Condition>
using enable_if_t = typename std::enable_if<all<Condition...>::value, detail::enabler>::type;

template <typename... Condition>
using disable_if_t = typename std::enable_if<!all<Condition...>::value>::type;

//---------------------------------

// example function showing SFINAE overloads
template <typename T,
enable_if_t< std::is_arithmetic<T>
, std::is_integral<T>
>...>
T twice(T t)
{
return 2*t;
}
template <typename T,
disable_if_t< std::is_arithmetic<T>
, std::is_integral<T>
>...>
T twice(T t)
{
return t + t;
}
//---------------------------------

int main()
{
std::cout << twice(5) << std::endl;
std::cout << twice(std::string("Hello world")) << std::endl;
return 0;
}

Tuesday, 29 April 2014

Exiting recursive function templates without using helper class templates and partial specialisation

Contrived examples follow, but they serve to illustrate partial specialisation of class templates vs exiting recursive function templates using a branch.

The old way: use a helper class template, partially specialise it with the recursion exit case, and call a static function on this class template from a function template:

#include <iostream>

// helper class template
template<typename T, unsigned idx>
struct foo_impl
{
static void fn(T t)
{
std::cout << t << " " << idx << std::endl;
foo_impl<T, idx - 1>::fn(t); // recursively call fn
}
};

// partial specialisation of helper class template for exit case
template<typename T>
struct foo_impl<T, 0>
{
static void fn(T) {} // do nothing exit case
};

// function template which uses helper class templates
template<unsigned idx, typename T>
void foo(T t)
{
foo_impl<T, idx>::fn(t);
}

int main()
{
foo<5>("Hello world");
return 0;
}

The new way: have the special case branch in the function template itself, and recursively call the function template from itself.

To prevent the compiler from barfing when instantiating the recursive path, the trick is to recursively call the function template with the same parameters for the special case. Even though this code path will never actually execute, it is needed so the compiler can parse the template.

#include <iostream>

template<unsigned idx, typename T>
void foo(T t)
{
if (idx == 0) // special exit case
return;
std::cout << t << " " << idx << std::endl;

// recursively call the function
foo<idx - (idx ? 1 : 0)>(t); // note recursion returns itself in special exit case (code path will actually never be reached)
}

int main()
{
foo<5>("Hello world");
return 0;
}

Tuesday, 5 March 2013

SFINAE decltype comma operator trick

Note the decltype statement below contains 2 elements: reserve and bool: decltype(t.reserve(0), bool())

This is a trick using SFINAE and the comma operator: SFINAE will cull the function if 'reserve' doesn't exist and the comma operator will mean the result type of the decltype statement will be a bool.

This means we can easily implement an 'enable_if'esque statement to check for the existence of a member function called 'reserve'

// Culled by SFINAE if reserve does not exist or is not accessible
template <typename T>
constexpr auto has_reserve_method(T& t) -> decltype(t.reserve(0), bool()) { return true; }

// Used as fallback when SFINAE culls the template method
constexpr bool has_reserve_method(...) { return false; }

template <typename T, bool b>
struct Reserver
{
static void apply(T& t, size_t n) { t.reserve(n); }
};

template <typename T>
struct Reserver <T, false>
{
static void apply(T& t, size_t n) {}
};

template <typename T>
bool reserve(T& t, size_t n)
{
Reserver<T, has_reserve_method(t)>::apply(t, n);
return has_reserve_method(t);
}

(Thanks to Matthieu M for his post on stackoverflow here)

--------------------------

Another implementation which has 2 SFINAE functions to access a member int, items_n or items_c, ultimately falling back to 0 if neither exist

// culled by SFINAE if items_n does not exist
template<typename T>
constexpr auto has_items_n(int) -> decltype(std::declval<T>().items_n, bool())
{
return true;
}
// catch-all fallback for items with no items_n
template<typename T> constexpr bool has_items_n(...)
{
return false;
}
//-----------------------------------------------------

template<typename T, bool>
struct GetItemsN
{
static int value(T& t)
{
return t.items_n;
}
};
template<typename T>
struct GetItemsN<T, false>
{
static int value(T&)
{
return 0;
}
};
//-----------------------------------------------------

// culled by SFINAE if items_c does not exist
template<typename T>
constexpr auto has_items_c(int) -> decltype(std::declval<T>().items_c, bool())
{
return true;
}
// catch-all fallback for items with no items_c
template<typename T> constexpr bool has_items_c(...)
{
return false;
}
//-----------------------------------------------------

template<typename T, bool>
struct GetItemsC
{
static int value(T& t)
{
return t.items_c;
}
};
template<typename T>
struct GetItemsC<T, false>
{
static int value(T&)
{
return 0;
}
};
//-----------------------------------------------------

template<typename T>
int get_items(T& t)
{
if (has_items_n<T>(0))
return GetItemsN<T, has_items_n<T>(0)>::value(t);
if (has_items_c<T>(0))
return GetItemsC<T, has_items_c<T>(0)>::value(t);
return 0;
}
//-----------------------------------------------------

When you have two candidates function templates, and want to use SFINAE to choose between them, sometimes you may have a parameter for which both overloads will work.

To prevent ambiguity you can favour one overload over the other.

By using implicit type casting we can make one overload a better match, therefore resolving the ambiguity.

#include <iostream>

template<class T>
auto serialize_imp(std::ostream& os, T const& obj, int)
-> decltype(os << obj, void())
{
os << obj;
}

template<class T>
auto serialize_imp(std::ostream& os, T const& obj, long)
-> decltype(obj.stream(os), void())
{
obj.stream(os);
}

template<class T>
auto serialize(std::ostream& os, T const& obj)
-> decltype(serialize_imp(os, obj, 0), void())
{
serialize_imp(os, obj, 0);
}

struct X
{
void stream(std::ostream&) const
{
std::cout << "\nX::stream()\n";
}
};

int main(){
serialize(std::cout, 5);
X x;
serialize(std::cout, x);
}

Here the ostream operator overload will be chosen when an object with both operator<< and stream() because by passing in 0 for the 3rd parameter of serialize_imp, we choose the overload with the int parameter, as 0 is an int, whereas the long parameter would require an implicit cast.

(Thanks to Xeo for his post on stackoverflow here)

Petaflop