如何用c++递归模板定义B+树形结构

2sbarzqh 于 2022-12-15 发布在其他

关注(0)|答案(2)|浏览(112)

我正在创建一个类似B+树的数据结构，不同之处在于每个节点级别能够保存不同类型的值（用于缓存目的），并且具有不同数量的子节点。
例如：

根节点保存多达8个层1节点子节点和Struct1的值，
level1节点保存多达16个level2节点子节点和Struct2的值，
level2节点保存多达32个叶节点子节点和Struct3的值，
叶节点保存StructLeaf的值。

我不需要树结构在运行时改变，所以我想使用模板来配置它。我期望上面例子的示例化看起来像这样：

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

和模板定义，这不是一个实际代码，只是我认为它看起来像：

// 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;
}

我知道如何使用递归的int模板，不使用TData，只使用ChildrenSize来创建这个结构，但我也想知道是否或如何向模板中添加数据类型？
我试着使用模板的模板，但它看起来像是另一个用例，而不是传递对，因为我找不到一种方法来访问内部模板值。

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

c++

来源：https://stackoverflow.com/questions/74792297/how-to-define-a-btree-like-structure-with-c-recursive-templates

2条答案

按热度按时间

gab6jxml1#

不完全是你问的但是...一些建议...
1.如果您只在基本情况下需要strutLead，请将其放在模板参数列表的最后一个位置，而不是第一个位置
1.可以将级别的维度和类型“ Package ”为其他类型的模板参数，例如TWrapper
因此tree变量变为

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

可以实现Node声明和定义TWrapper

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

并声明Node如下

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

接收强制类型名和类型名的可变序列
递归case的声明可以简单地是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;
};

在这里，您从第一个TWrapper中获取数组的维数和TData类型，然后定义下面的Node，只需传递其余的模板参数。
基本情况可以简单地写成Node的另一个特殊化，如下所示

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

下面是一个完整的编译示例

#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;
}

赞(0）回复(0）举报 2022-12-15

kgqe7b3p2#

自然递归的描述方式是每一级只知道下一级，类似于：

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

这可能会区分内部节点类型和顶层树，但您已经了解了这一点。
注意，你的代码草图不是递归的，而是可变的，你仍然可以向下递归，但是看起来比一开始就递归定义它要花更多的工作。

赞(0）回复(0）举报 2022-12-15

我来回答

如何用c++递归模板定义B+树形结构

2条答案

相关问题

热门标签

最新问答