是否可以制作constexpr树？

Question

我想用固定数目的子代（可能不是树）来构建constepxr树结构。该结构将能够回答问题“此树的索引2处是否存在节点？”

理想情况下，我想写这样的东西：

  struct Tree {
   std::array<std::optional<Tree>, 5> children; // 5 children max for each tree
  };

很遗憾，Tree引用其自身未编译。

我有什么想念的，还是可以解决此限制的方法？您知道解决类似问题的实现吗？

Answer 1

以下内容适用于C ++ 17。这应该是可能的，但在以前的版本上会更烦人：

#include <tuple>

struct no_node{};

template<class... ChildTrees>
struct Tree {
    using tuple_t = std::tuple<ChildTrees...>;
    tuple_t children;

    template<int N>
    static constexpr bool has_child() {
        if constexpr(N >= sizeof...(ChildTrees)) {
            return false;
        } else {
            return !std::is_same_v<std::tuple_element_t<N, tuple_t>, no_node>;
        }
    }
};


int main()
{
    Tree<> leaf;
    Tree<no_node, decltype(leaf)> right;
    static_assert(!leaf.has_child<0>());
    static_assert(right.has_child<1>());
    static_assert(!right.has_child<0>());
    static_assert(!right.has_child<2>());

}

请注意，这会生成很多类型。