C++:分支节点和叶节点的单独类？

Question

我正在制作一棵树(本质上是一个前缀树，但用于数字而不是字符串)，它是从数字元组的排序列表构建的((1,1,2)，(1,2,5)，(2 ,1,0) 等...)，每一个都与一个标量值相关联(最有可能是 int 或 double)。由于它只构建一次然后迭代/搜索了几次，我计划使用 std::vectors 来保存每个节点的子节点。要搜索树，我只需要调用 std::lower_bound 对每个节点的 _children vector 进行二分搜索，它将包含每个节点的 std::pairs 及其各自的键。但是，底部节点必须包含一个 vector ， vector 对由每个元组中的最后一个条目及其各自的值组成，因此必须是与 BranchNode 不同的类型。代码如下所示:

class GenNode
{
};

template<typename key_type,typename value_type>
class BranchNode : GenNode
{
    void insert(std::pair< std::vector<key_type> , value_type>);
private:
    std::vector< std::pair<key_type,GenNode*> > _children;
};

template<typename key_type,typename value_type>
class LeafNode : GenNode
{
private:
    std::vector< std::pair<key_type,value_type> > _children;
};

但是，这真的很丑陋，因为这两个类都必须继承无用的 GenNode 类，以便每个 BranchNode 的子节点可以是其他 BranchNode 或 LeafNode...有没有更好的方法来做到这一点？

Answer 1

如果你想将两种类型存储在同一个 vector 中，你需要相关的类(一个继承自另一个或两个继承自共同祖先)。

拥有一个空的共同祖先可能看起来很丑陋。但是，如果将搜索操作(以及其他迭代/处理)作为虚方法放入基类，并在 BranchNode 和 LeafNode(实现会有所不同)。

在这种情况下，基类也应该被模板化。 我的意思是有一个像这样的基类:

template<typename key_type,typename value_type>
class GenNode {
 public:
  virtual value_type search(key_type key) = 0;
};