Расширение классов и создание экземпляров

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 ++ и структуры данных.

-1

algorithm application-design c++red-black-tree tree

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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
}

1