c++ - テンプレートクラスとして渡された文字列を比較する方法は?

Question

任意のデータ型 (int、float、string など) を格納できるように、テンプレートクラスを使用するデータ構造があります。

データは整理されるため、2 つの値を比較する方法が必要です。通常は > または < を使用できますが、文字列で >/< 演算子を使用しても、アルファベット順でどちらが最初に来るかがわからないため、文字列の場合は機能しません。そのためには、compare() 関数を使用する必要があります。

ただし、データ構造はテンプレートクラスであるため、compare() 関数を使用するように指示することはできません。これは、文字列以外の場合は compare() 関数を認識しないためです。

回避策として、2 つの比較関数を作成してみました。

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

c++ - テンプレートクラスとして渡された文字列を比較する方法は?

1 に答える 1

Related

Reference