Nested Requirements for Tree Data Structure with heterogeneous Nodes

Niklas_Winter 0
Viewed 63

Objective:

I want to implement a tree data structure with non-identical nodes to manage my data. In general, the tree consists of 2 different type of nodes, namely, "Nodes" and "LeafNodes". Those nodes which have no children are considered to be "LeafNodes", which will be used to store data. Within the tree all nodes are tagged with metadata. The tree must be created at compile-time.

How:

My current implementation uses type template parameters to tag all nodes with metadata. The concept "Header" is used to specify the requirements of a header-type. If the node isn't a specialization of "LeafNode", "Nodes/LeafNodes" specializations are passed to specify the children of that node. The concept "Nodelike" is used to indicate how a specialization of "Node/LeafNode" has to look like.

Error:

I get a template constraint failure when specifying my tree type

using Tree = Node <
    Header0<0>,
    LeafNode<Header1<0,20,5>>,
    LeafNode<Header1<1,20,'f'>>,
    LeafNode<Header1<2,20,4.4>>
>;

Unfortunately, I can't interpret the compiler error so that I have no hint how to resolve the error. I am using the compiler "x86-64 gcc 12" with the following flags "-std=c++20 -O3". Here is the not working online code: Code

Implementation:

using namespace std;


template<class T>
concept LeafHeader = requires (){
    {T::ID} -> convertible_to<uint8_t>;
    {T::size} -> convertible_to<size_t>;
    T::dValue;
};

template<class T>
concept NodeHeader = requires (){
    {T::ID} -> convertible_to<uint8_t>;
};

template<class T>
concept Header = NodeHeader<T> || LeafHeader<T>;

template<class T>
concept NodeLike = requires(T){
    is_object_v<T>;
    requires T::Header;

};


template<LeafHeader H>
struct LeafNode final{

    // Resource Header
    static constexpr H header{};

    // Instances
    using type = typename H::type;
};

template<NodeHeader H, NodeLike... N>
struct Node{
    static constexpr H header{};
    tuple<N...> childs;

};

template<uint8_t I, std::size_t S, auto V>
struct Header1{
    static constexpr uint8_t ID = I;
    static constexpr size_t size = S;
    using type = decltype(V);
    static constexpr type dValue = V;
};

template<uint8_t I>
struct Header0{
    static constexpr uint8_t ID = I; 
};


using Tree = Node <
    Header0<0>,
    LeafNode<Header1<0,20,5>>,
    LeafNode<Header1<1,20,'f'>>,
    LeafNode<Header1<2,20,4.4>>
>;

int main(){
    Tree t;
}
variadic-templates tree c++-concepts c++20 c++
1 Answers

There are two problems with the definition of the NodeLike:

template<class T>
concept NodeLike = requires(T) {
  is_object_v<T>;
  requires T::Header;
};

First, the requires-clause only checks the validity of the expression, so is_object_v<T> is useless here because it is always valid, you should use the nested requires, but it is more appropriate just to move it outside the requires-clause.

Second, requires T::Header is not satisfied in your case, because class Node does not have a static variable named Header (but header, I suspect it's a typo), and since you're using the nested-requires, T::Header will be evaluated, which is never satisfied because the variable cannot be converted to bool.

You can just use T::header to check if T has a static variable named header, so this should work:

template<class T>
concept NodeLike = is_object_v<T> && requires { T::header; };
康桓瑋0
Related