dimanche 10 juillet 2022

C++ make tree node class as derivable with CRTP

I wrote a node class for red-black trees as follows:


template <Containable T> struct RBTreeNode {
  T key_ = T{};
  RBTreeNode *parent_ = nullptr;
  bool black_ = false; // the new node starts out red
  std::unique_ptr<RBTreeNode> left_;
  std::unique_ptr<RBTreeNode> right_;
  RBTreeNode() = default;
  RBTreeNode(T key) : key_{std::move(key)} {}
  RBTreeNode(const RBTreeNode &node) = delete;
  RBTreeNode &operator=(const RBTreeNode &node) = delete;
  RBTreeNode(RBTreeNode &&node) = delete;
  RBTreeNode &operator=(RBTreeNode &&node) = delete;
};

This design works okay as-is, but as soon as I try to extend it to derived classes, this design becomes a big problem.

I want to extend RBTreeNode by adding some member variables from derived classes like this:

template <Containable T> struct RBOrderNode : public RBTreeNode<T> {
  using Base = RBTreeNode<T>;
  std::ptrdiff_t size_ = 1;
  RBOrderNode() = default;
  RBOrderNode(T key) : Base(std::move(key)) {}
};

but since left_ and right_ is std::unique_ptr<RBTreeNode>, traversing tree with referring size_ member variables becomes impossible without using virtual or dynamic dispatch. This is of course, unacceptable.

I've used CRTP pattern several times before, but it seems tricky to apply in this case. How can I apply it in this situation?

EDIT: live demo: link

Aucun commentaire:

Enregistrer un commentaire