c++ - 避免在树结构中使用 cast

Question

我们正在考虑需要类型转换的设计，但感觉不对。显然用谷歌搜索了这个问题，但没有找到答案。将不胜感激关于如何避免类型转换需要的建议。这是一个精简的示例(请执行任何拼写错误，尚未编译)。

struct NodeBase
{
   enum class type
   {
     value,
     aggregate
   };
   type m_type;
};

struct NodeAggregate : public NodeBase
{
   std::vector<NodeBase*> m_list;
};

struct NodeValue : public NodeBase
{
   std::string m_key;
   std::string m_value;
};

上面的类可以用来创建一个多层次的树结构。

“难点”在于开发一种无需强制转换即可遍历此结构的算法。基类中的类型变量应标识正确的类型，并将转换次数减少为单个，但不会避免转换。

这个问题的替代设计是什么？

感谢任何评论。

Answer 1

您似乎正在重新实现的模式称为 tagged union, or variant ，通常与访客模式配对。我建议使用现有的实现，而不是自己动手。

但也要考虑替代实现:

• 使用同类节点。让每个节点都能够存储子列表和数据。这样你只需要一种类型的节点，不需要强制转换。如果只有叶子可以有数据，那么您可以在算法中实现该限制，而不是数据结构。

  struct Node
  {
       std::vector<Node*> m_list;
       std::string m_key;
       std::string m_value;
  };
  

• 或者使用虚函数:

  struct NodeBase
  {
      virtual       bool  is_leaf()            = 0;
      virtual const range children()     const = 0;
      virtual       range children()           = 0;
      virtual const std::string* key()   const = 0;
      virtual       std::string* key()         = 0; // if the tree is not sorted by key
      virtual const std::string* value() const = 0;
      virtual       std::string* value()       = 0;
      virtual ~NodeBase() {}
  };
  

  叶节点和分支节点可以实现不同的功能。 Leaf 总是可以返回空范围，而 branch 可以返回 null key 和 value。或者，他们可以要求用户使用 is_leaf，并在调用错误类型的函数时抛出异常。

  我没有直接返回对 vector 的访问，而是使用了一个 range 类型，它应该是一对迭代器，它允许您封装底层容器的选择。

在所有这些设计中，您可以将键和值类型模板化以获得更好的通用性。