如何为仅含InnerNode与Leaf的树实现模板方法？求相关惯用法及最佳实践

问题背景 #

我正在实现一棵仅包含InnerNode（内部节点）和Leaf（叶子节点）的树，常规继承实现如下：

class Node { public: virtual ~Node() = default; };
class InnerNode: public Node { std::vector<std::unique_ptr<Node>> children; ... };
class Leaf: public Node { ... };

由于模板方法无法声明为虚函数，我采用了如下 workaround 实现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>(f)); 
        } else if (Leaf* leaf = get_leaf()) { 
            leaf->for_each_leaf(std::forward<F>(f)); 
        } 
    } 
};
class InnerNode: public Node { 
    // ... 
    InnerNode* get_inner_node() override { return this; } 
    template <class F> void for_each_inner_node(F&& f) { 
        // 递归遍历子节点+处理当前内部节点逻辑
        for (auto& child : children) {
            child->for_each(std::forward<F>(f));
        }
        f(*this);
    } 
};
class Leaf: public Node { 
    // ... 
    Leaf* get_leaf() override { return this; } 
    template <class F> void for_each_leaf(F&& f) { 
        f(*this);
    } 
};

我想了解：

1. 这个惯用法的名称是什么？
2. 使用dynamic_cast、std::variant或是在Node中存储类型信息这些替代方案的性能表现如何？
3. 这类问题的最佳实践是什么？

一、惯用法名称 #

你当前使用的模式叫做**「类型标记（Type Tagging）」，也可以归为「通过虚访问器实现安全向下转型」**的范畴。它本质上是用虚函数暴露具体类型，绕过了模板不能作为虚函数的限制，属于双分派（Double Dispatch）的一种简化变体——不过严格意义上的双分派通常处理两个类型的交互，这里更偏向于单类型的动态识别。

二、各替代方案的性能对比 #

以下基于常见编译器优化级别（O2/O3）分析：

1. 你的当前实现（虚访问器+静态转型） #

• 性能表现：最坏情况是2次虚函数调用+1次非虚模板函数调用，但实际中编译器会优化掉无效分支（比如get_inner_node返回非空时，get_leaf的分支会被完全消除）。现代CPU对虚函数调用的分支预测命中率很高，开销非常小，且模板函数可完全内联，遍历性能接近手写非多态代码。
• 优势：类型安全，无需额外存储，代码符合传统OOP继承风格。

2. dynamic_cast方案 #

class Node { 
    // ...
    template <class F> void for_each(F&& f) {
        if (auto* inner = dynamic_cast<InnerNode*>(this)) {
            inner->for_each_inner_node(std::forward<F>(f));
        } else if (auto* leaf = dynamic_cast<Leaf*>(this)) {
            leaf->for_each_leaf(std::forward<F>(f));
        }
    }
};

• 性能表现：开销明显高于你的当前实现。dynamic_cast需要依赖RTTI（运行时类型信息）遍历继承链或查询类型表，不仅调用本身更慢，还会增加二进制体积和缓存压力。
• 优势：代码更简洁，无需额外声明虚函数。

3. 手动存储类型信息（Type Tag） #

class Node { 
public:
    enum class Type { Inner, Leaf };
    virtual ~Node() = default;
    Type get_type() const noexcept { return type_; }
protected:
    Node(Type type) : type_(type) {}
private:
    Type type_;
};

class InnerNode : public Node {
public:
    InnerNode() : Node(Type::Inner) {}
    // ...
};

class Leaf : public Node {
public:
    Leaf() : Node(Type::Leaf) {}
    // ...
};

template <class F> void Node::for_each(F&& f) {
    switch(get_type()) {
        case Type::Inner:
            static_cast<InnerNode*>(this)->for_each_inner_node(std::forward<F>(f));
            break;
        case Type::Leaf:
            static_cast<Leaf*>(this)->for_each_leaf(std::forward<F>(f));
            break;
    }
}

• 性能表现：这是性能最优的方案之一。get_type()是简单的成员变量读取（可被编译器内联为常量），switch会被优化为跳转表或直接分支，完全没有虚函数调用开销，静态转型也无运行时成本。
• 劣势：需要手动维护类型枚举，新增节点类型时必须同步更新枚举和switch分支，容易遗漏出错。

4. std::variant方案（放弃继承） #

struct InnerNode;
struct Leaf;

using Node = std::variant<std::unique_ptr<InnerNode>, std::unique_ptr<Leaf>>;

struct InnerNode {
    std::vector<Node> children;
    template <class F> void for_each(F&& f) {
        f(*this);
        for (auto& child : children) {
            std::visit([&f](auto&& node_ptr) { node_ptr->for_each(f); }, child);
        }
    }
};

struct Leaf {
    template <class F> void for_each(F&& f) {
        f(*this);
    }
};

• 性能表现：现代编译器对std::visit优化极佳，尤其是变体类型数量少（仅2种）时，会被编译为类似手动类型判断的分支，性能接近手动Type Tag方案，远优于dynamic_cast。
• 优势：无需继承体系，符合现代C++值语义风格，避免多态切片问题，新增节点类型仅需更新variant定义。
• 劣势：需要熟悉std::visit和模板元编程，递归遍历写法稍显复杂。

三、最佳实践 #

选择方案需结合场景需求：

• 极致性能+固定节点类型：优先选择手动Type Tag方案，性能最优且逻辑清晰。
• 节点类型可能扩展+代码安全：你的虚访问器方案或std::variant方案都是不错选择——前者贴合传统OOP，后者更符合现代C++风格。
• 代码简洁优先+性能要求不极端：可考虑dynamic_cast，但注意RTTI的额外开销（部分场景可能需要关闭RTTI，此时该方案不可用）。

另外需要注意：你当前代码中std::forward(f)应改为std::forward<F>(f)，才能正确保留函数对象的左值/右值语义。

内容的提问来源于stack exchange，提问作者eyelash