Продление классов и конкретизации

Question

Давайте предположим, что мы имеем реализацию RedBlack-Tree, который состоит из 2-х классов:

• Tree - содержит указатель на Node *root дерева и определяет все операции над деревом (Insert, Delete и т.д.)
• Node - хранение данных, который содержит указатели на Node *parent, Node *left, Node *right узлов и std::string key.

Tree::Insert() имеет следующую реализацию:

void Tree::Insert(const std::string &key) 
{ 
    Node *z = new Node(key); 
    // adding node logic 
} 

Теперь задача: каждый узел должен хранить время его создания.

Ограничения: реализация базового дерева должна быть изменена как можно меньше и должна содержать сведения об определенных расширениях (чтобы она не знала ничего о свойстве времени создания).

Мои мысли: распространяется NodeWithTime : Node и добавлено unsigned int creation_time Недвижимость.

Где я застрял: как мы будем создавать экземпляр узла сейчас?

Любые предложения?

PS: это не домашнее задание или задание - я просто изучаю C++ и структуры данных.

Answer 1

Это относительно просто. Во-первых, узел структура:

template<typename T> struct Node { 
    Node(T t) : value(std::move(t)), time(RightNow()) {} 
    T value; 
    TimeType time; 
    std::unique_ptr<Node> left; 
    std::unique_ptr<Node> right; 
}; 

Быстрый помощник make_unique:

template<typename T, typename... Args> std::unique_ptr<T> make_unique(Args&&... args) { 
    return std::unique_ptr<T>(new T(std::forward<Args>(args...))); 
} 
template<typename T> void Tree<T>::Insert(T key) { 
    auto z = make_unique<Node<T>>(std::move(key)); 
    // insert 
} 

Во-первых, я установил ваш дерьмовый new и delete и заменить его смарт-указатели. Затем я также сделал ваше дерево шаблоном, потому что кому нужно дерево, которое может делать только один тип? Затем я поместил ваш const T& с T, чтобы он мог жить с типами только для перемещения.

Затем я просто добавил поле Time и вызвал RightNow() в конструкторе. Точный TimeType и RightNow(), которые вы используете, зависят от ваших потребностей и того, что именно вы подразумеваете под «временем его создания». Мы говорим о «6 июля 2013 года»? Или часы с очень высоким разрешением? В любом случае эти данные «время создания» не влияют на дерево.

Редактировать: Подождите, вы хотите иметь один тип дерева, где только некоторые узлы знают время создания? Или просто изменить дерево так, чтобы все узлы знали время творения? Я сделал # 2, но для # 1 вы действительно могли просто наследовать от Node. К сожалению,

template<typename T> struct Node { 
    Node(T t) : value(std::move(t)) {} 
    T value; 
    std::unique_ptr<Node> left; 
    std::unique_ptr<Node> right; 
}; 
template<typename T> struct NodeWithTime : Node<T> { 
    TimeType time; 
    NodeWithTime(T t) : Node(std::move(t)), time(RightNow()) {} 
}; 
template<typename T> void Tree<T>::insert(T t) { 
    std::unique_ptr<Node> nodeptr; 
    if (IWantToStoreCreationTime) 
     nodeptr = make_unique<NodeWithTime<T>>(std::move(t)); 
    else 
     nodeptr = make_unique<Node>(std::move(t)); 
    // insert 
}