Filter template meta function

Question

I wrote a simple C++ template meta function for filtering out types from a list not matching a predicate. This is similar to Filtering variadic template arguments but does pattern matching instead of std::conditional with the aim of being faster. To that end no empty typelists are concatenated which should incur less instantiations and be faster according to https://blog.galowicz.de/2016/06/25/cpp_template_type_list_performance

The below code works for all my test cases. Any hints how to make it faster (less template instantiations), smaller, better, ...? (Note: Assume appropriate *_t using-templates)

template <typename... Ts>
struct typelist;

template <typename... TLists>
struct concat;
template <typename... Args1, typename... Args2>
struct concat<typelist<Args1...>, typelist<Args2...>>
{
    using type = typelist<Args1..., Args2...>;
};
template <class Seq1, class Seq2, class... Seqs>
struct concat<Seq1, Seq2, Seqs...> : concat<Seq1, concat_t<Seq2, Seqs...>>
{
};

template <class TList, template <typename> class Cond>
struct filter;
template<bool matches, template <typename> class Cond, typename...>
struct filter_helper;

template<template <typename> class Cond, typename T, typename... Ts>
struct filter_helper<true, Cond, T, Ts...>
{
    using type = concat_t<typelist<T>, filter_t<typelist<Ts...>, Cond>>;
};

template<template <typename> class Cond, typename T, typename... Ts>
struct filter_helper<false, Cond, T, Ts...>
{
    using type = filter_t<typelist<Ts...>, Cond>;
};

template<template <typename> class Cond, typename T, typename... Ts>
struct filter<typelist<T, Ts...>, Cond>
{
    using type = typename filter_helper<Cond<T>::value, Cond, T, Ts...>::type;
};

template<template <typename> class Cond>
struct filter<typelist<>, Cond>
{
    using type = typelist<>;
};

Some tests (TMP_ASSERT is like static_assert):

using list1 = tmp::typelist<int, double>;
using list2 = tmp::typelist<float>;
using list3 = tmp::typelist<double>;
using list4 = tmp::typelist<float, double, double>;
using list5 = tmp::typelist<double, float, double>;
using list6 = tmp::typelist<double, double, float>;
using empty = tmp::typelist<>;

template<typename T>
struct is_not_double: std::true_type{};
template<>
struct is_not_double<double>: std::false_type{};

TMP_ASSERT_SAME((tmp::filter_t<list1, is_not_double>), (tmp::typelist<int>));
TMP_ASSERT_SAME((tmp::filter_t<list2, is_not_double>), (tmp::typelist<float>));
TMP_ASSERT_SAME((tmp::filter_t<list3, is_not_double>), (tmp::typelist<>));
TMP_ASSERT_SAME((tmp::filter_t<list4, is_not_double>), (tmp::typelist<float>));
TMP_ASSERT_SAME((tmp::filter_t<list5, is_not_double>), (tmp::typelist<float>));
TMP_ASSERT_SAME((tmp::filter_t<list6, is_not_double>), (tmp::typelist<float>));
TMP_ASSERT_SAME((tmp::filter_t<empty, is_not_double>), (tmp::typelist<>));

Note: Code is from a library licensed under BSD 3-Clause.

Answer 1

I find all those structs tricks a bit old-school now...

There is an alternative implementation using constexpr functions; I also recommend to use if constexpr to make things more readable, but it's doable without it; you just need another overload:

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

template <typename... T1s, typename... T2s>
constexpr auto concatenate(Type_list<T1s...>, Type_list<T2s...>) {
    return Type_list<T1s..., T2s...>{};
}

template <template <typename> typename Condition, typename Result>
constexpr auto filter_types(Result result, Type_list<>) {
    return result;
}

template <template <typename> typename Condition, typename Result, typename T, typename... Ts>
constexpr auto filter_types(Result result, Type_list<T, Ts...>) {
    if constexpr (Condition<T>{})
        return filter_types<Condition>(concatenate(result, Type_list<T>{}), Type_list<Ts...>{});
    else
        return filter_types<Condition>(result, Type_list<Ts...>{});
}

template <template <typename> typename Condition, typename... Types>
using filtered_types = std::decay_t<decltype(filter_types<Condition>(Type_list<>{}, Type_list<Types...>{}))>;


template<typename T>
struct is_not_double: std::true_type{};
template<>
struct is_not_double<double>: std::false_type{};

template <typename T>
void print_type() {
    puts(__PRETTY_FUNCTION__);
    }

int main() {
    print_type<filtered_types<is_not_double, double, int, char, float*, double, char*, double>>();
}

I'd rather have this sort of programming: template programming looks like normal programming, rather than have two subsets of the language apart from each other.

---

Edit: as per request, here's a rewriting of the code without C++ 17 features:

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

template <typename... T1s, typename... T2s>
constexpr auto concatenate(Type_list<T1s...>, Type_list<T2s...>) {
    return Type_list<T1s..., T2s...>{};
}

template <template <typename> typename Condition, typename Result, typename T, typename... Ts>
constexpr auto filter_types(Result result, Type_list<T, Ts...>, std::true_type)  {
    return filter_types<Condition>(concatenate(result, Type_list<T>{}), Type_list<Ts...>{});
}

template <template <typename> typename Condition, typename Result, typename T, typename... Ts>
constexpr auto filter_types(Result result, Type_list<T, Ts...>, std::false_type) {
    return filter_types<Condition>(result, Type_list<Ts...>{});
}

template <template <typename> typename Condition, typename Result>
constexpr auto filter_types(Result result, Type_list<>) {
    return result;
}

template <template <typename> typename Condition, typename T, typename... Ts, typename... Us>
constexpr auto filter_types(Type_list<Us...> result, Type_list<T, Ts...> lst) {
    return filter_types<Condition>(result, lst, Condition<T>{});
}

template <template <typename> typename Condition, typename... Types>
using type_filter = decltype(filter_types<Condition>(Type_list<>{}, Type_list<Types...>{}));

As for a variadic, container agnostic, concatenate, here's what you would do with fold expressions:

template <template <typename> typename Type_container, typename... T1s, typename... T2s>
constexpr auto operator+(Type_container<T1s...>, Type_container<T2s...>) {
    return Type_container<T1s..., T2s...>{};
}

template <typename... Type_lists>
constexpr auto concatenate(Type_lists... type_lists) {
    return (type_lists + ...);
}

Without fold expressions you need to provide overloads for calls with 0, 1 and more type lists, as you did with your structs.

Answer 2

You can halve your concat calls by just creating new typelists inline and skipping the intermediate 2-param concat objects on rewind.

Should concat be callable on empty and single argument lists?

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

template <>
struct concat<> {
    using type = typelist<>;
};

template <typename... Ts>
struct concat<typelist<Ts...>> {
    using type = typelist<Ts...>;
};

template <typename... Ts0, typename... Ts1, typename... Rest>
struct concat<typelist<Ts0...>, typelist<Ts1...>, Rest...> 
: concat<typelist<Ts0..., Ts1...>, Rest...> {};

// Helper until C++20
template <typename... Ts>
using concat_t = typename concat<Ts...>::type;

---

Rather than recursively filtering your list, consider a sequential approach using pack expansion. To do this, we'll need to exploit a property of concatenation with typelists. When you concatenate a list with no elements to a list of elements (concat<typelist<int>, typelist<>>), the result list remains the same (typelist<int>).

First, maps the predicate result (true/false) to either typelist<T> or typelist<>.

template <bool>
struct filter_if_result {
    template <typename T> using type = typelist<T>;
};

template <>
struct filter_if_result<false> {
    template <typename T> using type = typelist<>;
};

Second, pack expand the unfiltered types and apply the predicate to each. Then concat the results to merge typelists with the collected elements with the empty typelists.

template <template <typename> class Predicate, typename Sequence>
struct filter_if;

template <template <typename> class Predicate, typename... Ts>
struct filter_if<Predicate, typelist<Ts...>> {
    using type = concat_t<
        typename filter_if_result<Predicate<Ts>::value>::template type<Ts>...>;
};

// Helper until C++20
template <template <typename> class Predicate, typename Sequence>
using filter_if_t = typename filter_if<Predicate, Sequence>::type;

Note - filter_if is used to differentiate the predicate version from the version that filters on a specific type.

Answer 3

Are you doing it in a namespace? concat and filter are too simple and generic names.

using type = concat_t<typelist<T>, filter_t<typelist<Ts...>, Cond>>;

As long as it's the only case you prepend an element to a list it's okay, but on the second occasion you might think of defining cons. :)

Oh, and looks like your concat accepts at least two arguments.