如何为单列表节点和双列表节点构建模板层次结构

Question

我只想实现两种类型的节点(仅节点):
用于单链表的节点和用于双链表的节点类。
显而易见的解决方案是定义两个单独的类:

template <typename T>
struct SinglyNode
{
    using node_pointer = SinglyNode<T>*;
    SinglyNode(T data = T{}, node_pointer next = nullptr)
        : m_data{ data },
        m_next{ next }
    {}
    T m_data;
    node_pointer m_next;
};
template <typename T>
struct DoublyNode
{
    using node_pointer = DoublyNode<T>*;
    DoublyNode(T data = T{}, node_pointer prev = nullptr, node_pointer next = nullptr)
        : m_data{ data },
        m_prev { prev },
        m_next{ next }
    {}
    T m_data;
    node_pointer m_prev;
    node_pointer m_next;
};

我知道DoublyNode和SinglyNode都有数据，并链接到下一个节点(节点不属于同一类型，SinglyNode::m_next是类型SinglyNode*和DoublyNode::m_next是类型DoublyNode*)，此外，DoublyNode还具有到前一个节点的链接。

但是，我如何创建一个层次结构来擦除/最小化代码重复，以便用户可以使用派生类成员而不需要dynamic_cast到派生节点?

注意:一个代码片段或一些提示对我来说就足够了。

Answer 1

对于CRTP，您可以这样做:

template <typename Derived, typename T>
struct SinglyNodeCRTP
{
    using node_pointer = Derived*;
    SinglyNodeCRTP(T data = T{}, node_pointer next = nullptr)
        : m_data{ data },
        m_next{ next }
    {}
    T m_data;
    node_pointer m_next;
};

template <typename T>
struct SinglyNode : SinglyNodeCRTP<SinglyNode<T>, T>
{
    using SinglyNodeCRTP::SinglyNodeCRTP;
};
template <typename T>
struct DoublyNode : SinglyNodeCRTP<DoublyNode<T>, T>
{
    using node_pointer = typename SinglyNodeCRTP<DoublyNode<T>, T>::node_pointer;
    DoublyNode(T data = T{}, node_pointer prev = nullptr, node_pointer next = nullptr)
        : SinglyNodeCRTP<DoublyNode<T>, T>{ data , prev },
        m_prev{ prev }
    {}
    node_pointer m_prev;
};

Answer 2

得到问题的答案后的最终代码。

      template <typename N, typename T>
      struct node_base {
        T m_value;
        N* m_next;
        node_base(T value = T{}, N* next = T{})
            : m_value{ value },
            m_next{ next }
        {}
      };
      template <typename T>
      struct snode : public node_base<snode<T>, T>
      {
          using node_base::node_base;
      };
      template <typename T>
      struct dnode : public node_base<dnode<T>, T>
      {
        using node_type = dnode<T>;
        dnode(T value = T{}, node_type* prev = nullptr, node_type* next = nullptr)
            : node_base<node_type, T>{ value, next },
            m_prev{prev}
        {}
        dnode<T>* m_prev;
      };