5
\$\begingroup\$

So, time to explore the scary depths of template metaprogramming (well, scary for me, anyways).

This library basically provides 2 different lists, a list of types and a list of sizes.

Both lists support:

  • Contains: check whether an element is in the list
  • IndexOf: retrieve the index of an element in the list. static_asserts that the element is in the list.
  • Size: retrieve the length of a list.
  • Rename: Instantiate another template with the elements in the list.
  • Filter: Return a list containing only the elements matching a predicate.

Additionally, the list of sizes supports a Get operation: retrieve the size at an index.

Any suggestions for improvements are welcome!

mpl_types.h

#pragma once

namespace MPL
{
namespace Types
{
    namespace impl
    {
        struct type_list_end{};

        template<typename T, typename... Ts>
        struct type_list
        {
            using current = T;
            using next = type_list<Ts...>;
        };

        template<typename T>
        struct type_list<T>
        {
            using current = T;
            using next = type_list_end;
        };

        template<size_t Count, typename... Ts>
        struct type_list_builder_helper
        {
            using type = type_list<Ts...>;
        };

        template<typename... Ts>
        struct type_list_builder_helper<0u, Ts...>
        {
            using type = type_list_end;
        };

        template<typename... Ts>
        struct type_list_builder
        {
            using type = typename type_list_builder_helper<sizeof...(Ts), Ts...>::type;
        };

        template<typename TypeList, typename T>
        struct type_list_contains; // forward declaration

        template<bool Same, typename TypeList, typename T>
        struct type_list_contains_helper
        {
            static const constexpr bool value = type_list_contains<typename TypeList::next, T>::value;
        };

        template<typename TypeList, typename T>
        struct type_list_contains_helper<true, TypeList, T>
        {
            static const constexpr bool value = true;
        };

        template<typename TypeList, typename T>
        struct type_list_contains
        {
            static const constexpr bool value = typename type_list_contains_helper<std::is_same<typename TypeList::current, T>::value, TypeList, T>::value;
        };

        template<typename T>
        struct type_list_contains<type_list_end, T>
        {
            static const constexpr bool value = false;
        };

        template<size_t Index, typename TypeList, typename T>
        struct type_list_index_of;

        template<bool Same, size_t Index, typename TypeList, typename T>
        struct type_list_index_of_helper
        {
            static const constexpr size_t value = type_list_index_of<Index + 1, typename TypeList::next, T>::value;
        };

        template<size_t Index, typename TypeList, typename T>
        struct type_list_index_of_helper<true, Index, TypeList, T>
        {
            static const constexpr size_t value = Index;
        };

        template<size_t Index, typename TypeList, typename T>
        struct type_list_index_of
        {
            static const constexpr size_t value = type_list_index_of_helper<std::is_same<typename TypeList::current, T>::value, Index, TypeList, T>::value;
        };

        template<size_t Size, typename TypeList>
        struct type_list_size
        {
            static const constexpr size_t value = type_list_size<Size + 1, typename TypeList::next>::value;
        };

        template<size_t Size>
        struct type_list_size<Size, type_list_end>
        {
            static const constexpr size_t value = Size;
        };

        template<template<typename...> typename Target, typename TypeList>
        struct type_list_rename;

        template<template<typename...> typename Target, typename... Ts, template<typename...> typename TypeList>
        struct type_list_rename<Target, TypeList<Ts...>>
        {
            using type = Target<Ts...>;
        };

        template<template<typename...> typename Target>
        struct type_list_rename<Target, type_list_end>
        {
            using type = Target<>;
        };

        template<typename TypeList, template<typename> typename Pred, typename... Ts>
        struct type_list_filter;

        template<bool Same, typename TypeList, template<typename> typename Pred, typename... Ts>
        struct type_list_filter_helper
        {
            using type = typename type_list_filter<typename TypeList::next, Pred, Ts...>::type;
        };

        template<typename TypeList, template<typename> typename Pred, typename... Ts>
        struct type_list_filter_helper<true, TypeList, Pred, Ts...>
        {
            using type = typename type_list_filter<typename TypeList::next, Pred, Ts..., typename TypeList::current>::type;
        };

        template<typename TypeList, template<typename> typename Pred, typename... Ts>
        struct type_list_filter
        {
            using type = typename type_list_filter_helper<Pred<typename TypeList::current>::value, TypeList, Pred, Ts...>::type;
        };

        template<template<typename> typename Pred, typename... Ts>
        struct type_list_filter<type_list_end, Pred, Ts...>
        {
            using type = typename type_list_builder<Ts...>::type;
        };
    }

    template<typename... Ts>
    using List = typename impl::type_list_builder<Ts...>::type;

    template<typename TypeList, typename T>
    static constexpr bool Contains()
    {
        return impl::type_list_contains<TypeList, T>::value;
    }

    template<typename TypeList, typename T>
    static constexpr size_t IndexOf() noexcept
    {
        static_assert(Contains<TypeList, T>(), "TypeList does not contain T");

        return impl::type_list_index_of<0u, TypeList, T>::value;
    }

    template<typename TypeList>
    static constexpr size_t Size() noexcept
    {
        return impl::type_list_size<0u, TypeList>::value;
    }

    template<template<typename...> typename Target, typename TypeList>
    using Rename = typename impl::type_list_rename<Target, TypeList>::type;

    template<typename TypeList, template<typename> typename Pred>
    using Filter = typename impl::type_list_filter<TypeList, Pred>::type;
}
}

mpl_sizes.h

#pragma once

namespace MPL
{
namespace Sizes
{
    namespace impl
    {
        struct size_list_end{};

        template<size_t I, size_t... Is>
        struct size_list
        {
            static const constexpr size_t current = I;
            using next = size_list<Is...>;
        };

        template<size_t I>
        struct size_list<I>
        {
            static const constexpr size_t current = I;
            using next = size_list_end;
        };

        template<size_t Count, size_t... Is>
        struct size_list_builder_helper
        {
            using type = size_list<Is...>;
        };

        template<size_t... Is>
        struct size_list_builder_helper<0u, Is...>
        {
            using type = size_list_end;
        };

        template<size_t... Is>
        struct size_list_builder
        {
            using type = typename size_list_builder_helper<sizeof...(Is), Is...>::type;
        };

        template<typename SizeList, size_t Value>
        struct size_list_contains;

        template<bool Same, typename SizeList, size_t Value>
        struct size_list_contains_helper
        {
            static const constexpr bool value = size_list_contains<typename SizeList::next, Value>::value;
        };

        template<typename SizeList, size_t Value>
        struct size_list_contains_helper<true, SizeList, Value>
        {
            static const constexpr bool value = true;
        };

        template<typename SizeList, size_t Value>
        struct size_list_contains
        {
            static const constexpr bool value = size_list_contains_helper<SizeList::current == Value, SizeList, Value>::value;
        };

        template<size_t Value>
        struct size_list_contains<size_list_end, Value>
        {
            static const constexpr bool value = false;
        };

        template<size_t Index, typename SizeList, size_t Value>
        struct size_list_index_of;

        template<bool Same, size_t Index, typename SizeList, size_t Value>
        struct size_list_index_of_helper
        {
            static const constexpr size_t value = size_list_index_of<Index + 1, typename SizeList::next, Value>::value;
        };

        template<size_t Index, typename SizeList, size_t Value>
        struct size_list_index_of_helper<true, Index, SizeList, Value>
        {
            static const constexpr size_t value = Index;
        };

        template<size_t Index, typename SizeList, size_t Value>
        struct size_list_index_of
        {
            static const constexpr size_t value = size_list_index_of_helper<SizeList::current == Value, Index, SizeList, Value>::value;
        };

        template<size_t Index, size_t Value>
        struct size_list_index_of<Index, size_list_end, Value>{};

        template<size_t Size, typename SizeList>
        struct size_list_size
        {
            static const constexpr size_t value = size_list_size<Size + 1, typename SizeList::next>::value;
        };

        template<size_t Size>
        struct size_list_size<Size, size_list_end>
        {
            static const constexpr size_t value = Size;
        };

        template<size_t CurrentIndex, typename SizeList, size_t Index>
        struct size_list_get;

        template<bool Same, size_t CurrentIndex, typename SizeList, size_t Index>
        struct size_list_get_helper
        {
            static const constexpr size_t value = size_list_get<CurrentIndex + 1, SizeList, Index>::value;
        };

        template<size_t CurrentIndex, typename SizeList, size_t Index>
        struct size_list_get_helper<true, CurrentIndex, SizeList, Index>
        {
            static const constexpr size_t value = SizeList::current;
        };

        template<size_t CurrentIndex, typename SizeList, size_t Index>
        struct size_list_get
        {
            static const constexpr size_t value = size_list_get_helper<CurrentIndex == Index, CurrentIndex, SizeList, Index>::value;
        };

        template<template<size_t...> typename Target, typename SizeList, size_t... Is>
        struct size_list_rename
        {
            using type = typename size_list_rename<Target, typename SizeList::next, Is..., SizeList::current>::type;
        };

        template<template<size_t...> typename Target, size_t... Is>
        struct size_list_rename<Target, size_list_end, Is...>
        {
            using type = Target<Is...>;
        };

        template<typename SizeList, template<size_t> typename Pred, size_t... Is>
        struct size_list_filter;

        template<bool Match, typename SizeList, template<size_t> typename Pred, size_t... Is>
        struct size_list_filter_helper
        {
            using type = typename size_list_filter<typename SizeList::next, Pred, Is...>::type;
        };

        template<typename SizeList, template<size_t> typename Pred, size_t... Is>
        struct size_list_filter_helper<true, SizeList, Pred, Is...>
        {
            using type = typename size_list_filter<typename SizeList::next, Pred, Is..., SizeList::current>::type;
        };

        template<typename SizeList, template<size_t> typename Pred, size_t... Is>
        struct size_list_filter
        {
            using type = typename size_list_filter_helper<Pred<SizeList::current>::value, SizeList, Pred, Is...>::type;
        };

        template<template<size_t> typename Pred, size_t... Is>
        struct size_list_filter<size_list_end, Pred, Is...>
        {
            using type = typename size_list_builder<Is...>::type;
        };
    }

    template<size_t... Is>
    using List = typename impl::size_list_builder<Is...>::type;

    template<typename SizeList, size_t Value>
    static constexpr bool Contains() noexcept
    {
        return impl::size_list_contains<SizeList, Value>::value;
    }

    template<typename SizeList, size_t Value>
    static constexpr size_t IndexOf() noexcept
    {
        static_assert(Contains<SizeList, Value>(), "SizeList does not contain Value");

        return impl::size_list_index_of<0u, SizeList, Value>::value;
    }

    template<typename SizeList>
    static constexpr size_t Size() noexcept
    {
        return impl::size_list_size<0u, SizeList>::value;
    }

    template<typename SizeList, size_t Index>
    static constexpr size_t Get() noexcept
    {
        static_assert(Index < Size<SizeList>(), "Index out of range");

        return impl::size_list_get<0u, SizeList, Index>::value;
    }

    template<template<size_t...> typename Target, typename SizeList>
    using Rename = typename impl::size_list_rename<Target, SizeList>::type;

    template<typename SizeList, template<size_t> typename Pred>
    using Filter = typename impl::size_list_filter<SizeList, Pred>::type;
}
}

examples

#include "mpl_types.h"
#include "mpl_sizes.h"
#include <tuple>

struct A {};
struct B {};
struct C {};
struct D {};

using TypeList1 = MPL::Types::List<A, B, C>;

// TypeList1 contains A, B and C
static_assert(MPL::Types::Contains<TypeList1, A>() && MPL::Types::Contains<TypeList1, B>() && MPL::Types::Contains<TypeList1, C>(), "");
// ... but not D
static_assert(!MPL::Types::Contains<TypeList1, D>(), "");

using TupleOfList = MPL::Types::Rename<std::tuple, TypeList1>;
// TupleOfList is exactly the same as std::tuple<A, B, C>;
static_assert(std::is_same<TupleOfList, std::tuple<A, B, C>>::value, "");

// this predicate matches all types but B
template<typename T>
using isNotB = std::integral_constant<bool, !std::is_same<T, B>::value>;

// filter TypeList1 with this predicate
using TypeList2 = MPL::Types::Filter<TypeList1, isNotB>;
// TypeList2 should now contain (A, C)
static_assert(!MPL::Types::Contains<TypeList2, B>(), "");
static_assert(MPL::Types::IndexOf<TypeList2, A>() == 0u, "");
static_assert(MPL::Types::IndexOf<TypeList2, C>() == 1u, "");
static_assert(MPL::Types::Size<TypeList2>() == 2u, "");

template<typename... Ts>
using Indices = MPL::Sizes::List<MPL::Types::IndexOf<TypeList1, Ts>()...>;

using IndicesInTuple = MPL::Types::Rename<Indices, TypeList2>;
// IndicesInTuple contains (0, 2)

template<size_t... Indices>
struct TupleExtractor {
    template<typename... Ts>
    static auto extract(std::tuple<Ts...> t) {
        return std::make_tuple(std::get<Indices>(t)...);
    }
};

int main() {
    TupleOfList t;
    B bValue = std::get<MPL::Types::IndexOf<TypeList1, B>()>(t);

    using MyExtractor = MPL::Sizes::Rename<TupleExtractor, IndicesInTuple>;
    std::tuple<A, C> newTuple = MyExtractor::extract(t);
}
\$\endgroup\$
  • \$\begingroup\$ You've seem to fall into the same issue as I did. You can follow my chain of posts (only two of them though), link to the first one. Specifically, the recursive nature is rarely useful. \$\endgroup\$ – Incomputable Aug 10 '17 at 10:51
  • \$\begingroup\$ @Incomputable: Thanks for the link and the food for thoughts ;) I'm already finding places for improvement \$\endgroup\$ – hoffmale Aug 10 '17 at 10:58
  • \$\begingroup\$ It would be great to provide some main() with examples. They can be trivial, but should "showcase" usage of the code you've written. \$\endgroup\$ – Incomputable Aug 10 '17 at 11:08
  • \$\begingroup\$ @Incomputable: added some examples \$\endgroup\$ – hoffmale Aug 10 '17 at 11:38
  • 1
    \$\begingroup\$ Naturally, you'd use one of the many metaprogramming libraries out there, such as Brigand or Metal \$\endgroup\$ – Justin Aug 11 '17 at 19:06
4
\$\begingroup\$
#pragma once

namespace MPL
{
...

You don't #include <type_traits>, but you do use std::is_same. Add the #include:

#pragma once

#include <type_traits>

namespace MPL
{
...

    struct type_list_end{};

    template<typename T, typename... Ts>
    struct type_list
    {
        using current = T;
        using next = type_list<Ts...>;
    };

    template<typename T>
    struct type_list<T>
    {
        using current = T;
        using next = type_list_end;
    };

It's a bit odd to define a separate type to indicate an empty sequence. I would expect the empty sequence to be type_list<>:

    // We just let our default case be the empty sequence
    // That saves us a bit of code. If you don't want to do so,
    // you can specialize the template for empty arguments
    template<typename... Ts>
    struct type_list
    {};

    template<typename T, typename... Ts>
    struct type_list<T, Ts...>
    {
        using current = T;
        using next = type_list<Ts...>;
    };

This means that (almost) everywhere you had to have a special case for an empty sequence, you now don't. For example, you can completely remove this:

    template<template<typename...> typename Target>
    struct type_list_rename<Target, type_list_end>
    {
        using type = Target<>;
    };

There would also be no reason to have type_list_builder, so you could remove it altogether:

template<typename... Ts>
using List = impl::type_list<Ts...>;

One thing about template metaprogramming: instantiating templates / SFINAE are very expensive. If we can avoid instantiating templates as much as is reasonable, we can improve compile times.


You can greatly simplify your implementation of Contains:

    template<typename TypeList, typename T>
    struct type_list_contains;

    template<typename... Ts, typename T>
    struct type_list_contains<type_list<Ts...>, T>
    {
        // You don't need both const and constexpr on variables
        static constexpr bool value = any<std::is_same<Ts, T>::value...>::value;
    };

But then you'd need an implementation of any, such as:

template<bool...>
struct bool_list
{};
// If you are using C++14, you may want to use
// template<bool... Bs>
// using bool_list = std::integer_sequence<bool, Bs...>;

template<bool... Bs>
using all = std::is_same<
    bool_list<true, Bs...>,
    bool_list<Bs..., true>
>;
// C++17:
// constexpr bool all = Bs && ..;

template<bool... Bs>
using any = std::integral_constant<bool,
    !all<(!Bs)...>::value
>;
// C++17:
// constexpr bool any = Bs || ..;

Your implementation of Size is doing way too much work. There's no need to recurse at all, you can simply do:

    template<typename TypeList>
    struct type_list_size;

    template<typename... Ts>
    struct type_list_size<type_list<Ts...>>
    {
        static constexpr size_t value = sizeof...(Ts);
    };

Rename is more well known as "apply". You take a meta-function and an argument list, and apply the function on the arguments.


For your Size list:

    template<size_t I, size_t... Is>
    struct size_list
    {
        static const constexpr size_t current = I;
        using next = size_list<Is...>;
    };

This is arbitrarily restricted to only take size_t, when you can easily extend it to take any type T:

    template<typename T, T first, T... rest>
    struct value_list
    {
        static constexpr T current = first;
        using next = value_list<T, rest...>;
    };

On that matter, it's a bit annoying that we have to rewrite the code for values as well as types. However, we could instead wrap the values in a type and reuse our type list:

template <typename T, T... values>
using value_list = type_list<std::integral_constant<T, values>...>;
\$\endgroup\$
  • \$\begingroup\$ I believe integral_constant is C++14 feature, which is unfortunately not used by the OP. \$\endgroup\$ – Incomputable Aug 11 '17 at 19:20
  • \$\begingroup\$ @Incomputable It's C++11 \$\endgroup\$ – Justin Aug 11 '17 at 19:21
  • \$\begingroup\$ I don't care too much about the differences of C++11/14/17 (this is a small side project of mine, so I can freely choose what I need). About the #include <type_traits>: when I do include it, VS just highlights it as unused (heck, it compiled the sample with only those 3 files present!). Other than that, this is me learning something new, so (of course!) I make a lot of silly mistakes - thanks for the pointers :) \$\endgroup\$ – hoffmale Aug 11 '17 at 19:25
  • \$\begingroup\$ @Justin, sorry for confusing things. Then its probably the sequences that are C++14. \$\endgroup\$ – Incomputable Aug 11 '17 at 19:25
  • \$\begingroup\$ @Incomputable Yeah integer_sequence is C++14, sadly \$\endgroup\$ – Justin Aug 11 '17 at 19:26
3
\$\begingroup\$

Typing from mobile device.

Architecture

It resembles ranges, yes. But is it useful? It will generate a lot of types, which can increase memory usage during compiling, and the code might ultimately fail to compile due to being out of memory. Consider using simple

template <typename ... Types>
struct type_list {};

Rethink algorithms

There are some algorithms which are obscurely implemented (size_list_contains really could use some simplification). I think the following tip on how to check if two template parameters are the same will be useful:

template <typename T, typename U>
struct is_same
{
     static constexpr bool value = false;
}

template <typename T>
struct is_same<T, T>
{
     static constexpr bool value = true;
}

Hide helpers

You could use classes to make helpers private, thus cleaning up a lot of places. One disadvantage of the approach is that compiler will keep issuing shadowing warnings, which are not always useful.

Better interface

Template functions could place Value first, and then accept the list by value. That would compiler to deduce list, and users would only specify value.

Build script

It is important to have some sort of script that people could use after installing your library. Although it is header only, I've encountered cases where it would still be useful, especially when it is part of another component. I wouldn't want to mess with file system when I'm at language level. It could also specify C++ version to be used with it, perform compiler feature checks. There are also package managers for C++ (yes, they actually exist).

Conclusion

There are better things to spend your life on. Finding a problem that typelists would effectively solve is extremely hard. May be learning SFINAE tricks and useful idioms, like detection idiom, would be better.

\$\endgroup\$

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.