Можно ли сделать дерево constexpr? - PullRequest
Новая
       1

Можно ли сделать дерево constexpr?

1 голос
/ 26 января 2020

Я хотел бы построить constepxr древовидную структуру с фиксированным числом дочерних элементов, которые могут быть или не быть древовидными. Структура будет в состоянии ответить на вопрос «есть ли узел с индексом 2 в этом дереве?»

В идеале я хотел бы написать что-то вроде этого: 

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

К сожалению Tree ссылка на себя не компилируется.

Есть ли что-то, что я пропустил, или способ обойти это ограничение? Знаете ли вы реализацию, решающую подобную проблему?

1 Ответ

1 голос
/ 26 января 2020

Следующие работы на 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>());

}

Имейте в виду, что это генерирует много типов.

...