Red Black tree template

Question

I am having trouble implementing a red black tree which uses a template. I have read and understand the purpose but do not know exactly how to implement it into the header file and .cpp file. I was reading in some forums that they must in the same file as the template and others say that they can be separate but in a .hpp file.

header file

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 file

#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> *)
{
}

I also know that I did not include parameters. I am mostly asking for how to approach this so that I can get to coding away.

Implementation can be in a separate file that is included into the header file. `.inc` or `.inl` file extensions are frequently used in such cases. See https://stackoverflow.com/q/1208028/580083 for more details. — Daniel Langr, Feb 21 '18 at 22:19

score 3 · Accepted Answer · answered Feb 21 '18 at 22:22

3

There are ways of implementing class templates in a .cpp file but the most common method is to implement them in a .hpp (or .h) file. See Why can templates only be implemented in the header file?.
More importantly, you may not use:
```
redBlackTree::redBlackTree()
{
} 
```
to implement class template member functions. That syntax can be used only classes. You need to use:
```
template <typename myType>
redBlackTree<myType>::redBlackTree()
{
} 
```
and make the change for all other functions.

answered Feb 21 '18 at 22:22

R Sahu

204,454
14
159
270

Thank you. This got me started. I had read the other forum but wanted more clarification and this brought it. – gamer1996 Feb 26 '18 at 03:19
@gamer1996, you're welcome. Glad I was able to help. – R Sahu Feb 26 '18 at 03:21

score 0 · Answer 2 · answered Feb 21 '18 at 22:22

All the functions that use myType in any way needs to be in the .hpp file. This is because all the translation units needs to be able to access the full definition of the function in order to instantiate the template.

If you want to keep them in separate files you can make another .hpp file that you put the definitions in, then #include that in your first .hpp file.

Some people like to use a different file-ending for this implementation file, .tcc for example.

Red Black tree template

2 Answers2