4

我处于需要在多态对象树的许多实例之间共享数据的情况，但话又说回来，我需要共享数据是“每棵树”，因此在基类中使用静态类成员并不是一个真正的选择.

我不想用指向共享数据的额外成员指针来“负担”每个实例，所以我目前的方法（考虑到我使用树）是将共享数据作为树根节点的成员，并且每次访问共享数据根据访问“树全局”数据的特定节点的深度，通过一系列间接链接。

由于在某些情况下共享数据会被非常频繁地访问（每秒数百万......至少这是预期的），我想知道是否有一些设计模式可以帮助我避免间接到达根节点，同时仍然不会给对象的足迹带来额外的膨胀。

虽然可以将根节点指针“缓存”为本地，例如访问共享数据的紧密循环，但在许多情况下，功能将沿着树节点级联，甚至在过程中切换树，因此缓存根节点指针只适用于狭隘的语境。

  • 请注意，静态成员的提及并不将实现范围限制为 C++，我还添加了 C 标记，因为此时我对任何想法持开放态度。
4

2 回答 2

0

所有与树节点交互的方法都将指向根的指针作为它们的第一个参数。

享元包装类可以隐藏此实现细节，您可以通过不透明类访问树节点，该类具有真正的树节点指针以及指向其中的根指针。如果您要求一个孩子，它会返回另一个蝇量级。

现在你的树缺少额外的指针，但接口类有额外的指针。

如果您的树节点是不可变的（逻辑上），您甚至可以复制它们的状态以降低间接成本。

template<class Data>
struct internal_tree {
  Data d;
  std::unique_ptr<internal_tree> left;
  std::unique_ptr<internal_tree> right;
};

template<class Data>
struct flyweight_tree {
private:
  internal_tree* internal = nullptr;
  internal_tree* root = internal;
  flyweight_tree(internal_tree* t, internal_tree* r):internal(t),root(r) {}
public:
  flyweight_tree() {}
  flyweight_tree(internal_tree* r):internal(r) {}
  flyweight_tree left() const { return { internal->left.get(), root }; }
  flyweight_tree right() const { return { internal->right.get(), root }; }
};

现在我们的实际internal_tree数据结构不存储指向根的指针。使用它的代码通过 a 访问它flyweight_tree，它存储指向根的指针，但指向根的指针仅存储在访问点，从不长期存储。

如果您想要 a parent，您甚至可以将其实现为享元，其中flyweight_tree存储std::vector指向父级的指针（而不是root）。这在你的树节点中节省了另一堆内存（没有指向父节点的指针，但是每个使用它的人都可以得到父节点，因为他们通过 使用它flyweight_tree）。

我们可以在 中实现大部分工作internal_tree，它将flyweight_tree存储的信息作为参数，或者我们可以在其中实现大部分树逻辑flyweight_tree并将其保留internal_tree为紧凑的“长期存储”结构。

于 2014-06-15T14:14:41.760 回答
0

我能想到的可能性是：

  • 如果您的根数有限，请将偏移量（例如在 uint8_t 中）存储到具有您的根的静态数组中。例如，如果您只有 5-10 个根，则无需为每个节点存储高达 64 位。
  • 为什么不在自己的进程中运行每个“树”（在操作系统级别）？这样，每个根都可以存储为静态数据并全局访问。
  • 如果你可以限制节点的数量，也许你可以使用一个特殊的分配器：首先在给定内存边界的开头分配你的根，例如 0x0010000、0x0020000 等......然后用 a 检索根的地址每个节点的简单减法/位移？但是您必须能够确保您可以在每棵树的内存区域内分配所有节点。
于 2018-04-19T16:56:56.300 回答