Have you ever felt the need to perform set theoretic operations on
types? Not really? Me neither, but I thought it’s a fun thing to try
out. So, if you ever feel the need of using type sets, C++11 makes it
quite easy to do so. Especially variadic templates allow for a much more
condensed syntax compared to type list constructs formerly used.
(Disclaimer: This is rather a proof of concept, but maybe somebody comes
up with a useful scenario.)
Let’s start by defining an empty type_set type:
template<typename ... Types> struct type_set; typedef type_set<> empty_set;
As you can see, the struct is just a placeholder for the template
arguments. The empty set is defined using a typedef and an empty
template argument list. The first type set operator we will define is
the element_of operator.
template<typename A, typename B> struct is_element; template<typename A> struct is_element<A, empty_set> { static const bool value = false; }; template<typename A, typename HeadB, typename ... TypesB> struct is_element<A, type_set<HeadB, TypesB...>> { static const bool value = std::is_same<A,HeadB>::value || is_element<A, type_set<TypesB...>>::value; }; template<typename A, typename B> struct is_element { static const bool value = false; static_assert(always_false<A,B>::value, "Second template argument is not a type set"); };
where always_false is defined as follows
template<typename ... T> struct always_false { static const bool value = false; };
The implementation of element_of is just a recursive look up function operating on the type level. The always_false
construct is needed to trigger the static assert and print out a nice
error warning only in the case that the template is instantiated with a
non type set type in the second parameter.
Note, at the moment there is no mechanism that stops us from putting the same type twice into the type set (i.e. type_set<int,int,bool> is a valid type name). I will come to that in a minute. First lets define subset and equality operators:
template<typename A, typename B> struct is_subset; template<typename ... TypesB> struct is_subset<empty_set, type_set<TypesB...>> { static const bool value = true; }; template<typename HeadA, typename ... TypesA, typename ... TypesB> struct is_subset<type_set<HeadA, TypesA...>, type_set<TypesB...>> { static const bool value = is_element<HeadA, type_set<TypesB...>>::value && is_subset<type_set<TypesA...>, type_set<TypesB...>>::value; }; template<typename A, typename B> struct is_subset { static const bool value = false; static_assert(always_false<A,B>::value, "Template arguments are no type sets"); }; template<typename A, typename B> struct is_set_equal { static const bool value = is_subset<A,B>::value && is_subset<B,A>::value; };
These implementations are possibly not the most efficient (we’re speaking about compile time efficiency here), but they stick quite closely to the mathematical definitions of the operators:
and
It should be clear now how a naive implementation of a proper subset (
template<bool condition, typename NewA, typename A> struct cons_set_if; template<typename NewA, typename ... TypesA> struct cons_set_if<true, NewA, type_set<TypesA...>> { typedef type_set<NewA, TypesA...> type; }; template<typename NewA, typename ... TypesA> struct cons_set_if<false, NewA, type_set<TypesA...>> { typedef type_set<TypesA...> type; }; template<bool condition, typename NewA, typename A> struct cons_set_if { typedef void type; static_assert(always_false<NewA,A>::value, "Template arguments are no type sets"); };
Using the conditional cons operator we can reduce a set by eliminating duplicates. The reduce operation uses the cons_set_if operator to recursively add elements to a new type set if the element is not yet contained in this set:
template<typename A> struct reduce_set; template<> struct reduce_set<empty_set> { typedef empty_set type; }; template<typename HeadA, typename ... TypesA> struct reduce_set<type_set<HeadA, TypesA...>> { typedef typename reduce_set<type_set<TypesA...>>::type tail_reduced; typedef typename cons_set_if<!is_element<HeadA, tail_reduced>::value, HeadA, tail_reduced>::type type; }; template<typename A> struct reduce_set { typedef void type; static_assert(always_false<A>::value, "Template argument is not a type set"); };
The implementation of a union
template<typename A, typename B> struct set_union; template<typename ... TypesA, typename ... TypesB> struct set_union<type_set<TypesA...>, type_set<TypesB...>> { typedef typename reduce_set<type_set<TypesA..., TypesB...>>::type type; }; template<typename A, typename B> struct set_union { typedef void type; static_assert(always_false<A,B>::value, "Template arguments are no type sets"); };
The intersection cons_set_if
operator again. By recursively adding only elements that are in the
other set as well, we end up with the intersection of both sets:
template<typename A, typename B> struct set_intersection; template<typename ... TypesB> struct set_intersection<empty_set,type_set<TypesB...>> { typedef empty_set type; }; template<typename HeadA, typename ... TypesA, typename ... TypesB> struct set_intersection<type_set<HeadA, TypesA...>, type_set<TypesB...>> { typedef typename set_intersection<type_set<TypesA...>, type_set<TypesB...>>::type tail_intersection; typedef typename reduce_set< typename cons_set_if<is_element<HeadA, type_set<TypesB...>>::value, HeadA, tail_intersection>::type >::type type; }; template<typename A, typename B> struct set_intersection { typedef void type; static_assert(always_false<A,B>::value, "Template arguments are no type sets"); };
The last part I will show here, is a cross product operator. The cross product operator maps two type sets to a type set of tuple types. This is done by recursion again, but this time by splitting a square into a head square, vertical rectangle, horizontal rectangle and a tail square:
template<typename A, typename B> struct set_cross; template<typename ... Types> struct set_cross<empty_set, type_set<Types...>> { typedef empty_set type; }; template<typename ... Types> struct set_cross<type_set<Types...>, empty_set> { typedef empty_set type; }; template<typename HeadA, typename HeadB> struct set_cross<type_set<HeadA>, type_set<HeadB>> { typedef type_set<std::tuple<HeadA, HeadB>> type; }; template<typename HeadA, typename ... TypesA, typename HeadB, typename ... TypesB> struct set_cross<type_set<HeadA, TypesA...>, type_set<HeadB, TypesB...>> { private: typedef typename set_cross<type_set<HeadA>, type_set<HeadB>>::type head_square; typedef typename set_cross<type_set<HeadA>, type_set<TypesB...>>::type head_vert; typedef typename set_cross<type_set<TypesA...>, type_set<HeadB>>::type head_horiz; typedef typename set_cross<type_set<TypesA...>, type_set<TypesB...>>::type tail; typedef typename set_union<head_square, head_vert>::type u1; typedef typename set_union<u1, head_horiz>::type u2; public: typedef typename set_union<u2, tail>::type type; }; template<typename A, typename B> struct set_cross { typedef void type; static_assert(always_false<A,B>::value, "Template arguments are no type sets"); };
Equipped with these set operators you can do funky things like:
cout << is_subset<type_set<int,string>, type_set<int,string,int>>::value << endl; cout << is_subset<type_set<int,string>, type_set<int>>::value << endl; cout << is_set_equal<type_set<int, string>, reduce_set<type_set<int, string, int>>::type >::value << endl; cout << is_set_equal<set_union<type_set<int, string>, type_set<int, bool, double>>::type, type_set<int, string, bool, double>>::value << endl; cout << is_set_equal<set_intersection<type_set<int, string>, type_set<int, bool, double>>::type, type_set<int>>::value << endl; cout <<is_set_equal< set_cross< type_set<int, string>, type_set<int, bool> >::type, type_set< tuple<int,int>, tuple<int,bool>, tuple<string,int>, tuple<string,bool> > >::value << endl;
I haven’t figured out whether there is an actual use case for set theoretic type constructions like this. If anybody comes up with an idea, that would be appreciated! Otherwise, it’s a nice exercise to learn how to use variadic templates.
Source:http://www.bleedingmind.com/index.php/2012/03/04/set-theory-in-cpp11/
