c++ - 使用模板构建哨兵节点 - C++

Question

我目前正在尝试使用模板在 C++ 中实现 RB 树。我有 2 个类 - 一个是 rB.h(其中有所有需要的函数，例如插入和删除以提供树的功能)，另一个是 node.h(由节点的基本属性和相应的 getter/setter 函数以提供封装)。我想声明一个名为“sentinel”的节点。 sentinel节点的作用是让每个有NULL指针的节点(即左/右 child 不存在)指向sentinel。此外，哨兵的颜色应该是黑色。我不确定应该如何声明它，因为我使用的是模板并且对 C++ 和模板都是全新的。下面是我的 node.h 的一些代码(主要是私有(private)变量和构造函数)。我没有包括整个类，所以我不会有很多代码行。谁能提供任何指导方针？

template<class T, class key>

class Node {
private:
    Node<T,key>*left;
    Node<T,key>*right;
    Node<T,key>*parent;
    key k;
    T value;
    string colour;

public:

    Node<T,key>* root;


    Node(T value,key k,Node<T,key>*l, Node<T,key>*r, Node<T,key>*p, string c){
        setLeft(l);
        setRight(r);
        setParent(p);
        setKey(k);
        setValue(value);
        setColour(c);
    }

   //all getters and setters


};

Answer 1

对于哨兵节点，您可能会使用类模板的 static 成员函数，它提供对指向 static 变量的指针的访问:

template <typename T, typename Key>
Node<T, Key> const* Node<T, Key>::sentinel() {
    static Node<T,Key> rc(...);
    return &rc;
}