c++ - 避免在树结构中使用强制转换

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() {}
  };
  

  叶子节点和分支节点可以不同地实现功能。叶子总是可以返回空范围，而分支可以返回空键和值。或者，他们可以要求用户使用 is_leaf ，如果调用了错误类型的函数，则抛出异常。

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

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