5

我正在制作一棵树（本质上是一棵前缀树，但对于数字不是字符串），它是由数字元组的排序列表构建的（ (1,1,2), (1,2,5), (2,1, 0) 等...)，每个都与单个标量值相关联（最有可能是 int 或 double）。由于它只构建一次，然后迭代/搜索了几次，我计划使用 std::vectors 来保存每个节点的子节点。要搜索树，我只需要调用 std::lower_bound 对每个节点的 _children 向量进行二进制搜索，该向量将包含每个节点的 std::pairs 及其各自的键。但是，底部节点必须包含一个向量，该向量由每个元组中的最后一个条目及其各自的值组成，因此必须与 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……有没有更好的方法来做到这一点？

4

2 回答 2

2

是的，您需要两种不同的类型。事实上，像这样的 ( Leaf OR Node) 被称为有区别的联合。

有几种实现它的方法，但在 C++ 中，具有两个派生类的公共基类可能是最常见的。

使用递归包装器的一个有趣的替代方案是使用一个公共boost::variant基础。这特别有趣，因为它避免使用指针（从而为您处理内存管理）。

于 2013-06-11T19:02:18.463 回答
2

如果要将两种类型存储在同一个向量中，则需要相关的类（一个继承自另一个或都继承自共同祖先）。

拥有一个空洞的共同祖先可能看起来很丑陋。但是，如果您将搜索操作（以及其他迭代/处理）作为虚拟方法放入基类中，并在BranchNodeand中实现它LeafNode（实现方式会有所不同），您可以获得更优雅的设计。

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

template<typename key_type,typename value_type>
class GenNode {
 public:
  virtual value_type search(key_type key) = 0;
};
于 2013-06-11T18:48:46.800 回答