c++ - 编译时将树转换为元组

Question

我遇到了以下问题:

给定一棵由 Node<> 类型的非终端节点表示的树和任意类型的终端节点，如 A , B等等(见下文)。

因为我不想使用运行时多态性，所以我喜欢将树转换为 std::tuple通过 constexpr其功能类似于下面示例中立即调用的 lambda 表达式。

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

template<typename... T>
struct Node {
    constexpr Node(const T&... n) : mChildren{n...} {}
    std::tuple<T...> mChildren;
};

template<uint8_t N>
struct IndexNode {
    std::array<uint8_t, N> mChildren;
};

int main() {
    constexpr auto tree = []() {
        auto t = Node(A(), 
                       B(), 
                       Node(C(),
                            Node(D())), 
                       E());    

        // transform t into std::tuple<A, B, C, D, IndexNode<1>{3}, IndexNode<2>{2, 4}, E, IndexNode<4>{0, 1, 5, 6}>

        // return ...;        
    }();

}

想法是使用元组元素的索引作为指向树的事件(选定)节点的“指针”。总体目的是在不使用运行时多态性的情况下在 µC 上实现菜单系统。

如果我可以在编译时执行这个转换，我可以使用一个特殊的元函数来检索事件的元组元素并在其上调用一些函数。这个函数我已经写好了。

缺失的链接肯定是某种深度优先树遍历......但我无法弄清楚。

Answer 1

使用大量的 std::tuple_cat、std::index_sequence 和递归如下？

#include <tuple>
#include <array>
#include <iostream>

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

template <typename... T>
struct Node
 {
   constexpr Node (T const & ... n) : mChildren { n... }
    { }

   std::tuple<T...> mChildren;
 };

template <std::size_t N>
struct IndexNode
 { std::array<uint8_t, N> mChildren; };

template <typename>
struct cntT : public std::integral_constant<std::size_t, 1U>
 { };

template <typename ... Ts>
struct cntT<Node<Ts...>>
   : public std::integral_constant<std::size_t, 1U + (cntT<Ts>::value + ...)>
 { };

template <typename T>
struct getT
 {
   constexpr auto operator() (T const & t, std::size_t & cnt)
    { ++cnt; return std::make_tuple(t); }
 };

template <typename ... Ts>
struct getT<Node<Ts...>>
 {
   template <std::size_t ... Is>
   constexpr auto func (std::tuple<Ts...> const & t,
                        std::index_sequence<Is...> const &,
                        std::size_t & cnt)
    {
      std::size_t val { cnt };

      IndexNode<sizeof...(Ts)> in
          { { { uint8_t(val += cntT<Ts>::value)... } } };

      return std::tuple_cat(getT<Ts>()(std::get<Is>(t), cnt)...,
                            std::make_tuple(in));
    }

   constexpr auto operator() (Node<Ts...> const & n, std::size_t & cnt)
    {
      return func(n.mChildren, std::make_index_sequence<sizeof...(Ts)>{},
                  cnt);
    }
 };

template <typename ... Ts>
constexpr auto linearNode (Node<Ts...> const & n)
 { 
   std::size_t cnt ( -1 );

   return getT<Node<Ts...>>()(n, cnt);
 }

int main()
 {  
   constexpr auto tree = []()
    {
      auto t = Node { A{}, B{}, Node{ C{}, Node{ D{} } }, E{} };

      return linearNode(t);
    }();

   static_assert( std::is_same<
      decltype(tree),
      std::tuple<A, B, C, D, IndexNode<1>, IndexNode<2>, E,
                 IndexNode<4>> const>::value, "!");

   std::cout << "IndexNode<1> { ";

   for ( auto const & v : std::get<4U>(tree).mChildren )
      std::cout << int(v) << ", ";

   std::cout << "}" << std::endl; // print IndexNode<1> { 3, }

   std::cout << "IndexNode<2> { ";

   for ( auto const & v : std::get<5U>(tree).mChildren )
      std::cout << int(v) << ", ";

   std::cout << "}" << std::endl; // print IndexNode<2> { 2, 4, }

   std::cout << "IndexNode<4> { ";

   for ( auto const & v : std::get<7U>(tree).mChildren )
      std::cout << int(v) << ", ";

   std::cout << "}" << std::endl; // print IndexNode<4> { 0, 1, 5, 6, }
 }