c++ - 将树展平为链表c++，没有指针

Question

我正在研究遗传算法，我想尝试将一些函数放入 cuda 中，看看是否可以实现有值(value)的加速。

目前的数据结构是一棵节点树，其中函数节点包含指向它们可能拥有的任何子节点的指针 vector 。我相信我需要将这棵树折叠成一个链表，可能是一个节点 vector (不是指针)。这些节点将包含其子节点的整数索引列表。通过这种方式，我可以将结构按值传递给 cuda。

  root/             (0)
  ├── add           (1)
  │   ├── 5         (2)
  │   └── divide    (3)
  │       ├── 10    (4)
  │       └── 5.7   (5)
  └── multiply      (6)
      ├── 1.2       (7)
      └── 77        (8)

它可以很容易地展平，但我担心进行这些更改将需要一些自定义函数，并且可能比 node->childNode[x] 样式结构的计算成本更高。

例如，如果我想用数字 7 替换除法及其子结构，我需要:

• 流行成员 4,5
• 将索引 3 处的分界线更改为数字 7。
• 更新根函数，使其第二个子函数的引用现在为 4。
• 更新乘法函数，现在是4，也就是子节点现在是5和6

一定有更好的办法吧？我不是 C++ 专家，所以我正在寻求建议，代码示例会非常有帮助!

Answer 1

我建议保持你的树结构完全原样，除了将你的指针替换为数组中的索引，如 tera 所说。

我在说什么数组？您需要设置一个内存池(也称为固定大小块分配器)。你可以谷歌这个。池基本上是一个数组，无论您的节点类型是什么。您应该提前选择一个最大大小(您在树中需要的最大节点数)。然后，您永远不必调整/增加此数组的大小。您的内存池类将具有分配和释放方法，但这些方法对数组的索引而不是指针进行操作。

通过这种方法，您将能够非常便宜地完成您提到的树修改——使用内存池，分配和删除项目非常便宜，而且您永远不会在内存中复制/移动节点。

您会将树的根(同样，只是一个索引，而不是指针)连同内存池的数组传递给 GPU。