Filtering variadic template arguments

Question

I wrote some code to implement a way to filter the arguments of a variadic template based on their type.

My current solution requires many helper meta-functions and I'm sure that there must be a better way. How would you improve this?

#include <type_traits>
#include <tuple>

//Type for storing a variadic template
template <typename ...>
struct list {};

//helper meta-functions

//list_rename function. Renames any template type. Needed to convert list to tuple later
template <typename source, template <typename ...> class TargetT>
struct list_rename_impl;

template <template <typename ...> class SourceT, typename ... Args, template <typename ...> class TargetT>
struct list_rename_impl<SourceT<Args...>, TargetT>
{
    using type = TargetT<Args...>;
};

template <typename source, template <typename ...> class TargetT>
using list_rename = typename list_rename_impl<source, TargetT>::type;
//~END list_rename

//list_append function. Appends List U to T. Needed for the list_on_condition function
template <typename T, typename U>
struct list_append_impl
{};

template <typename ... LHS, typename ... RHS>
struct list_append_impl<list<LHS...>, list<RHS...>>
{
    using type = list<LHS..., RHS...>;
};

template <typename T, typename U>
using list_append = typename list_append_impl<T, U>::type;
//~END list_append


//list_on_condition function. Creates a list of all passed Elements for which Condition<Element>::value is true.
//This way a parameter pack can be filtered on a condition and stored 
template <template <typename> class Condition, typename ... Elements>
struct list_on_condition_impl
{};

template <template <typename> class Condition>
struct list_on_condition_impl<Condition>
{
    using type = list<>; //No more elements to left, return empty list
};

template <template <typename> class Condition, typename Element>
struct list_on_condition_impl<Condition, Element>
{
    using type = typename std::conditional //Only one element left. Return it, if it fullfills the Condition
                 <
                    Condition<Element>::value,
                    list<Element>,
                    list<>
                 >::type;
};

template <template <typename> class Condition, typename Element, typename ... Elements>
struct list_on_condition_impl<Condition, Element, Elements...>
{
    using type = list_append //Check the first element and append it to the others recursively
                 <
                    typename std::conditional
                    //Current element  gets wrapped in a list, if it fullfills the Condition,
                    //otherwise it resolves to an empty list 
                    <
                        Condition<Element>::value,
                        list<Element>,
                        list<>
                    >::type,
                    //self recursion
                    typename list_on_condition_impl

                    <
                        Condition,
                        Elements...
                    >::type
                 >;
};

template <template <typename> class Condition, typename ... Elements>
using list_on_condition = typename list_on_condition_impl<Condition, Elements...>::type;
//~ END helpers

//A dummy struct
template <typename ... Args>
struct A
{};

//Another dummy struct
template <typename ... Args>
struct B {};

//The actual testcase struct
template <typename ... Args> //This variadic template has to be filtered
class C
{
    private:
        //condition meta-functions; Decide if the template parameter is an A<...> or a B<...>
        template <typename T>
        struct IsA : std::false_type {};

        template <typename ... Elements>
        struct IsA<A<Elements...>> : std::true_type{};

        template <typename T>
        struct IsB : std::false_type {};

        template <typename ... Elements>
        struct IsB<B<Elements...>> : std::true_type{};

    public:
        using As = list_on_condition<IsA, Args...>; //Filtering using the helper functions from above
        using Bs = list_on_condition<IsB, Args...>;

        using ATuple = list_rename<As, std::tuple>; //Converting the list container to a tuple type 
        using BTuple = list_rename<Bs, std::tuple>;

        ATuple m_ATuple; //The template arguments in separated tuples
        BTuple m_BTuple;
};

int main()
{
    //Some checks to proof, that it works
    using t1 = C<A<int>, B<int>>;

    static_assert(   std::is_same
                     <
                       typename t1::As,
                       list<A<int>>
                     >::value
                  && std::is_same
                     <
                       typename t1::Bs,
                       list<B<int>>
                     >::value, "!!");

    using t2 = C<A<int>, B<int>, A<double, int>, A<float>, B<long>>;

    static_assert(   std::is_same
                     <
                       typename t2::As,
                       list<A<int>, A<double, int>, A<float>>
                     >::value
                  && std::is_same
                     <
                       typename t2::Bs,
                       list<B<int>, B<long>>
                     >::value, "!!");

    //Is there a more elegant way of filtering variadic templates?

    return 0;
}

Quuxplusone · Accepted Answer · 2016-01-04 05:08:40Z

One reason you think you require a lot of helper metafunctions is that you haven't clearly separated the code for solving the problem (filtering a list) from the code for testing the solution (e.g. list_rename and A, B, C).

Your actual solving the problem code, with redundant comments and newlines removed, boils down to this:

template <typename ...> struct list {};

template <typename T, typename U> struct list_append_impl {};

template <typename ... LHS, typename ... RHS>
struct list_append_impl<list<LHS...>, list<RHS...>> {
    using type = list<LHS..., RHS...>;
};

template <typename T, typename U>
using list_append = typename list_append_impl<T, U>::type;

template <template <typename> class Condition, typename ... Elements>
struct list_on_condition_impl {};

template <template <typename> class Condition>
struct list_on_condition_impl<Condition> {
    using type = list<>;
};

template <template <typename> class Condition, typename Element>
struct list_on_condition_impl<Condition, Element> {
    using type = typename std::conditional<
                    Condition<Element>::value,
                    list<Element>,
                    list<>
                 >::type;
};

template <template <typename> class Condition, typename Element, typename ... Elements>
struct list_on_condition_impl<Condition, Element, Elements...> {
    using type = list_append<
                    typename std::conditional<
                        Condition<Element>::value,
                        list<Element>,
                        list<>
                    >::type,
                    typename list_on_condition_impl<
                        Condition,
                        Elements...
                    >::type
                 >;
};

template <template <typename> class Condition, typename ... Elements>
using list_on_condition = typename list_on_condition_impl<Condition, Elements...>::type;

That's not particularly concise, but it's much less bad than you originally thought it was.

So let's work on removing the unnecessary parts. First of all, you have three specializations of list_on_condition_impl; that's a red flag, because you should basically always have two specializations of any recursive template — you should have one base case and one recursive case. If you have two base cases, something is probably wrong. You can safely remove the middle case,

template <template <typename> class Condition, typename Element>
struct list_on_condition_impl<Condition, Element> {
    using type = typename std::conditional<
                    Condition<Element>::value,
                    list<Element>,
                    list<>
                 >::type;
};

, because that case (an Elements list of length 1) will be handled perfectly fine by the recursive case.

Next, a style/safety note: For metaprogramming, you don't need to provide full definitions (i.e. class bodies) for your types; a declaration is usually all you need. Furthermore, providing just the declarations will prevent the user from accidentally trying to define variables of those types. So, for example, you should write

template <typename T, typename U> struct list_append_impl;

instead of

template <typename T, typename U> struct list_append_impl {};

and so on throughout. This also means that if someone accidentally tries to refer to list_append_impl<int, int>::type, they'll get a hard compiler error implicit instantiation of undefined template 'list_append_impl<int, int>' instead of a SFINAE-friendly error no type named 'type' in 'list_append_impl<int, int>'.

Next: Since list_append_impl is just an implementation detail, you probably don't need to define a convenience alias list_append for it. You could just use typename list_append_impl<...>::type in the couple of places you need it. This would kill off three more lines.

I also suggest naming the metafunction filter, instead of list_on_condition; the former conveys exactly what the metafunction is supposed to do, while the latter is pretty opaque to anybody reading the code.

Similarly, I'd recommend Predicate over Condition, Ts... and Us... over LHS... and RHS..., and T and Rest... over Element and Elements....

And for parameters whose names don't matter because they're unused — remove the unused names! (Unless you use a documentation-generation tool that needs the names for some reason, I guess.)

Consider using std::conditional_t<x,y,z> in place of typename std::conditional<x,y,z>::type, if you're using a recent enough C++14 library.

With the above suggestions and a bit of trivial whitespace formatting (e.g., typename... in place of typename ...), we get this:

template <typename...> struct list;

template <typename, typename> struct list_append_impl;

template <typename... Ts, typename... Us>
struct list_append_impl<list<Ts...>, list<Us...>> {
    using type = list<Ts..., Us...>;
};

template <template <typename> class, typename...>
struct filter_impl;

template <template <typename> class Predicate>
struct filter_impl<Predicate> {
    using type = list<>;
};

template <template <typename> class Predicate, typename T, typename... Rest>
struct filter_impl<Predicate, T, Rest...> {
    using type = typename list_append_impl<
                    std::conditional_t<
                        Predicate<T>::value,
                        list<T>,
                        list<>
                    >,
                    typename filter_impl<Predicate, Rest...>::type
                 >::type;
};

template <template <typename> class Predicate, typename... Ts>
using filter = typename filter_impl<Predicate, Ts...>::type;

One minor improvement you could make would be to split out the subproblem of "concatenating an arbitrary number of lists", so that you could write filter_impl without the recursion.

template <typename... Lists> struct concat;

template <template<typename> class Pred, typename T>
using filter_helper = std::conditional_t<Pred<T>::value, list<T>, list<>>;

template <template <typename> class Pred, typename... Ts> 
using filter = typename concat<filter_helper<Pred, Ts>...>::type;

You could implement such a variadic concat with recursion:

template <>
struct concat<> { using type = list<>; };
template <typename... Ts>
struct concat<list<Ts...>> { using type = list<Ts...>; };
template <typename... Ts, typename... Us>
struct concat<list<Ts...>, list<Us...>> { using type = list<Ts..., Us...>; };
template<typename... Ts, typename... Us, typename... Rest>
struct concat<list<Ts...>, list<Us...>, Rest...> { using type = typename concat<list<Ts..., Us...>, Rest...>::type; };

The above solves your problem in about 16 lines of code, as opposed to 29 lines for your cleaned-up version, as opposed to 42 lines for your original. And the advantage of splitting out the "concatenating lists" subproblem is that there are many different ways to tackle that particular subproblem —

you could unroll the recursion 3x or even 8x to avoid running so quickly into template-recursion-depth limits
you could use a compiler builtin (if one exists) to concatenate all the lists at once
variation on the above: you could delegate the heavy lifting to tuple_cat
or you could Keep It Simple and just use the 8-line version above.

You could benchmark each of these and see which one is most suitable for your expected workload.

Thank you for your detailed answer and the revised version! Besides the improvements on the content, especially finding the right names for functionality is often the most important aspect. — realloc
– realloc, Commented Jan 4, 2016 at 19:51
I don't seem to be understanding how to use "filter" to get the first type of the found list. I tried: template <typename B> struct my_pred { template <typename T> using filter = std::is_base_of<B, T>; }; filter< my_pred<A>::filter, C, B > v; But I get: 'v' uses undefined struct 'list<T>' — Rangel Reale
– Rangel Reale, Commented Jul 17, 2018 at 1:33
@RangelReale: You'd have to implement first_of yourself — something like template<class...> struct first_of_impl; template<class T, class... Rest> struct first_of_impl<T, Rest...> { using type = T; }; template<class... Ts> using first_of = typename first_of_impl<Ts...>::type;. But then once you've done that, you'd get your final answer by using answer = first_of<filter<my_pred<A>::filter, C, B>>;. — Quuxplusone
– Quuxplusone, Commented Jul 17, 2018 at 17:26
I don't understand why we need four concat not two like other recursive implementation for metaprogramming. — Yulong Ao
– Yulong Ao, Commented Mar 12, 2019 at 10:05

Dan Oberlam · Accepted Answer · 2016-01-04 04:42:59Z

The first issue I see is the name of your struct, list. This is problematic - supposing you eventually put this into its own hpp/cpp file, someone may someday try to link to a file that has the line using std::list;. Even beyond that, the name may be confusing at first glance - either rename it or use a namespace (or both).

When I see usings like this

using list_rename = typename list_rename_impl<source, TargetT>::type;

I like to name the aliased type as type_name_t, so in this case list_rename_t.

You can also use std::conditional_t<B, T, F> instead of std::conditional<B, T, F>::type since C++14.

This is being pedantic, but the comment here is inaccurate, C is a class.

//The actual testcase struct
template <typename ... Args>
class C

I don't find comments like

//~END list_rename

to be at all helpful - you use this format consistently, so maybe this is required stylistically, or you have some documentation generating tool, or whatever, but unless you have a compelling reason to have this sort of comment its just noise.

Do you have a compelling reason to require the user to say

using ATuple = list_rename<As, std::tuple>;

Instead of something like this?

template <typename source>
using list_rename_as_tuple = typename list_rename_impl<source, std::tuple>::type;

...

using ATuple = list_rename_as_tuple<As>;

I guess I haven't thought about the use cases of this enough, but do you need to make this generic enough that the user specifies their result container type? Would tuple be a common enough destination type that the second alias is helpful?

I'm not sure if it can be reduced to fewer meta-functions, I don't have the bandwidth to really dig into it at the moment, but is there an advantage to that? Right now I find this to be pretty easy to reason about and understand.

Stack Exchange Network

Filtering variadic template arguments

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

Filtering variadic template arguments

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions