红黑树模板

Question

我在实现一个使用模板的红色黑树时遇到了困难。我已经阅读并理解了它的用途，但不知道如何将其具体实现到头文件和.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> *)
{
}

我也知道我不包括参数。我主要是问如何处理这个问题，这样我就可以开始编写代码了。

Answer 1

1. 有在.cpp文件中实现类模板的方法，但最常见的方法是在.hpp (或.h)文件中实现它们。见Why can templates only be implemented in the header file?。
2. 更重要的是，您不能使用： redBlackTree::redBlackTree() {} 实现类模板成员函数。该语法只能用于类。你需要使用： 模板redBlackTree::redBlackTree() {} 并对所有其他功能进行更改。

Answer 2

以任何方式使用myType的所有函数都需要在.hpp文件中。这是因为所有的翻译单元都需要能够访问函数的全部定义，才能实例化模板。

如果希望将它们保存在单独的文件中，则可以创建另一个.hpp文件，将定义放入其中，然后在第一个.hpp文件中创建该文件。

有些人喜欢对这个实现文件使用不同的文件结尾，例如.tcc。