c++ - 用C++转换树

我有一个由不同类型的节点组成的异构n元树，例如:

class Node { }

class Subnode1 : public Node
{

}

class Subnode2 : public Node
{
private:
  unique_ptr<Subnode1> child;

public:
  Subnode1* getChild() { return child.get(); }
}

class Subnode4 : public Subnode2 { }

class Subnode3 : public Node
{
private:
  list<unique_ptr<Subnode2>> children;
public:
  // getter
}

// etc

该结构可以包含任何数量的节点类型，并且将来会进行扩展。

我实现了一种访问树的方法，该方法允许我自定义访问每个节点时的操作，该操作基本上是通过以下方式实现的:

void genericVisit(Node* node) {
  if (dynamic_cast<Subnode2>(node))
    visit(static_cast<Subnode2*>(node));
  // etc
}

virtual void visit(Subnode2* node) {
  if (node->getChild())
    genericVisit(node->getChild());
}

// etc

它能很好地遍历树，但是现在我需要能够用其他子树替换子树，因此我正在考虑遵循的最佳方法，而不会过多地更改结构。

最好的解决方案是让getter直接返回unique_ptr<Subnode2>&，这样我就可以对唯一指针进行访问，并且可以在访问智能指针时更改其内容。这会起作用，但是unique_ptr不是多态的，并且无法将调用分派(dispatch)到最专门的方法，例如:

void genericVisit(unique_ptr<Node>& node) { // NON WORKING CODE
  if (dynamic_cast<unique_ptr<Subnode2>&>(node))
    visit(static_cast<unique_ptr<Subnode2>&>(node));
  // etc
}

因此，我想知道哪种方法是解决该问题的最佳方法，请注意，在遍历树时，只要更改当前子树的内容而不更改对父节点中该节点的引用，(通过使用一个unique_ptr)我看不到任何问题。

最佳答案

解决必须在unique_ptr<T>上进行分派(dispatch)的问题的一种方法是返回指针，就像您在访问者中那样传递指针，但是将返回类型更改为Node*，如下所示:

// Top-level function stays the same
Node* genericVisit(Node* node) {
    if (dynamic_cast<Subnode2>(node)) {
        return visit(static_cast<Subnode2*>(node));
    }
    // etc
}
// Specialized overloads can return replacements as they go
virtual Node* visit(Subnode2* node) {
    if (mustReplace()) {
        Subnode1 *myReplacement = ...
        return myReplacement;
    }
    if (node->getChild()) {
        Node *replacement = genericVisit(node->getChild());
        // nullptr means no replacement; non-null means we replace the child
        if (replacement) {
            node->setChild(replacement);
        }
    }
    return nullptr;
}

这种方法要求实现者在执行替换之前要注意返回的内容(即是否为nullptr)。另一方面，它由进行访问者调用的功能来决定执行替换的最终决定，最终转化为对内部的更多控制，即更好的封装。

关于c++ - 用C++转换树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27708139/