title: How to implement template methods for a tree that has only two types of nodes?
body: <p>I'm implementing a tree where each <code>Node</code> is only either an <code>InnerNode</code> or a <code>Leaf</code> which I would normally implement like this:</p>
  
  <pre><code>class Node {
  public:
      virtual ~Node() = default;
  };
  
  class InnerNode: public Node {
      std::vector&lt;std::unique_ptr&lt;Node&gt;&gt; children;
      ...
  };
  
  class Leaf: public Node {
      ...
  };
  </code></pre>
  
  <p>Now I would like to have a template method <code>for_each</code> but <a href="https://stackoverflow.com/q/7968023/799849">template methods cannot be virtual</a>. To work around this I could implement <code>for_each</code> like this:</p>
  
  <pre><code>class Node {
      ...
      virtual InnerNode* get_inner_node() {
          return nullptr;
      }
      virtual Leaf* get_leaf() {
          return nullptr;
      }
      template &lt;class F&gt; void for_each(F&amp;&amp; f) {
          if (InnerNode* inner_node = get_inner_node()) {
              inner_node-&gt;for_each_inner_node(std::forward(f));
          }
          else if (Leaf* leaf = get_leaf()) {
              leaf-&gt;for_each_leaf(std::forward(f));
          }
      }
  };
  
  class InnerNode: public Node {
      ...
      InnerNode* get_inner_node() override {
          return this;
      }
      template &lt;class F&gt; void for_each_inner_node(F&amp;&amp; f) {
          ...
      }
  };
  
  class Leaf: public Node {
      ...
      Leaf* get_leaf() override {
          return this;
      }
      template &lt;class F&gt; void for_each_leaf(F&amp;&amp; f) {
          ...
      }
  };
  </code></pre>
  
  <p>Alternatively I could use <code>dynamic_cast</code> or <code>std::variant</code> or I could store the type inside <code>Node</code>. In the worst-case my code for <code>for_each</code> uses two virtual method calls and one non-virtual method call, but I wonder what the performance of the alternative approaches would be. Is there a name for this kind of idiom and is there a best practice for how to solve it?</p>