7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Mast Aug 9 '18 at 8:44
  • \$\begingroup\$ 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)? \$\endgroup\$ – Flamefire Aug 9 '18 at 11:53
  • \$\begingroup\$ 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. \$\endgroup\$ – Mast Aug 9 '18 at 11:58
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Flamefire Aug 8 '18 at 20:50
  • \$\begingroup\$ @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. \$\endgroup\$ – papagaga Aug 9 '18 at 10:08
  • \$\begingroup\$ The typename in template template parameters is a c++17 feature. \$\endgroup\$ – Snowhawk Aug 9 '18 at 10:49
  • \$\begingroup\$ 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. \$\endgroup\$ – Flamefire Aug 9 '18 at 11:08
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Flamefire Aug 9 '18 at 11:48
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Flamefire Aug 8 '18 at 20:37
  • \$\begingroup\$ Sure, but cons<Head is somewhat shorter than concat<typelist<Head> \$\endgroup\$ – bipll Aug 8 '18 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.