增强数据结构而不浪费内存

我有课Tree我想将其扩充为更专业的数据结构，例如Order_tree and Interval_tree。这些增强功能需要添加Node，例如大小信息，以及对某些算法的微小更改。

我想知道在 C++ 中实现性能、可读性和可维护性方面的增强的最佳方法。树不应该以多态方式使用。到目前为止我所尝试的是公开继承Tree，然后重载基本方法。 （我为自己是面向对象编程的初学者而道歉）

template <typename T>
class Tree {
protected:
    enum class Color : char {BLACK = 0, RED = 1};

    struct Node {
        T key;
        Node *parent, *left, *right;
        Color color;
        Node() : color{Color::BLACK} {} // sentinel construction
        Node(T val, Color col = Color::RED) : key{val}, parent{nil}, left{nil}, right{nil}, color{col} {}
    };
    using NP = typename Tree::Node*;

    NP root {nil};
    // nil sentinel
    static NP nil;

    // core utility algorithms...

};

template <typename T>
typename Tree<T>::NP Tree<T>::nil {new Node{}};

订单树

template <typename T>
class Order_tree : public Tree<T> {
    using Color = typename Tree<T>::Color;
    using Tree<T>::Tree;    // inherit constructors
    struct Order_node {
        T key;
        Order_node *parent, *left, *right;
        size_t size;    // # of descendent nodes including itself = left->size + right->size + 1
        Color color;
        Order_node() : size{0}, color{Color::BLACK} {}  // sentinel construction
        Order_node(T val, Color col = Color::RED) : key{val}, parent{nil}, left{nil}, right{nil}, size{1}, color{col} {}
    };
    using NP = typename Order_tree::Order_node*;
    NP root {nil};
    static NP nil;

    // overloading on only the methods that need changing
};

template <typename T>
typename Order_tree<T>::NP Order_tree<T>::nil {new Order_node{}};

然而，这行为不正确，因为现在我有 2 个根和 2 个零，所有基本方法都在基本根上工作，并且Tree<T>::NP而不是Order_tree::NP so the Order_node无法使用 的 size 属性。

一种方法是复制粘贴代码，这是非常难以维护的。我认为的另一种方法是在 T 和 NP 上对 Tree 进行模板化，这样Order_tree是一个别名using Order_tree = Tree<Order_node>并在节点上专门化树。

如果您真的对“所有树的通用树”感兴趣，那么问题似乎不在树中，而是在 Node 中。您需要节点的一些特殊情况，那么为什么不将它们也通用化呢？例如：

 template <typename T>
class Tree {
protected:
    struct BaseNode {
    //all code you really can generalize here 
    };

    struct Node : public BaseNode {
    //You need Node here only if you want your base Tree class to be ready to use.
    //If you want to use only its derives such as Order_tree,
    //you create special nodes kinds only there
    };

    // core utility algorithms...

BaseNode * root; //Only one root node, there is no need in duplication! 
                 //You can instantiate it as root = new OrderTreeNode or root = new SpecialTreeNode in any derives.

};

然而Node虚函数调用的代价相当大。所以你需要清楚地理解 - 你是否需要泛化而不是重复代码，或者你是否需要性能。