I'm creating a b tree like data structure, the difference being each node level is capable of holding different type of values (for caching purposes) and having different amount of children.

E.g.:

• root-node holds up to 8 level1-node children and a value of Struct1,
• level1-node holds up to 16 level2-node children and a value of Struct2,
• level2-node holds up to 32 leaf-node children and a value of Struct 3,
• leaf-node holds a value of StructLeaf.

I don't need tree structure to change at runtime, so I want to use templates to configure it. I'm expecting instantiation of example above to look something like this:

Tree<StructLeaf, <8, Struct1>, <16, Struct2>, <32, Struct3>>()

and template definition like this, this is not an actual code, only how I suppose it may look like:

// variadic template recursion 'entrypoint'
template<
    typename TLeafData, // do I have to set leaf data before variadic template, even if it is of different structure?
    <int TChildrenSize, typename TData>... TChildNodes> // list of pairs of nodes configurations, how to make it a variadic of pairs?
>
class Node;


// template recursion body
template<
    typename TLeafData, //same as before
    <int TChildrenSize, typename TData> TNode, // values for the current node, how to define a pair?
    <int TChildrenSize, typename TData>... TChildNodes> // same as before
>
class Node {
    TNode.TData data; // how to access TNode.TData?
    std::array<Node<TLeafData, TChildNodes...>, TNode.TChildrenSize> children; // how to pass TChildNodes and access TNode.TChildrenSize?
}


// template recursion end
template<
    typename TLeafData, //same as before
    <> // empty template to stop recursion, how to define it?
>
class Node {
    TLeafData data;
}

I see how to make this structure without TData, only with ChildrenSize, by just using recursive template of int, but I also wander if or how is it possible to add data type to the template?

---

I tried using template of template for this, but it looks like it is for another usecase other than passing pairs as I couldn't find a way to access the internal template values.

template<template<int A, typename B> typename C>
class AClass {
    C.B data; // type B is unaccessable
}

CodePudding user response：

Not exactly what you asked but... some suggestions...

1. if you need strutLead only in the ground case, put it in the last position of the template parameter list, not in the first position
2. you can "wrap" the dimension and the type of the level as template parameter of an additional type, say it TWrapper

So your tree variable become

Node<TWrapper<8u, Struct1>, TWrapper<16u, Struct2>,
     TWrapper<32u, Struct3>, StructLeaf>  tree;

You can realize Node declaring and defining TWrapper

template <std::size_t, typename>
struct TWrapper
{ };

and declaring Node as follows

// template declaration
template <typename, typename...>
class Node;

as receiving a mandatory typename and a variadic sequence of typenames

The declaration of the recursion case can simply be a specialization of Node as follows

// recursion case Node
template <std::size_t Dim, typename TData, typename ... Ts>
class Node<TWrapper<Dim, TData>, Ts...>
{
  TData  data;

  std::array<Node<Ts...>, Dim>  children;
};

where you get the dimension of the array and the TData type from the first TWrapper and you define the following Node simply passing the remaining template parameters.

The ground case can be simply written as another specialization of Node as follows

// groud case Node
template <typename TData>
class Node<TData>
{
  TData  data;
};

A full compiling example follows

#include <array>

template <std::size_t, typename>
struct TWrapper
{ };

// template declaration
template <typename, typename...>
class Node;

// recursion case Node
template <std::size_t Dim, typename TData, typename ... Ts>
class Node<TWrapper<Dim, TData>, Ts...>
{
  TData  data;

  std::array<Node<Ts...>, Dim>  children;
};

// groud case Node
template <typename TData>
class Node<TData>
{
  TData  data;
};

struct Struct1 {};
struct Struct2 {};
struct Struct3 {};
struct StructLeaf {};

int main()
{
  Node<TWrapper<8u, Struct1>, TWrapper<16u, Struct2>,
       TWrapper<32u, Struct3>, StructLeaf>  tree;
}

CodePudding user response：

The naturally recursive way of describing this is for each level only to know about the next, something like:

using MyTree = Tree<Struct1, 8,
                    Tree<Struct2, 16,
                         Tree<Struct3, 32,
                              Leaf<StructLeaf>
                              >
                        >
                   >;

possibly this should differentiate between the internal node types and the top-level tree, but you get the idea.

---

Note that your code sketch is not recursive, but variadic. You can still recurse down that, but it seems like more work than just defining it recursively in the first place.