我有一个应用程序，想要计算通过 bool 运算(内部节点)组合的图元树(叶节点)的不同表示(网格、体素化、带符号距离函数...)。
我的第一个方法是为每个不同的表示编写一个带有虚拟 getter 函数的抽象基类，并在各自的节点缓存中间结果，只要它们的子树没有变化(这会刷新它们缓存)。
但是，我对树结构与每个不同表示的丑陋耦合不满意。为了缓解这种情况，我删除了抽象基类，而是为每个表示设置了一个访问者。
这巧妙地将树与表示分离，但给我留下了一个问题，我现在需要在其他地方缓存中间结果，这就是我的问题开始的地方。
长话短说
如何在树的内部节点缓存(任意多种不同类型的)中间值而不使树依赖于值类型？
我的方法
需求提供了两种选择:
- 将数据存储在树中，但类型删除
- 将数据存储在树的外部并以某种方式将其“连接”到节点
第一个让我对一些效率问题感到困惑:我可以很容易地在节点中添加一个 boost::any 的容器(或类似的东西)，但是每个访问者都必须搜索整个它自己的数据的容器。
第二个中的分离引入了保持缓存与当前树保持同步的问题。如果树中有更改(删除、更改节点)，缓存值至少必须无效。我的直觉是使用一些哈希函数和 unordered_map 但我也遇到了一些问题:
- 我不能使用树节点本身作为键，所以我需要引入另一个类，它只引用树节点并在树中表示它们
- 从
unordered_map的键中引用值需要删除其引用被删除的所有条目，或者我们在unordered_map中有一个悬空引用(/指针)，这可能在重新哈希时被触发 - 树中的更改需要重建
unordered_map，因为键可能已更改
我是否遗漏了一些明显的解决方案？ 您喜欢哪种方法(为什么)？
最佳答案
我曾经遇到过类似的问题，我的解决方法如下:
- 让每个节点都有一个唯一的标识符。
- 让每个节点都有一个版本号。使节点的计算值无效的修改只会增加版本号。
- 让每个访问者都有一个缓存映射，其中 ID 对是键，映射到版本/值对。
- 当(重新)遍历树时，在 map 中查找节点条目。如果版本正确，则使用缓存的值。如果已过期，则计算新值并替换旧版本/值对。
起初，我使用节点的地址作为 ID，但出于内存原因，我不得不重用子树并选择节点的路径作为 ID。这样的路径的优点是它可以由每个访问者计算并且不需要存储在节点处。在我的例子中，每个节点最多可以有两个 child ，所以一条路径只是一组左/右决策，它可以存储在一个简单的无符号整数中并进行一些位移(我的树从未达到 32 的深度，因此 32 位无符号作为 key 绰绰有余)。
关于c++ - 如何在树访问者中进行每个节点缓存，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23995361/