c++templatestuplesmetaprogrammingparameter-pack

Simplify creation of compile-time binary tree type


In the context of creating a binary tree type for a larger C++ project, I need to create a compile time type representing the nodes in each level.

Does anyone know, using the newest standards, if there is a simpler, nicer looking way of creating the LevelType, for an arbitrary value of nLevels in the (very simplified) code below?

I just need the type, so I can define it for the class Tree.

Thank you!

#include<array>
#include<iostream>

template <typename LevelType>
class Tree
{            
    public:
    LevelType level ;                                                                                                                                        
};

template <std::size_t nLevels, std::size_t... Is>
constexpr auto make_tree_impl(std::index_sequence<Is...>)
{
    return Tree
    <typename std::remove_reference
    <decltype(std::make_tuple(std::array<double,1<<Is>()...))>::type>();
};

template <std::size_t nLevels>
constexpr auto make_tree()
{
    return make_tree_impl<nLevels>(std::make_index_sequence<nLevels>());
};

int main()
{
    const unsigned int nLevels = 5;
    auto tree = make_tree<nLevels>();
    std::cout << std::is_same<decltype(tree),
    Tree<std::tuple<std::array<double,1>,
                    std::array<double,2>,
                    std::array<double,4>,
                    std::array<double,8>,
                    std::array<double,16>>>>::value << std::endl ;
    return 0;
}

Solution

  • You don't need std::remove_reference because make_tuple returns a non-reference.

    You don't need std::make_tuple. You can just specify the std::tuple directly.

    You don't need make_tree to be a function. If you only want the type it can be an alias template.

    And with the above you also don't need make_tree_impl to be defined, because it is only ever called to obtain the return type, which as a non-reference type again doesn't require a remove_reference:

    template <auto... Is>
    auto make_tree_impl(std::index_sequence<Is...>)
        -> Tree<std::tuple<std::array<double, std::size_t{1} << Is>...>>;
    
    template <std::size_t nLevels>
    using make_tree = decltype(make_tree_impl(std::make_index_sequence<nLevels>{}));
    

    Then you get the type directly with:

    using T = make_tree<nLevels>;
    

    The make_tree_impl function can also be replaced with an equivalent lambda in C++20 and later, but it won't make it look more readable.