c++ - 将运算符重载作为模板参数传递

Question

我正在编写一个增强二叉搜索树类。我用整数完成了简单版本，现在我想用模板实现相同的结构。我遇到的问题如下。

我需要一棵树，里面装满了我无法更改的库中的对象。这些对象没有我当前用于树实现的更大运算符。我该怎么做？
Tree.h 文件有一个结构体节点，其中包含节点或叶子的所有信息以及实际的树代码

结构节点

template <typename keytype>
class 
template <typename keytype >
struct Node {
    //key value
    keytype key;
    //node type , leaf ot internal Node
    bool leaf;
    //childern pointers
    struct Node<keytype>* left;
    struct Node<keytype>* right;
    //height of tree 
    int height;
    //ansestor
    struct Node<keytype>* ansestor;
};



template <typename item>
class Tree{
public:
Tree();                                     //tree constructor

void insert(item key);                      //inserts a new element 

bool remove(item key);                      //remove an existing element

void printInOrder();                        //print tree in order

int getHeight();                            //returns the height of the tree

Node<item> getFirst();                          //returns the first element of tree-list 

Node<item> getLast();                               //returns the last element of tree-list

Node<item> getNext();                               //returns the next value of the last accessed element

Node<item> getPrevious();                           //returns the privious value of the last accessed element

private:

int height,
    numOfElements;

Node<item>* root;

Node<item>* listPosition;                           //internal pointer, points to an element in the list

/***************************private functions**********************/

void _insert(Node<item> *&newNode, item &key);      //private insertion function

bool _remove(Node<item> *&currentNode,item &key);   //remove the leaf with key is it exists

void _balanceTree(Node<item> *&currentNode);        //balance the tree if needed

void _rotateLeft(Node<item> *&root);                //performs a left rotation

void _rotateRight(Node<item> *&root);               //performs a right rotation

Node<item>* _createNewNode(const item &key,     //alocates memeory space for new leaf/node
    const bool &leaf=true,                      //and passes it defaults or given values
    Node<item>* left=NULL, Node<item>* right=NULL,
    const int &height=0, Node<item>* ansestor=NULL);

void _updateHeight(Node<item> *&currentNode);       //updates the height of a node 

void _inOrderTraversal(Node<item>* currentNode);    //print in order function

void _printNodesInfo(Node<item>* currentNode);  //print node function

bool _removeLeft(Node<item> *&parent);          //removes the left child of a internal node

bool _removeRight(Node<item> *&parent);         //removes the right chold of a internal node

Node<item> _getFirst(Node<item> *root);                 //returns the value of the first item and 
                                            //sets the internal pointer to that element 

Node<item> _getLast(Node<item> *root);                  //returns the value of the last item and 
                                            //sets the internal pointer to that element 

Node<item>* _next(Node<item> *leaf);                    //returns a pointer to leaf's next element and
                                            //sets the internal pointer to that element 

Node<item>* _previous(Node<item> *leaf);                //returns a poiunter to leaf's previous element and
                                            //sets the internal pointer to that element 

};

当我想要进行插入等操作来查找节点的位置时，我使用以下代码来比较键

if (key>currentNode->key)
    {
        if (DEBUG){
            cout<<">>>>>>>>>>>>>>go right>>>>>>>>>"<<endl;
        }
        this->_insert(currentNode->right,key);
    }
    else
    {
        if (DEBUG){
            cout<<"<<<<<<<<<<<<<go left<<<<<<<<<<<"<<endl;
        }
        this->_insert(currentNode->left,key);
    }

这是函数_insert的一部分

template <typename item>
void Tree<item>::_insert(Node<item> *&currentNode, item &key){

if (this->root==NULL)
{/*the tree is empty at this point*/
    if (DEBUG){
        cout<<"tree was empty"<<endl;
    }
    /*inititialize the root*/

    root= this->_createNewNode(key,true);
    this->numOfElements=1;
    return;


}
else if (currentNode->height==0)//currentNode->leaf==true
{//we reached a leaf 
    if (DEBUG){
        cout<<"-------insertion found-----"<<endl;
    }
    Node<item>* oldLeaf= currentNode;                       //keep the pointer to the old leaf
    Node<item>* privious;

    currentNode= this->_createNewNode(654, false);  //create a new internal node and link it to the tree
    currentNode->height=1;                          //set its height to 1 

    Node<item>* newLeaf = _createNewNode(key, true); 

    if (newLeaf->key>oldLeaf->key)
    {/*the new leaf is the biggest element in the tree*/
        currentNode->right= newLeaf;
        currentNode->left= oldLeaf;

        //list connection
    }
    else
    {/*normal insertion*/
        currentNode->right= oldLeaf;
        currentNode->left= newLeaf;


        //list connection
        privious=this->_previous(oldLeaf);
        if (privious!=NULL){//old element was not the first one 
            privious->right=newLeaf;
            newLeaf->left=privious;
        }

    }
    currentNode->left->right=currentNode->right;
    currentNode->right->left=currentNode->left;

    currentNode->key= currentNode->left->key;
    currentNode->left->ansestor= currentNode;
    this->numOfElements++;
    return;
}
else
{/*search deeper to the tree*/
    if (key>currentNode->key)
    {
        if (DEBUG){
            cout<<">>>>>>>>>>>>>>go right>>>>>>>>>"<<endl;
        }
        this->_insert(currentNode->right,key);
    }
    else
    {
        if (DEBUG){
            cout<<"<<<<<<<<<<<<<go left<<<<<<<<<<<"<<endl;
        }
        this->_insert(currentNode->left,key);
    }
    //this balance tree
    this->_updateHeight(currentNode);
    this->_balanceTree(currentNode);        //balance the tree if needed
    this->_updateHeight(currentNode);

    //cout <<"-----------------test height is "<<currentNode->height<<endl;

    return;
}
}

现在，正如我之前提到的，如果键是具有更大运算符(如 int)的东西，则此方法有效。我如何编写代码来处理没有此运算符的对象？
例如如果我需要用代表点的类填充树，并且该类不支持更大的运算符。假设我想基于 x 轴存储它们，因此如果 x1>x2，点 p1(x1,y1) 大于点 p2(x2,y2)。我可以为类似的东西编写函数，但我不知道如何在树中传递这个函数以及如何保留 int 等对象的默认比较。
提前致谢

Answer 1

你可以看看STL对关联容器做了什么，这个问题已经解决了。

拿std::set例如(本质上是二叉搜索树)，有 < 的比较函数嵌入树的类型中，如 comparator 。你可以拥有:

// The comparison object
struct Comp
{
    bool operator()(int i1, int i2)
    {
        return i1 < i2;
    }
};
// using the comparison object as the comparator
std::set<int, Comp> lala;

类似地，你可以让你的树布局看起来像这样

template <typename keytype, typename Comp>
struct Node
{
    ....
    friend bool operator<(Node const& left, Node const &right)
    { // Now your nodes know how to compare themselves
        return Comp(left, right);
    }
    ....
};

template <typename item, typename Comp>
class Tree
{
    ....
    Node<item, Comp> *root; 
    ....
};

现在，在为 Tree 编写代码时您可以编写的成员函数

n1 < n2 ; // node1 < node2

并知道它们正在根据您指定为模板参数的比较器进行比较

---

作为奖励功能，您可以查看 here一旦您定义了<，就可以为您生成所有关系运算符。运算符(实际上，比较器的定义是由此设计强制执行的，因此从 Node 继承的 relational 将自动为您提供 > 、 >= 、 <= 、 == 、 !=生成)

template <typename keytype, typename Comp>
struct Node : relational<Node<keytype,Comp>>
{ ... }