是否可以制作 constexpr 树？

Question

我想构建一个 constepxr 树结构，其中包含固定数量的子节点，这些子节点可能是也可能不是树。该结构将能够回答问题 "is there a node present at index 2 in this tree?"

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

  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>());

}

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

是否可以制作 constexpr 树？

Is it possible to make a constexpr tree?

c++

tree

constexpr