如何比较作为模板类传递的字符串？

Question

我有一个数据结构，使用模板类，它可以存储任何数据类型 - 整数，浮点数，字符串等。

因为数据将被组织，所以我需要一种方法来比较两个值。通常我可以使用>或<，但是在字符串不可用的情况下，因为在字符串上使用>/<运算符不会告诉我哪个字母按字母顺序排列。为此，我需要使用compare（）函数。

但是由于数据结构是一个模板类，我不能告诉它使用compare（）函数，因为它不会识别compare（）函数的任何对象，但是一个字符串。

作为一种变通，我试着写两个比较功能：在值是一个字符串类型的情况下

template (class t) 
int BinaryTree<T>::compareVals(T v1, T v2); 

和

template (class t) 
int BinaryTree<T>::compareVals(string v1, string v2); 

这样，程序将使用方法与其中的compare（）函数。

但是试图做到这一点，我得到一个编译器错误，基本上告诉我，我不能重载函数。

所以我没有想法。我怎样才能使这个模板类正确地比较和排序字符串以及数字？

非常感谢您的意见！

这里是整个类，以供参考：

#ifndef binarytree_class 
#define binarytree_class 

#include <iostream> 
#include <string> 
#include <vector> 

using std::cout; 
using std::string; 
using std::vector; 

template <class T> 
class BinaryTree{ 
    public: 
     struct TreeNode{ 
      TreeNode * leftChild, 
        * rightChild; 
      T key; 
      vector<T> data; 
      int size; 
     }; 

     BinaryTree(); 
     ~BinaryTree(); 
     bool isEmpty(); 
     int getSize(); 
     void add(T key, T data); 
     void remove(T key); 
     int getHeight(); 
     bool keyExists(T key); 
     int getKeyHeight(T key); 
     void displayAll();      

    private: 
     int size; 
     TreeNode * root; 

     TreeNode * findParent(TreeNode * start, TreeNode * child); //finds the parent node of child in subtree starting at root start 
     TreeNode * findNode(TreeNode * node, T input); //find node with data input in subtree at root node 
     TreeNode * findMin(TreeNode * node);  
     void removeNode(TreeNode * node);  //Small part of algorithm (case: 2 children) borrowed from tech-faq.com/binary-tree-deleting-a-node.html 
     void displaySubTree(TreeNode * node); //displays subtree starting at node 
     void sortAdd(TreeNode * eNode, TreeNode * nNode); //adds a new node nNode to subtree starting at root eNode 
     void destroySubTree(TreeNode * node); //destroys subtree starting at node. 
     void display(TreeNode * node, string indent, bool last); //Algorithm borrowed from http://stackoverflow.com/questions/1649027/how-do-i-print-out-a-tree-structure 
     char leftOrRight(TreeNode * eNode, TreeNode * nNode); //compares keys in existing node vs new node and returns L or R 
     int calcHeight(TreeNode * node, int depth); //calculates the height from node. Algorithm borrowed from wiki.answers.com 
     int compareVals(T v1, T v2); 
     int compareVals(string v1, string v2);  
}; 

template <class T> 
BinaryTree<T>::BinaryTree<T>() : size(0){} 

template <class T> 
bool BinaryTree<T>::isEmpty(){ 
    return (!size); 
} 

template <class T> 
int BinaryTree<T>::compareVals(T v1, T v2){ 
    int result; 
    v1 <= v2? result = -1 : result = 1; 
    return result; 
} 

template <class T> 
int BinaryTree<T>::compareVals(string v1, string v2){ 
    int result; 
    result = v1.compare(v2); 
    if(result >= 0) 
     result = -1; 
    else 
     result = 1; 
    return result; 
} 

template <class T> 
int BinaryTree<T>::getSize(){ 
    return size; 
} 

template <class T> 
void BinaryTree<T>::add(T key, T data){ 
    bool done = false; 
    TreeNode * temp; 

    if(keyExists(key)){ 
     temp = findNode(root,key); 
     temp->size++; 
     temp->data.push_back(key); 
    } 
    else{ 
     temp = new TreeNode; 
     temp->leftChild = 0; 
     temp->rightChild = 0; 
     temp->key = key; 
     temp->size = 0; 
     temp->data.push_back(data);   
     if(isEmpty()) 
      root = temp; 
     else 
      sortAdd(root, temp); 
     size++; 
    } 
} 

template <class T> 
void BinaryTree<T>::sortAdd(TreeNode * eNode, TreeNode * nNode){ 
    if(leftOrRight(eNode, nNode) == 'L'){ 
     if(eNode->leftChild == 0) 
      eNode->leftChild = nNode; 
     else 
      sortAdd(eNode->leftChild,nNode); 
    } else { 
     if(eNode->rightChild == 0) 
      eNode->rightChild = nNode; 
     else 
      sortAdd(eNode->rightChild,nNode); 
    } 
} 

template <class T> 
char BinaryTree<T>::leftOrRight(TreeNode * eNode, TreeNode * nNode){ 
    char result; 
    if(compareVals(nNode->key, eNode->key) == -1) 
     result = 'L'; 
    else 
     result = 'R'; 
    return result; 
} 

template <class T> 
void BinaryTree<T>::displayAll(){ 
    display(root,"",true);  
} 

template <class T> 
void BinaryTree<T>::display(TreeNode * node, string indent, bool last){ 
    if(!isEmpty()){ 
     cout << indent; 
     if(last){ 
      cout << "\\-"; 
      indent += " "; 
     } else { 
      cout << "|-"; 
      indent += "| "; 
     } 
     cout << node->key << "\n"; 
     if(node->leftChild != 0) 
      display(node->leftChild, indent, false); 
     if(node->rightChild != 0) 
      display(node->rightChild, indent, true); 
    } else 
     cout << "TREE IS EMPTY" << "\n\n"; 
} 

template <class T> 
int BinaryTree<T>::getHeight(){ 
     if(!root) 
     cout << "ERROR: getHeight() root is NULL!" << "\n"; 
     int result; 
     if(isEmpty()) 
      result = 0; 
     else 
      result = calcHeight(root, 1); 
     return result; 
} 

template <class T> 
int BinaryTree<T>::getKeyHeight(T key){ 
    int result = -1; 
    if(!keyExists(key)) 
     cout << "ERROR: Trying to get height of nonexistant key " << key << "\n"; 
    else{ 
     TreeNode * temp = findNode(root, key);  
     result = getHeight() - calcHeight(temp,1); 
    } 
    return result; 
} 

template <class T> 
int BinaryTree<T>::calcHeight(TreeNode * node, int depth){ //Algorithm borrowed from wiki.answers.com 
    int leftDepth, 
     rightDepth, 
     result; 
    if(node->leftChild) 
     leftDepth = calcHeight(node->leftChild, depth+1); 
    else 
     leftDepth = depth; 
    if(node->rightChild) 
     rightDepth = calcHeight(node->rightChild, depth+1); 
    else 
     rightDepth = depth; 
    if(leftDepth > rightDepth)  
     result = leftDepth; 
    else 
     result = rightDepth; 
    return result; 
} 

template <class T> 
void BinaryTree<T>::remove(T input){ 
    if(!keyExists(input)) 
     cout << "ERR: trying to remove nonexistant key " << input << "\n"; 
    else{ 
     TreeNode * temp = findNode(root,input); 
     removeNode(temp); 
    }  
} 

template <class T> 
bool BinaryTree<T>::keyExists(T key){ 
    bool result; 
    if(isEmpty()) 
     result = false; 
    else{ 
     if(findNode(root,key) != 0) 
      result = true; 
     else 
      result = false; 
    } 
    return result;  
} 


template <class T> 
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findNode(TreeNode * node, T input){ 
    TreeNode * result = 0;  //Returns 0 if none found 
    if(node->key == input) 
     result = node; 
    else{ 
     if(node->leftChild != 0) 
      result = findNode(node->leftChild, input); 
     if(result == 0 && node->rightChild != 0) 
      result = findNode(node->rightChild, input); 
    } 
    return result; 
} 

template <class T> 
void BinaryTree<T>::removeNode(TreeNode * node){ 
    TreeNode * parent = 0; 
    if(node != root) 
     parent = findParent(root,node); 

    if(node->leftChild && node->rightChild){     //Case: both children (algorithm borrowed from tech-faq.com) 
     TreeNode * temp = findMin(node->rightChild); 
     string tkey = temp->key; 
     removeNode(temp); 
     node->key = tkey; 
    } else { 
     if(parent){            
      if(!(node->leftChild) && !(node->rightChild)){  //case: no children & not root 
       if(parent->leftChild == node) 
        parent->leftChild = 0; 
       else 
        parent->rightChild = 0;  
      }  
      if(!(node->leftChild) && node->rightChild){   //case: right child only & not root 
       if(parent->leftChild == node) 
        parent->leftChild = node->rightChild; 
       else 
        parent->rightChild = node->rightChild;  
      } 
      if(node->leftChild && !(node->rightChild)){   //case: left child only & not root 
       if(parent->leftChild == node) 
        parent->leftChild = node->leftChild; 
       else 
        parent->rightChild = node->leftChild;  
      } 
      delete node; 
      size--; 
     } 
     else{ 
      if(node->leftChild)        //case: left child only & root 
       root = node->leftChild; 
      else           //case: right child only & root 
       root = node->rightChild; 
      delete node;         //case: no children & root intrinsically covered 
      size--;  
     } 
    } 
} 

template <class T> 
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findMin(TreeNode * node){ 
    TreeNode * result; 
    if(node->leftChild == 0) 
     result = node; 
    else 
     result = findMin(node->leftChild); 
    return result; 
} 

template <class T> 
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findParent(TreeNode * start, TreeNode * child){ 
    TreeNode * result = 0; 

    if(start->leftChild){ 
     if(start->leftChild->key == child->key) 
      result = start; 
     else 
      result = findParent(start->leftChild, child); 
    } 
    if(start->rightChild && result == 0){ 
     if(start->rightChild->key == child->key) 
      result = start;  
     else 
      result = findParent(start->rightChild, child); 
    } 
    return result; 
} 

template <class T> 
void BinaryTree<T>::destroySubTree(TreeNode * node){ 
    TreeNode * parent = 0; 
    if(node != root) 
     parent = findParent(root,node); 
    if(node->leftChild) 
     destroySubTree(node->leftChild); 
    if(node->rightChild) 
     destroySubTree(node->rightChild); 
    if(parent){ 
     if(parent->leftChild == node) 
      parent->leftChild = 0; 
     else 
      parent->rightChild = 0; 
    } 
    size--; 
    delete node;  
} 

template <class T> 
BinaryTree<T>::~BinaryTree<T>(){ 
    if(!isEmpty()) 
     destroySubTree(root); 
} 



#endif 

Answer 1

当T为std::string，你将最终不得不用相同的签名功能，这就是为什么你的编译器是抱怨。为了克服这个问题，只需将compareVals作为自己的模板。我也建议你让他们static，这样你就可以打电话给他们没有对象。

static int compareVals(std::string const& v1, std::string const& v2) 
{ 
    //compare std::string 
} 

template<typename U> 
static int compareVals(U v1, U v2) 
{ 
    //compare everything else 
} 

事实上，std::stringdoes have built in relational operators，所以对你的具体使用情况下，它可能没有必要定义像上面比较功能。无论如何，这种方法可能仍然有用，可以避免为将来最终支持的每种数据类型定义假设运算符。