c++ - 如何为只有两种节点的树实现模板方法？

Question

我正在实现一棵树，其中每个 Node 只是一个 InnerNode 或一个 Leaf，我通常会这样实现:

class Node {
public:
    virtual ~Node() = default;
};

class InnerNode: public Node {
    std::vector<std::unique_ptr<Node>> children;
    ...
};

class Leaf: public Node {
    ...
};

现在我想要一个模板方法for_each 但是template methods cannot be virtual .要解决这个问题，我可以像这样实现 for_each:

class Node {
    ...
    virtual InnerNode* get_inner_node() {
        return nullptr;
    }
    virtual Leaf* get_leaf() {
        return nullptr;
    }
    template <class F> void for_each(F&& f) {
        if (InnerNode* inner_node = get_inner_node()) {
            inner_node->for_each_inner_node(std::forward(f));
        }
        else if (Leaf* leaf = get_leaf()) {
            leaf->for_each_leaf(std::forward(f));
        }
    }
};

class InnerNode: public Node {
    ...
    InnerNode* get_inner_node() override {
        return this;
    }
    template <class F> void for_each_inner_node(F&& f) {
        ...
    }
};

class Leaf: public Node {
    ...
    Leaf* get_leaf() override {
        return this;
    }
    template <class F> void for_each_leaf(F&& f) {
        ...
    }
};

或者我可以使用 dynamic_cast 或 std::variant 或者我可以将类型存储在 Node 中。在最坏的情况下，我的 for_each 代码使用两个虚方法调用和一个非虚方法调用，但我想知道替代方法的性能如何。是否有这种成语的名称，是否有解决它的最佳实践？

Answer 1

作为 template 的替代方案，您可以使用 std::function:

class Node {
public:
    // ...
    virtual ~Node() = default;
    virtual void for_each(std::function<void(/*DataType*/)> f) = 0;
};

class InnerNode : public Node {
    std::vector<std::unique_ptr<Node>> children;
public:
    //...
    void for_each(std::function<void(/*DataType*/)> f) override {
        // ...
    }
};

class Leaf : public Node {
public:
    //...
    void for_each(std::function<void(/*DataType*/)> f) override {
        // ...
    }
};