9
\$\begingroup\$

I'm reading "Modern C++ Design"(A. Alexandrescu, 2002) and practicing basic TMP in chapter 3. Typelists. Since the book is quite dated, I revised example codes in C++17-esque manner.

Feel free to comment anything!

#include <cstddef>
#include <iostream>
#include <utility>
#include <type_traits>

// defining a typelist

template <typename T>
void printType() {
    std::cout << __PRETTY_FUNCTION__ << '\n';
}

template <typename...> struct TypeList;

template <>
struct TypeList<> {};

template <typename Head, typename... Tails>
struct TypeList<Head, Tails...> {
    using head = Head;
    using tails = TypeList<Tails...>;
};

// length of a typelist

template <typename TList> struct Length;

template <typename... Types>
struct Length<TypeList<Types...>> {
    static constexpr std::size_t value = sizeof...(Types);
};

template <typename TList>
inline constexpr std::size_t Length_v = Length<TList>::value;

// indexed access

template <typename TList, std::size_t index> struct TypeAt;

template <typename Head, typename... Tails>
struct TypeAt<TypeList<Head, Tails...>, 0> {
    using type = Head;
};

template <typename Head, typename... Tails, std::size_t index>
struct TypeAt<TypeList<Head, Tails...>, index> {
    static_assert(index < sizeof...(Tails) + 1, "index out of range");
    using type = typename TypeAt<TypeList<Tails...>, index - 1>::type;
};

template <typename TList, std::size_t index>
using TypeAt_t = typename TypeAt<TList, index>::type;

// indexof

template <typename TList, typename T> struct IndexOf;

template <typename T>
struct IndexOf<TypeList<>, T> {
    static constexpr std::size_t value = -1;
};

template <typename TList, typename T>
inline constexpr std::size_t IndexOf_v = IndexOf<TList, T>::value;

template <typename... Tails, typename T>
struct IndexOf<TypeList<T, Tails...>, T> {
    static constexpr std::size_t value = 0;
};

template <typename Head, typename... Tails, typename T>
struct IndexOf<TypeList<Head, Tails...>, T> {
    static constexpr std::size_t value = std::is_same_v<Head, T> ? 0 :
                                         (IndexOf_v<TypeList<Tails...>, T> == -1 ? -1 :
                                          IndexOf_v<TypeList<Tails...>, T> + 1);

};

// appending to typelists

template <typename TList1, typename TList2> struct Append;

template <typename... TList, typename T>
struct Append<TypeList<TList...>, T> {
    using result_type = TypeList<TList..., T>;
};

template <typename T, typename... TList>
struct Append<T, TypeList<TList...>> {
    using result_type = TypeList<T, TList...>;
};

template <typename... TList1, typename... TList2>
struct Append<TypeList<TList1...>, TypeList<TList2...>> {
    using result_type = TypeList<TList1..., TList2...>;
};

template <typename TList1, typename TList2>
using Append_t = typename Append<TList1, TList2>::result_type;

// erasing a type from a typelist

template <typename TList1, typename T> struct Erase;

template <typename TList1, typename T>
using Erase_t = typename Erase<TList1, T>::result_type;

template <typename... Tails, typename T>
struct Erase<TypeList<T, Tails...>, T> {
    using result_type = TypeList<Tails...>;
};

template <typename Head, typename... Tails, typename T>
struct Erase<TypeList<Head, Tails...>, T> {
    using result_type = Append_t<Head, Erase_t<TypeList<Tails...>, T>>;
};

template <typename TList1, typename T> struct EraseAll;

template <typename TList1, typename T>
using EraseAll_t = typename EraseAll<TList1, T>::result_type;

template <typename T>
struct EraseAll<TypeList<>, T> {
    using result_type = TypeList<>;
};

template <typename... Tails, typename T>
struct EraseAll<TypeList<T, Tails...>, T> {
    using result_type = EraseAll_t<TypeList<Tails...>, T>;
};

template <typename Head, typename... Tails, typename T>
struct EraseAll<TypeList<Head, Tails...>, T> {
    using result_type = Append_t<Head, EraseAll_t<TypeList<Tails...>, T>>;
};

// erasing duplicates

template <typename TList> struct NoDuplicates;

template <typename TList>
using NoDuplicates_t = typename NoDuplicates<TList>::result_type;

template <>
struct NoDuplicates<TypeList<>> {
    using result_type = TypeList<>;
};

template <typename Head, typename... Tails>
struct NoDuplicates<TypeList<Head, Tails...>> {
    using result_type = Append_t<Head, EraseAll_t<NoDuplicates_t<TypeList<Tails...>>, Head>>;
};

// replacing an element

template <typename TList, typename Old, typename New> struct Replace;

template <typename TList, typename Old, typename New>
using Replace_t = typename Replace<TList, Old, New>::result_type;

template <typename Old, typename New>
struct Replace<TypeList<>, Old, New> {
    using result_type = TypeList<>;
};

template <typename... Tails, typename Old, typename New>
struct Replace<TypeList<Old, Tails...>, Old, New> {
    using result_type = TypeList<New, Tails...>;
};

template <typename Head, typename... Tails, typename Old, typename New>
struct Replace<TypeList<Head, Tails...>, Old, New> {
    using result_type = Append_t<Head, Replace_t<TypeList<Tails...>, Old, New>>;
};

template <typename TList, typename Old, typename New> struct ReplaceAll;

template <typename TList, typename Old, typename New>
using ReplaceAll_t = typename ReplaceAll<TList, Old, New>::result_type;

template <typename Old, typename New>
struct ReplaceAll<TypeList<>, Old, New> {
    using result_type = TypeList<>;
};

template <typename... Tails, typename Old, typename New>
struct ReplaceAll<TypeList<Old, Tails...>, Old, New> {
    using result_type = ReplaceAll_t<TypeList<New, Tails...>, Old, New>;
};

template <typename Head, typename... Tails, typename Old, typename New>
struct ReplaceAll<TypeList<Head, Tails...>, Old, New> {
    using result_type = Append_t<Head, ReplaceAll_t<TypeList<Tails...>, Old, New>>;
};

// partially ordering typelists

template <typename TList, typename Base> struct MostDerived;

template <typename TList, typename Base>
using MostDerived_t = typename MostDerived<TList, Base>::result_type;

template <typename Base>
struct MostDerived<TypeList<>, Base> {
    using result_type = Base;
};

template <typename Head, typename... Tails, typename T>
struct MostDerived<TypeList<Head, Tails...>, T> {
private:
    using cand = MostDerived_t<TypeList<Tails...>, T>;
public:
    using result_type = std::conditional_t<std::is_base_of_v<cand, Head>, Head, cand>;
};

template <typename TList> struct Derived2Front;

template <typename TList>
using Derived2Front_t = typename Derived2Front<TList>::result_type;

template <>
struct Derived2Front<TypeList<>> {
    using result_type = TypeList<>;
};

template <typename Head, typename... Tails>
struct Derived2Front<TypeList<Head, Tails...>> {
private:
    using TheMostDerived = MostDerived_t<TypeList<Tails...>, Head>;
public:
    using result_type = Append_t<TheMostDerived, Replace_t<TypeList<Tails...>, TheMostDerived, Head>>;
};


class A {
};

class B : public A {
};

class C : public B {
};

int main() {
    using numberList = TypeList<int, double, float, uint8_t>;
    printType<numberList>();
    std::cout << Length_v<numberList> << '\n';
    printType<TypeAt_t<numberList, 2>>();
    std::cout << IndexOf_v<numberList, float> << '\n';

    using charList = TypeList<char, wchar_t, uint8_t>;
    using AppendedList = Append_t<numberList, charList>;
    printType<AppendedList>();

    printType<Erase_t<AppendedList, uint8_t>>();
    printType<EraseAll_t<AppendedList, uint8_t>>();
    printType<NoDuplicates_t<AppendedList>>();
    printType<Replace_t<AppendedList, uint8_t, size_t>>();
    printType<ReplaceAll_t<AppendedList, uint8_t, size_t>>();

    using ChainList = TypeList<A, B, C>;
    printType<MostDerived_t<ChainList, A>>();
    printType<Derived2Front_t<ChainList>>();

}

Test Result

void printType() [with T = TypeList<int, double, float, unsigned char>]
4
void printType() [with T = float]
2
void printType() [with T = TypeList<int, double, float, unsigned char, char, wchar_t, unsigned char>]
void printType() [with T = TypeList<int, double, float, char, wchar_t, unsigned char>]
void printType() [with T = TypeList<int, double, float, char, wchar_t>]
void printType() [with T = TypeList<int, double, float, unsigned char, char, wchar_t>]
void printType() [with T = TypeList<int, double, float, long unsigned int, char, wchar_t, unsigned char>]
void printType() [with T = TypeList<int, double, float, long unsigned int, char, wchar_t, long unsigned int>]
void printType() [with T = C]
void printType() [with T = TypeList<C, B, A>]
\$\endgroup\$

3 Answers 3

11
\$\begingroup\$

Overall, your code looks very good.

No need to overload for empty template parameter packs

A typename... parameter pack also matches zero elements, so the following overload is unnecessary:

template <>
struct TypeList<> {};

Use std::conditional to avoid having to repeat code

You can use std::conditional to choose a type based on some condition. That allows you to merge some overloads, for example there is no longer a need to declare a TypeAt<..., 0>:

template <typename Head, typename... Tails, std::size_t index>
struct TypeAt<TypeList<Head, Tails...>, index> {
    static_assert(index < sizeof...(Tails) + 1, "index out of range");
    using type = typename std::conditional<index == 0, Head, TypeAt<TypeList<Tails...>, index - 1>>::type;
};

Missing test cases for empty typelists

When you write variadic templates, also be sure to test the cornercase where the parameter pack is empty. Your code handles empty typelists very well! Consider adding test cases like:

using EmptyList = TypeList<>;
printType<EmptyList>();
std::cout << Length_v<EmptyList> << '\n';

Also test if modifying an empty typelist works as expected, and whether removing all types from a non-empty typelist results in an empty typelist.

\$\endgroup\$
5
\$\begingroup\$

A minor point in the main() function: you have neglected to define uint8_t. I guess that should be std::uint8_t from <cstdint>, and that's leaked into global namespace from one of the other library headers - but it's not portable to rely on that!

\$\endgroup\$
3
\$\begingroup\$
template <typename Head, typename... Tails, std::size_t index>
struct TypeAt<TypeList<Head, Tails...>, index> {
    static_assert(index < sizeof...(Tails) + 1, "index out of range");
    using type = typename TypeAt<TypeList<Tails...>, index - 1>::type;
};

static_assert is a late failure. You want to fail here early, so other code can detect this failure.

template <typename Head, typename... Tails>
struct TypeList<Head, Tails...> {
    using head = Head;
    using tails = TypeList<Tails...>;
};

I'm uncertain if head/tails should be a fundamental property of the typelist.

I'd write a function on typelists that returns the head and tail.

template<class T>
struct tails {};
template<template<class...>class Z, class T0, class...Ts>
struct tails<Z<T0, Ts...>> {
    using type=Z<Ts...>;
};
template<class T>
using tails_t = typename tails<T>::type;
template<class T>
struct head {};
template<template<class...>class Z, class T0, class...Ts>
struct head<Z<T0, Ts...>> {
    using type=head;
};
template<class T>
using head_t = typename head<T>::type;

This now works on anything (not just one TypeList).

The syntax at point of use requires less typename spam as well.

...

The next thing to realize is that you are doing functional programming. There are better patterns than what you used.

Try fmap/join/bind:

template<template<class...>class F, class T>
struct fmap {};
template<template<class...>class F, class T>
using fmap_t = typename fmap<F,T>::type;

template<template<class...>class F, template<class...>class Z, class...Ts>
struct fmap<F, Z<Ts...>> {
    using type=Z<F<Ts...>>;
};
template<class L>
struct join;
template<class L>
using join_t = typename join<L>::type;
template<template<class...>class Z, class... T0s, class... T1s, class..Zs>
struct join<Z< Z<T0s...>, Z<T1s...>, Zs... > >:join< Z<Z<T0s...>, Zs... > {};
template<template<class...>class Z, class... T0s, class... T1s, class..Zs>
struct join<Z< Z<T0s...> > > {
    using type=Z<T0s...>;
};
template<template<class...>class F, class T>
using bind_t = join_t< fmap_t< F, T > >;

now we can express most of the rest of your operations using the above primitives.

template<class Ts, class T>
using append_t = join_t< TypeList< Ts, TypeList<T> > >;

Erase is just bind( x->[x] except y->[], Ts ). Replace is just bind( x->[x] except y->[z], Ts ).

Now you will probably find writing these a bit annoying. Value metaprogramming to the rescue!

In C++17 and later you can have constexpr lambdas. You can also write overloads of lambdas.

template<class Match, class Replace>
constexpr auto ReplaceAll = []( auto Types ) {
    return bind(
        overload( [](auto x){return x;}, [](tag_t<Match>){ return tag<Replace>; } ),
        Types
    );
};

Converting TMP to this style of metaprogramming and back can be easier than writing clean TMP.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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