Шаблон красно-черного дерева

У меня возникли проблемы с реализацией красно-черного дерева, использующего шаблон. Я прочитал и понял цель, но точно не знаю, как реализовать ее в файле заголовка и файле .cpp. Я читал на некоторых форумах, что они должны быть в том же файле, что и шаблон, а другие говорят, что они могут быть отдельными, но в файле .hpp.

заголовочный файл

enum nodeColor { RED, BLACK };

template <class myType>
struct nodeType
{

    myType  keyValue;
    nodeColor color;
    nodeType<myType> *left;
    nodeType<myType> *right;
    nodeType<myType> *parent;

};

template<class myType> 
class redBlackTree
{

public:
    redBlackTree() {}
    ~redBlackTree() {}
    void destroyTree();
    unsigned int countNodes() const;
    unsigned int height() const;
    void printTree() const;
    void insert(myType);
    bool search(myType);

private:
    bool search(myType, nodeType<myType> *);
    void destroyTree(nodeType<myType> *);
    unsigned int countNodes(nodeType<myType> *) const;
    unsigned int height(nodeType<myType> *) const;
    void printTree(nodeType<myType> *) const;
    void rightRotate(nodeType<myType> *);
    void leftRotate(nodeType<myType> *);

};

.cpp-файл

#include "redBlackTree.h"
using namespace std;

redBlackTree::redBlackTree()
{
}   
redBlackTree::~redBlackTree()
{
}
void redBlackTree::destroyTree()
{
}
unsigned int redBlackTree::countNodes() const
{
}
unsigned int redBlackTree::height() const
{
}
void redBlackTree::printTree() const
{
}
void redBlackTree::insert(myType)
{
}
bool redBlackTree<myType>::search(myType)
{
}

bool redBlackTree::search(myType, nodeType<myType> *)
{
}
void redBlackTree::destroyTree(nodeType<myType> *)
{
}
unsigned int redBlackTree::countNodes(nodeType<myType> *) const
{
}
unsigned int redBlackTree::height(nodeType<myType> *) const
{
}
void redBlackTree::printTree(nodeType<myType> *) const
{
}
void redBlackTree::rightRotate(nodeType<myType> *)
{
}
void redBlackTree::leftRotate(nodeType<myType> *)
{
}

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


c++ templates data-structures red-black-tree binary-search-tree
person gamer1996    schedule 21.02.2018    source источник
comment
Реализация может быть в отдельном файле, включаемом в заголовочный файл. В таких случаях часто используются расширения файлов .inc или .inl. Дополнительные сведения см. на странице stackoverflow.com/q/1208028/580083.   -  person Daniel Langr    schedule 22.02.2018

Ответы (2)


arrow_upward
3
arrow_downward

  1. Существуют способы реализации шаблонов классов в файле .cpp, но наиболее распространенным методом является их реализация в файле .hpp (или .h). См. Почему шаблоны могут быть реализованы только в заголовочном файле? .

  2. Что еще более важно, вы не можете использовать:

    redBlackTree::redBlackTree()
{
}

    для реализации функций-членов шаблона класса. Такой синтаксис можно использовать только в классах. Вам нужно использовать:

    template <typename myType>
redBlackTree<myType>::redBlackTree()
{
}

    и внесите изменения для всех остальных функций.

person R Sahu    schedule 21.02.2018
comment
Спасибо. Это заставило меня начать. Я читал другой форум, но хотел больше разъяснений, и это принесло его. - person gamer1996; 26.02.2018
comment
@gamer1996, пожалуйста. Рад, что смог помочь. - person R Sahu; 26.02.2018

arrow_upward
0
arrow_downward

Все функции, которые каким-либо образом используют myType, должны быть в файле .hpp. Это связано с тем, что все единицы перевода должны иметь доступ к полному определению функции для создания экземпляра шаблона.

Если вы хотите сохранить их в отдельных файлах, вы можете создать еще один файл .hpp, в который вы поместите определения, а затем #include в свой первый файл .hpp.

Некоторым людям нравится использовать другое окончание файла для этого файла реализации, например, .tcc.

person super    schedule 21.02.2018