CODEWITHSUNDEEP
c++templates
outmind
outmind

Reputation: 829

How to improve the self-referencing template implementation?

How to get rid of abstract classes in the given implementation of self-referencing templates?

I just tried to implement a skip-list data structure. So I wanted to create the template Node such that I may instantiate the class of the next link for different node classes to avoid class casts. Have found these questions:

Self-referencing Template in Template Argument

How to properly declare a self-referencing template type?

but none of them have a solution. Then I've made my own solution based on two lines of inheritance. One is the sequence of "abstract" templates (for Next argument propogation). Another is to instantiate concrete classes. But feel like it can be improved to handle the same without redundant abstract templates (NodeAbstract, NodeWithKeyAbstract etc). After several own tries I want to ask you help 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> >
{
};

Upvotes: 3

Views: 251

Answers (1)

Mateusz Kubuszok
Mateusz Kubuszok

Reputation: 27595

If I understand you correctly, your problem is basically that different maxlevel values in would produce different classes, and so you couldn't use one array to store them all (correct me if I'm wrong).

You cannot fully get rid of abstract classes - if you want to have nodes with different max level as different classes (different template specializations) you have to provide some common denominator for them.

Good news is that you can get rid of Curiously Recurring Template Pattern instead - since you use pointers you don't have to refer to exact implementation type (e.g. knowing exact template specialization) if you're abstraction gives you access to all information you need. Also your code can be simplified a bit.

Consider this 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 as well

  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 as well

 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 you with an abstraction for a "skipping" behavior. NodeImpl would be used to generate Nodes with different max level, but in the end used implementation would be transparent to you - you would only use Node's interface. Also on syntax level you would only use Node* type, so variety of implementations wouldn't be a problem. Virtual destructor would ensure that delete frees all memory, and key and value would always be accessible as public fields.

This code can of course be improved. Raw array can be replaced by std::array. Whole idea of max_level as a template can be get rid of if you decide to use std::vector with size set in constructor instead of array (then you'll only have Node and SkipList). As a bonus creating new nodes would be easier, since now you'd have to write some factory with specializations of all NodeImpl's from 1 to some value. Additionally pointers could be replaced by some smart pointer to avoid memory leaks.

Upvotes: 1

Related Questions