編譯時變換樹的成元組

Question

我卡具有以下問題：

鑑於Node<>類型的非終端節點和任意的類型，如A，B等的終端節點所表示的樹（見下文）。

因爲我不想使用運行時多態性我喜歡通過像在下面的例子中立即調用lambda表達式一個constexpr功能樹轉換成std::tuple。

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, } 
} 

Answer 2

@wimalopaan你看了max66' answer還是你找到了你的想法的另一個解決方案？我試圖通過索引映射連接輸入和輸出來解決問題。但是，這比我預期的要複雜得多。以下是我如何建立索引映射：

對於輸出元組，有一個明顯的索引選擇。交換存儲整理了一下（這是簡單的，我想象），該指數讀

using Tree = std::tuple< 
    IndexNode<4>{1, 2, 3, 7},// 0 
    A,      // 1 
    B,      // 2 
    IndexNode<2>{4, 5}, // 3 
     C,     // 4 
     IndexNode<1>{6},  // 5 
     D,     // 6 
    E      // 7 
>; 

輸入包括嵌套的元組的，所以讓我們發明一些多指標：

Node(/* 1, 2, 3, 7 */ // 0, Vals<> 
    A{},    // 1, Vals<0> 
    B{},    // 2, Vals<1> 
    Node(/* 4, 5 */  // 3, Vals<2> 
    C{},    // 4, Vals<2, 0> 
    Node(/* 6 */  // 5, Vals<2, 1> 
     D{}    // 6, Vals<2, 1, 0> 
    ) 
), 
    E{}     // 7, Vals<3> 
); 

爲了計算在IndexNode中的索引，指定「包含其子節點的節點所消耗的輸出索引的數量」是有用的。在max66's answer這叫做cntT。讓我們通過函數重載使用術語rank這裏這個量和計算：

template<class> struct Type {};// helper to pass a type by value (for overloading) 

template<class Terminal> 
size_t rank_of(Type<Terminal>) {// break depth recursion for terminal node 
    return 1; 
} 

template<class... Children> 
size_t rank_of(Type<Node<Children...>>) {// continue recursion for non-terminal node 
    return (
    1 +// count enclosing non-terminal node 
    ... + rank_of(Type<Children>{}) 
); 
} 

同樣的策略可以應用來獲得在輸入​​表示每個節點的multiindices。多指令累積（通過深度遞歸）到ParentInds。

#include "indexer.hpp"// helper for the "indices trick" 
#include "merge.hpp"// tuple_cat for types 
#include "types.hpp"// template<class...> struct Types {}; 
#include "vals.hpp"// helper wrapped around std::integer_sequence 

template<class Terminal, class ParentInds=Vals<>> 
auto indices_of(
    Type<Terminal>,// break depth recursion for terminal node 
    ParentInds = ParentInds{} 
) { 
    std::cout << __PRETTY_FUNCTION__ << std::endl; 
    return Types<ParentInds>{};// wrap in Types<...> for simple merging 
} 

template<class... Children, class ParentInds=Vals<>> 
auto indices_of(
    Type<Node<Children...>>,// continue recursion for non-terminal node 
    ParentInds parent_inds = ParentInds{} 
) { 
    return indexer<Children...>([&] (auto... child_inds) { 
    return merge(
     Types<ParentInds>{},// indices for enclosing non-terminal node 
     indices_of(
     Type<Children>{}, 
     parent_inds.append(child_inds) 
    )... 
    ); 
    }); 
} 

用GCC輸出7。2：

auto indices_of(Type<Terminal>, ParentInds) [with Terminal = E; ParentInds = Vals<3>] 
auto indices_of(Type<Terminal>, ParentInds) [with Terminal = D; ParentInds = Vals<2, 1, 0>] 
auto indices_of(Type<Terminal>, ParentInds) [with Terminal = C; ParentInds = Vals<2, 0>] 
auto indices_of(Type<Terminal>, ParentInds) [with Terminal = B; ParentInds = Vals<1>] 
auto indices_of(Type<Terminal>, ParentInds) [with Terminal = A; ParentInds = Vals<0>] 

隨着由indices_of計算的索引映射我們可以構建輸出元組是這樣的：

template<class T> 
constexpr auto transform(const T& t) { 
    static_assert(
    std::is_same< 
     T, 
     Node<A, B, Node<C, Node<D> >, E> 
    >{} 
); 

    auto inds = indices_of(Type<T>{}); 

    static_assert(
    std::is_same< 
     decltype(inds), 
     Types< 
     Vals<>, 
      Vals<0>, 
      Vals<1>, 
      Vals<2>, 
      Vals<2, 0>, 
      Vals<2, 1>, 
       Vals<2, 1, 0>, 
      Vals<3> 
     > 
    >{} 
); 

    return indexer(inds.size, [&] (auto... is) {// `is` are the tuple's output inds 
    return std::make_tuple(// becomes the final output tuple 
     transform_at(
     inds.construct_type_at(is),// multiindex `Vals<...>{}` for each tuple element 
     t,// input tree 
     is.next()// used by each `IndexNode`: offset for its index computation 
    )... 
    ); 
    }); 
} 

這裏是一個完整（希望無缺陷的）工作例子（online demo）：

#include <algorithm> 
#include <iostream> 
#include <tuple> 
#include <numeric> 

//////////////////////////////////////////////////////////////////////////////// 

template<size_t i> 
struct Val : std::integral_constant<size_t, i> { 
    template<size_t dist=1> 
    constexpr auto next(Val<dist> = {}) { 
    return Val<i+dist>{}; 
    } 
}; 

template<size_t... is> 
struct Vals { 
    template<size_t i> 
    constexpr auto append(Val<i>) { 
    return Vals<is..., i>{}; 
    } 
}; 

template<size_t i0, size_t... is> 
constexpr auto front(Vals<i0, is...>) { return Val<i0>{}; } 

template<size_t i0, size_t... is> 
constexpr auto pop_front(Vals<i0, is...>) { return Vals<is...>{}; } 

//////////////////////////////////////////////////////////////////////////////// 

template<class> struct Type {}; 

template<class... Ts> 
struct Types { 
    static constexpr auto size = Val<sizeof...(Ts)>{}; 

    template<std::size_t i, class... Args> 
    constexpr auto construct_type_at(Val<i>, Args&&... args) { 
    using Ret = std::tuple_element_t<i, std::tuple<Ts...>>; 
    return Ret(std::forward<Args>(args)...); 
    } 
}; 

//////////////////////////////////////////////////////////////////////////////// 

template<std::size_t... is, class F> 
constexpr decltype(auto) indexer_impl(std::index_sequence<is...>, F f) { 
    return f(Val<is>{}...); 
} 

template<class... Ts, class F> 
constexpr decltype(auto) indexer(F f) { 
    return indexer_impl(std::index_sequence_for<Ts...>{}, f); 
} 

template<size_t N, class F> 
constexpr decltype(auto) indexer(std::integral_constant<size_t, N>, F f) { 
    return indexer_impl(std::make_index_sequence<N>{}, f); 
} 

//////////////////////////////////////////////////////////////////////////////// 

template<class... Ts> 
auto merge(Types<Ts...> done) { 
    return done; 
} 

template<class... Ts, class... Us, class... Vs> 
auto merge(Types<Ts...>, Types<Us...>, Vs...) { 
// TODO: if desired, switch to logarithmic recursion 
// https://stackoverflow.com/a/46934308/2615118 
    return merge(Types<Ts..., Us...>{}, Vs{}...); 
} 

//////////////////////////////////////////////////////////////////////////////// 

struct TerminalNode { const char* msg{""}; };// JUST FOR DEBUG 

std::ostream& operator<<(std::ostream& os, const TerminalNode& tn) { 
    return os << tn.msg << std::endl;// JUST FOR DEBUG 
} 

struct A : TerminalNode {};// INHERITANCE JUST FOR DEBUG 
struct B : TerminalNode {}; 
struct C : TerminalNode {}; 
struct D : TerminalNode {}; 
struct E : TerminalNode {}; 

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

template<size_t N> 
struct IndexNode { 
    std::array<size_t, N> mChildren; 
    constexpr IndexNode(std::array<size_t, N> arr) : mChildren(arr) {} 

    friend std::ostream& operator<<(std::ostream& os, const IndexNode& self) { 
    for(auto r : self.mChildren) os << r << ", ";// JUST FOR DEBUG 
    return os << "\n"; 
    } 
}; 

//////////////////////////////////////////////////////////////////////////////// 

template<class Terminal> 
size_t rank_of(
    Type<Terminal>// break depth recursion for terminal node 
) { 
    return 1; 
} 
template<class... Children> 
size_t rank_of(
    Type<Node<Children...>>// continue recursion for non-terminal node 
) { 
    return (
    1 +// count enclosing non-terminal node 
    ... + rank_of(Type<Children>{}) 
); 
} 

//////////////////////////////////////////////////////////////////////////////// 

template<class Terminal, class ParentInds=Vals<>> 
auto indices_of(
    Type<Terminal>,// break depth recursion for terminal node 
    ParentInds = ParentInds{} 
) { 
    std::cout << __PRETTY_FUNCTION__ << std::endl; 
    return Types<ParentInds>{};// wrap in Types<...> for simple merging 
} 
template<class... Children, class ParentInds=Vals<>> 
auto indices_of(
    Type<Node<Children...>>,// continue recursion for non-terminal node 
    ParentInds parent_inds = ParentInds{} 
) { 
    return indexer<Children...>([&] (auto... child_inds) { 
    return merge(
     Types<ParentInds>{},// indices for enclosing non-terminal node 
     indices_of(
     Type<Children>{}, 
     parent_inds.append(child_inds) 
    )... 
    ); 
    }); 
} 

//////////////////////////////////////////////////////////////////////////////// 

template<class It, class T> 
constexpr It exclusive_scan(It first, It last, It out, T init) { 
    for(auto it=first; it!=last; ++it) { 
    auto in = *it; 
    *out++ = init; 
    init += in; 
    } 
    return out; 
} 

//////////////////////////////////////////////////////////////////////////////// 

template<size_t... child_inds, class Terminal, class Offset> 
constexpr decltype(auto) transform_at(
    Vals<child_inds...> inds, 
    const Terminal& terminal, 
    Offset 
) { 
    static_assert(0 == sizeof...(child_inds)); 
    return terminal; 
} 

template<size_t... child_inds, class... Children, class Offset> 
constexpr decltype(auto) transform_at(
    Vals<child_inds...> inds, 
    const Node<Children...>& node, 
    Offset offset = Offset{} 
) { 
    if constexpr(0 == sizeof...(child_inds)) {// the IndexNode is desired 
    auto ranks = std::array{rank_of(Type<Children>{})...}; 
    exclusive_scan(std::begin(ranks), std::end(ranks), std::begin(ranks), 0); 

    auto add_offset = [] (size_t& i) { i += Offset{}; }; 
    std::for_each(std::begin(ranks), std::end(ranks), add_offset); 

    return IndexNode{ranks}; 
    } 
    else {// some child of this enclosing node is desired 
    return transform_at(
     pop_front(inds), 
     std::get<front(inds)>(node.mChildren), 
     offset 
    ); 
    } 
} 

template<class T> 
constexpr auto transform(const T& t) { 
    auto inds = indices_of(Type<T>{}); 

    return indexer(inds.size, [&] (auto... is) {// is are the tuple output inds 
    return std::make_tuple(// becomes the final output tuple 
     transform_at(
     inds.construct_type_at(is),// multiindex for each tuple element 
     t,// input tree 
     is.next()// used by each `IndexNode`: offset for its index computation 
    )... 
    ); 
    }); 
} 

//////////////////////////////////////////////////////////////////////////////// 

int main() { 
    auto tree = []() { 
    auto t = Node( // 0, Val<> 
     A{"FROM A"}, // 1, Val<0> 
     B{"FROM B"}, // 2, Val<1> 
     Node(   // 3, Val<2> 
     C{"FROM C"}, // 4, Val<2, 0> 
     Node(  // 5, Val<2, 1> 
      D{"FROM D"} // 6, Val<2, 1, 0> 
     ) 
    ), 
     E{"FROM E"}  // 7, Val<3> 
    ); 

    return transform(t); 
    }(); 

    using Tree = decltype(tree); 

    indexer(std::tuple_size<Tree>{}, [&] (auto... is) { 
    (std::cout << ... << std::get<is>(tree)); 
    }); 

    return 0; 
}