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.

• Mast: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• Flamefire: Ok, sure. I just considered it a minor edit which makes the code shorter and therefore more readable. It did not change any functionality but rather style. Would it be ok, to add a note, that the specialization can be merged with the declaration so it does not need to be considered in the review (it wasn't by now)?
• Mast: Sure, that would be fine. Keep in mind though that while you can suggest reviewers focus on something else, they're free to mention it anyway if they feel a need to do so. But nothing wrong with providing a bit of direction.

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.

• Flamefire: I like the struct way because it is clear, that it is only TMP, not callable code, but those ideas are great, thanks! Some questions: a) C++14 only (see tag), could you revise the constexpr-if? b) How'd you implement the concatenate for 1-n lists and bonus: for any generic variadic templates (like std::tuple)? c) filtered_types does not take a typelist, which I'd need. I guess another indirection is required? d) why the decay_t? Isn't the result always a plain typelist? e) except the constexpr-if, all those functions could be left undefined, right? f) any info on performance?
• papagaga: @Flamefire: I provided some of the answers inside my post. For the other ones: c) yes, d) habits, decltype has its quirks and decaying it makes it walk the line. e) I don't believe so but I'm not sure, f) none, alas.
• Snowhawk: The typename in template template parameters is a c++17 feature.
• Flamefire: Won't the overloaded +-operator become a problem as now we have a function which can (seemingly) add e.g. 2 std::tuples but it will return an empty one in all cases? But you are right, the C++14 version looks like my structs: ideone.com/Nz58sb I'd be interested in any resources regarding compile-time performance, if anyone has some.

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.

• Flamefire: Awesome! Exactly what I was looking for: Improving my code to make it smaller AND faster. Wasn't able to measure a meaningfull difference but less concats are better and the nested template for filter_if_result means less instantiations (I guess)

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.

• Flamefire: Yes it is in a namespace (indicated in the examples, but omitted for brevity). What do you mean by "defining cons"? Define a separate function for prepending instead of concatenating? Might be good, but the concat is more generic (works for any number of typelists)
• bipll: Sure, but cons<Head is somewhat shorter than concat<typelist<Head>