CODEWITHSUNDEEP
c++templatesinheritance
NarekMeta
NarekMeta

Reputation: 103

How to construct template hierarchy for singly and doubly list nodes c++

I just want to implement two types of nodes(only nodes):
A node for singly linked list and a node class for doubly linked list.
The obvious solution would be to define two separate classes:

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;
};

I know that DoublyNode and SinglyNode both have data, and link to the next node(nodes aren`t of the same type, SinglyNode::m_next is of type SinglyNode* and DoublyNode::m_next is of type DoublyNode*), in addition DoublyNode also has link to previous node.

But how can I make a hierarchy to erase/minimize code duplicate so that user could use the derived class member without the need to dynamic_cast to derived node?

Note: A code snippet or a few hints will be sufficient for me.

Upvotes: 1

Views: 119

Answers (2)

NarekMeta
NarekMeta

Reputation: 103

Final code after getting the answers to my questions.

      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;
      };

Upvotes: 0

Jarod42
Jarod42

Reputation: 217135

With CRTP, you might do something like:

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;
};

Upvotes: 2

Related Questions