c++ - How to improve the self-referencing template implementation? -

how rid of abstract classes in given implementation of self-referencing templates?

i tried implement skip-list data structure. wanted create template node such may instantiate class of next link different node classes avoid class casts. have found these questions:

self-referencing template in template argument

how declare self-referencing template type?

but none of them have solution. i've made own solution based on 2 lines of inheritance. 1 sequence of "abstract" templates (for next argument propogation). instantiate concrete classes. feel can improved handle same without redundant abstract templates (nodeabstract, nodewithkeyabstract etc). after several own tries want ask me:

template <class value, class next > class nodeabstract { public:     value m_value;      next * next;      nodeabstract () : next(0) {}     next * getnext() {return next;} };  template <class value, class key, class next > class nodewithkeyabstract : public nodeabstract <value, next > { public:     key m_key; };  template <class value, class key> class nodewithkey : public nodewithkeyabstract <value, key, nodewithkey<value,key> > { };  template <class value, class key, int maxlevel, class next> class nodeskiplistabstract : public nodewithkeyabstract<value, key, next > { public:     next * nextjump[maxlevel-1]; };  template <class value, class key, int maxlevel> class nodeskiplist : public nodeskiplistabstract<value, key, maxlevel, nodeskiplist<value, key, maxlevel> > { }; 

if understand correctly, problem different maxlevel values in produce different classes, , couldn't use 1 array store them (correct me if i'm wrong).

you cannot rid of abstract classes - if want have nodes different max level different classes (different template specializations) have provide common denominator them.

good news can rid of curiously recurring template pattern instead - since use pointers don't have refer exact implementation type (e.g. knowing exact template specialization) if you're abstraction gives access information need. code can simplified bit.

consider code:

template <class key, class value> class node {  public:   virtual ~node() = default;    virtual std::size_t maxlevel() const = 0;   virtual node* skip(size_t level) const = 0;   // add setter    key key;   value value; };  template <class key, class value, std::size_t max_level> class nodeimpl : public node<key, value> {  public:   typedef node<key, value> node_type;    nodeimpl() : skips() {}    size_t maxlevel() const { return max_level; }   node_type* skip(std::size_t level) const {     return level < max_level ? skips[level] : nullptr;   }   // add setter   private:   node_type* skips[max_level]; };  template <class key, class value> class skiplist {   public:    typedef node<key, value> node_type;     node_type* head; }; 

here node provides abstraction "skipping" behavior. nodeimpl used generate nodes different max level, in end used implementation transparent - use node's interface. on syntax level use node* type, variety of implementations wouldn't problem. virtual destructor ensure delete frees memory, , key , value accessible public fields.

this code can of course improved. raw array can replaced std::array. whole idea of max_level template can rid of if decide use std::vector size set in constructor instead of array (then you'll have node , skiplist). bonus creating new nodes easier, since you'd have write factory specializations of nodeimpl's 1 value. additionally pointers replaced smart pointer avoid memory leaks.