增强数据结构而不浪费内存 [英] Augmenting data structure without wasting memory

问题描述

我有一个类Tree，我想将其扩展为更专业的数据结构，例如Order_tree和Interval_tree.这些扩充要求对Node进行添加，例如大小信息，并对某些算法进行较小的改动.

I have a class Tree that I'd like to augment into more specialized data structures, such as Order_tree and Interval_tree. These augmentations require additions to the Node, such as size information, and minor alterations to some algorithms.

我想从性能，可读性和可维护性方面了解在C ++中实现增强的最佳方法.这些树不应以多态的方式使用.到目前为止，我一直试图公开继承Tree，然后重载基本方法. (我很抱歉成为面向对象编程的初学者)

I'd like to know the best way to implement augmentations in C++ in terms of performance, readability, and maintainability. The trees should not be used in a polymorphic manner. What I've attempted so far is publicly inheriting Tree, and then overloading the base methods. (I apologize for being a beginner at object oriented programming)

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个nil，所有基本方法都在基本根上工作，并且使用Tree<T>::NP而不是Order_tree::NP，所以Order_node的size属性不能使用.

However, this doesn't behave properly since now I have 2 roots and 2 nils, with all the base methods working on the base root and with Tree<T>::NP rather than Order_tree::NP so the Order_node's size attribute cannot be used.

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

One way is to copy-paste the code, which is highly unmaintainable. Another way I think is to template Tree on T as well as NP, so that Order_tree is an alias using Order_tree = Tree<Order_node> and specialize tree on the node.

推荐答案

经过一些实验，我找到了实现我想要的目标的最佳方法:

After some experimentation, I found the best way to achieve what I want by:

• 节点类型上的模板树
• 将nil设置为每种Node类型的静态元素
• 移动一些不依赖于节点的私有方法 根除是在Node上模板化的正常功能
• 将可能要更改的功能虚拟化
• 增材树公开 从中继承并覆盖必要的虚函数
• 使用 基本树的根(在派生类中不保存任何数据)

• template Tree on Node type
• make nil a static element of each Node type
• move some private methods that work on nodes with no reliance on root out to be normal functions templated on Node
• make the functions that might be changed virtual
• augment Tree by publicly inheriting from it and overriding necessary virtual functions
• use the base Tree's root (hold no data in the derived class)

现在是什么样子:
tree.h

What it looks like now:
tree.h

namespace sal {

// utilities with no dependence on root, outside of class now
template <typename Node>
Node* tree_find(Node* start, typename Node::key_type key) {
    while (start != Node::nil && start->key != key) {
        if (key < start->key) start = start->left;
        else start = start->right;
    }
    return start;
}
// more of them...

template <typename Node>
class Tree {
protected:
    using NP = Node*;
    using T = typename Node::key_type;

    // nil is static member of each Node type now
    NP root {Node::nil};

    // virtual methods that could be changed by augmentation
    virtual void rotate_left(NP node);
    virtual void rotate_right(NP node);
    virtual void tree_insert(NP start, NP node);
    virtual void rb_delete(NP node);

    // non-virtual methods that are never overridden
    void rb_insert_fixup(NP node);
    void rb_delete_fixup(NP successor);
    void rb_insert(NP node);  // just a call to tree_insert and rb_insert_fixup
    void transplant(NP old, NP moved);
public:
    virtual ~Tree();  // does all the clean up so its derived classes don't have to
    // interface...
};

template <typename T>
struct Basic_node {
    static Basic_node* nil;

    using key_type = T;
    T key;
    Basic_node *parent, *left, *right;
    Color color;
    Basic_node() : color{Color::BLACK} {}   // sentinel construction
    Basic_node(T val) : key{val}, parent{nil}, left{nil}, right{nil}, color{Color::RED} {}
};

template <typename T>
using Basic_tree = Tree<Basic_node<T>>;

template <typename T>
Basic_node<T>* Basic_node<T>::nil {new Basic_node{}};

}

order_tree.h

#include "tree.h"

namespace sal {

template <typename Node>
class Order_augment : public Tree<Node> {

    using NP = Node*;
    using T = typename Node::key_type;
    using Tree<Node>::root;

    // no need to redefine shared core functions
    using Tree<Node>::rb_insert;
    using Tree<Node>::transplant;
    using Tree<Node>::rb_insert_fixup;
    using Tree<Node>::rb_delete_fixup;

    // order statistics operations
    NP os_select(NP start, size_t rank) const;
    size_t os_rank(NP node) const;

    // modification of rb operations to maintain augmentation
    virtual void tree_insert(NP start, NP node) override;
    virtual void rb_delete(NP node) override;
    virtual void rotate_left(NP node) override;
    virtual void rotate_right(NP node) override;
public:
    // augmented interface
};

template <typename T>
struct Order_node {
    static Order_node* nil;

    using key_type = T;
    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) : key{val}, parent{nil}, left{nil}, right{nil}, size{1}, color{Color::RED} {}
};

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

template <typename T>
using Order_tree = Order_augment<Order_node<T>>;

}

结果是保存扩展数据结构的文件大小现在约为1/3，并且代码重复被完全删除！这意味着任何改进核心方法的更改都只能局限在tree.h中，并且在所有增强树中都可以感受到其效果.

The result is that the file size holding the augmented data structures are now about 1/3 as large, and the code duplication is removed entirely! Which means any changes to improve the core methods can be localized to only tree.h and its effect will be felt in all augmented trees as well.

这篇关于增强数据结构而不浪费内存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！