Реализация дерева с использованием шаблонов C++

Question

Я пытаюсь узнать, как работают шаблоны в C++, поэтому я хотел бы реализовать дерево с использованием шаблонов C++. Вот традиционный полиморфный вариант:

#include <iostream> 
using namespace std; 

class Node { 
public: 
    virtual ~Node() {} 
    virtual void print() = 0; 
}; 

class InnerNode : public Node { 
public: 
    InnerNode(Node *lhs, Node *rhs) { 
     m_lhs = lhs; 
     m_rhs = rhs; 
    } 

    virtual ~InnerNode() { 
     delete m_lhs; 
     delete m_rhs; 
    } 

    virtual void print() { 
     cout << "inner" << endl; 
     if (m_lhs != NULL) 
      m_lhs->print(); 
     if (m_rhs != NULL) 
      m_rhs->print(); 
    } 
private: 
    Node *m_lhs; 
    Node *m_rhs; 
}; 

class LeafNode : public Node { 
    virtual void print() { 
     cout << "leaf" << endl; 
    } 
}; 

int main() { 
    Node *l1 = new LeafNode(); 
    Node *l2 = new LeafNode(); 
    Node *r = new InnerNode(l1, l2); 
    r->print(); 
} 

Я пытаюсь реализовать версию этого кода, используя только шаблоны, но у меня возникают некоторые проблемы с чем-то вроде этого:

#include <iostream> 
using namespace std; 

template <typename T> 
class Node { 
public: 
    virtual ~Node() {} 
    void print() { 
     static_cast<T *>(this)->print(); 
    } 
}; 

class InnerNode : public Node<InnerNode> { 
public: 
    InnerNode(Node *lhs, Node *rhs) { 
     m_lhs = lhs; 
     m_rhs = rhs; 
    } 

    virtual ~InnerNode() { 
     delete m_lhs; 
     delete m_rhs; 
    } 

    void print() { 
     cout << "inner" << endl; 
     if (m_lhs != NULL) 
      m_lhs->print(); 
     if (m_rhs != NULL) 
      m_rhs->print(); 
    } 
private: 
    Node *m_lhs; 
    Node *m_rhs; 
}; 

class LeafNode : public Node<LeafNode> { 
    virtual void print() { 
     cout << "leaf" << endl; 
    } 
}; 

int main() { 
    Node *l1 = new LeafNode(); 
    Node *l2 = new LeafNode(); 
    Node *r = new InnerNode(l1, l2); 
    r->print(); 
} 

Как я могу адаптировать вместо полиморфной версии использовать шаблоны?

Answer 1

Шаблоны позволяют заменять тип именем и генерировать конкретные экземпляры кода с использованием этого типа. Например, возможно иметь узлы с вариантными типами.

Ваш шаблон Node <> никогда не ссылается на параметр типа шаблона, поэтому нет причин сделать его шаблоном. По сути, ваш класс «Узла» - это просто абстрактный интерфейс, а не шаблон. InnerNode также не обязательно должен быть шаблоном, потому что нет разных типов, поскольку вы можете просто сохранить указатель базового класса на листья.

Листья имеют данные и поэтому являются кандидатами на темплатизацию, но поскольку ваш пример не помещает данные в листовые узлы, применение типа шаблона не является очевидным.

Надеюсь, это будет иллюстрировать:

#include <iostream> 
using namespace std; 

// interface for interacting with general nodes 
class INode { 
public: 
    virtual ~INode() {} 
    virtual void print() = 0; 
}; 

class InnerNode : public INode { 

public: 
    InnerNode(INode *lhs, INode *rhs) { 
     m_lhs = lhs; 
     m_rhs = rhs; 
    } 

    virtual ~InnerNode() { 
     delete m_lhs; 
     delete m_rhs; 
    } 

    void print() { 
     cout << "inner" << endl; 
     if (m_lhs != NULL) 
      m_lhs->print(); 
     if (m_rhs != NULL) 
      m_rhs->print(); 
    } 
private: 
    INode *m_lhs; 
    INode *m_rhs; 
}; 

template< typename DataType > 
class LeafNode : public INode { 
    virtual ~LeafNode() {}; 
    public: 
    LeafNode(DataType data) : m_data(data) {} 

    virtual void print() { 
     cout << "leaf:" << endl; 
     cout << m_data << endl; 
    } 
    private: 
    DataType m_data; 
}; 

int main() { 
    INode *l1 = new LeafNode<int>(2); 
    INode *l2 = new LeafNode<float>(3.14); 
    INode *r = new InnerNode(l1, l2); 
    r->print(); 
    delete r; 
} 

http://cpp.sh/3rmq

Answer 2

Ваш вопрос заранее предполагает, что дерево представляет собой структуру данных, которая содержит данные. Эти данные являются типом, который будет обрабатывать шаблон. Если у вас нет данных, тогда у вас нет типа данных для обобщения (шаблон).

Поскольку вы спрашивали о шаблонах, позвольте мне предположить, что у вас есть дерево, которое отслеживает «некоторый тип данных», который мы будем называть myDataType. Предположим, что это строка. Вот абсолютно минимальный интерфейс дерева и ни одна из деталей реализации. Я знаю, что это довольно бесполезное дерево, но вопрос был о шаблонах.

typedef myData std::string; 

class tree { 
private: 
    struct node { 
     myData data; 
     node * left, right; 
    }; 
    node * head; 
public: 
    void add (myData value); 
    bool is_value_in_the_tree (const myData &value); 
}; 

Если вы используете разные типы узлов для внутренних и листовых узлов, это не проблема. Это часть написания дерева. Детализация реализации. Мне все равно. Пока дерево работает для ОДНОГО типа данных, переход к шаблону должен заставить его работать для ЛЮБОГО типа данных. (1)

Вся тяжелая работа вошла в создание дерева. Переход к шаблону, чтобы он мог использовать любой тип данных, а не просто «myData». Просто скажите шаблон < typename myData >, чтобы вы могли использовать его с разными типами, вместо того чтобы требовать typedef, который может быть только одного типа. Или использовать «T», как и все остальные:

template<typename T> 
class tree { 
private: 
    template<typename T> 
    struct node { 
     T data; 
     node<T> * left, right; 
    }; 
    node<T> * head; 
public: 
    void add(T value); 
    bool is_value_in_the_tree(const T &value); 
}; 

Обратите внимание, что поскольку дерево и узел теперь шаблоны, вы должны указать, какой тип, когда вы используете их, хотя это могут быть разные типы для разных деревьев. дерево будет деревом строк.

tree<std::string> t; 
assert(!t.is_value_in_the_tree("hello"); 
t.add("hello") 
assert(t.is_value_in_the_tree("hello"); 

Также обратите внимание, что узлы являются частными, и использовать тот же T. Вы не должны сделать их частными, но я бы. Но заставить их использовать один и тот же тип является критическим, потому что, если кто-то объявит дерево, узлы будут обрабатывать sometype.

примечание 1: Хорошо, очевидно, что дерево не будет работать ни с одним типом, но вы получите ошибку компоновщика, если в типе отсутствует то, что требуется дереву, например, оператор <() или некоторые конструкторы узлов, в зависимости от того, как дерево реализовано.