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