1

バイナリ検索ツリーを構築するコードと、それが機能するかどうかをテストするためのbfsバイナリ検索ツリーを作成しましたが、多くのバグが発生し、長い間デバッグしていて、バグを見つけることができません。

#include<vector>

template<typename Key, typename Value>
struct BSTNode{
    Key key;
    Value value;
    BSTNode * left;
    BSTNode * right;
    BSTNode(Key k, Value v, BSTNode *l=NULL, BSTNode *r=NULL) :
    key(k), value(v), left(l), right(r) {}
};

template<typename Key, typename Value>
BSTNode<Key, Value>* min_height(std::vector<int> &v, int left, int right ) {
    if(left<=right){
        int mid=left+ (right-left)/2;
        BSTNode<Key, Value>* node=new BSTNode<Key, Value>(v[mid], v[mid]);
        node->left=min_height(v, left, mid-1 );
        node->right=min_height(v, mid+1, right );
        return node;
    }
}

int main(){
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    BSTNode<int, int>* root=min_height(v, 0, 5);
}

コンパイラエラー：

prog.cpp: In function ‘BSTNode<Key, Value>* min_height(std::vector<int>&, int, int)’:
prog.cpp:48:42: error: no matching function for call to ‘min_height(std::vector<int>&, int&, int&)’
prog.cpp:48:42: note: candidate is:
prog.cpp:44:22: note: template<class Key, class Value> BSTNode<Key, Value>* min_height(std::vector<int>&, int, int)
prog.cpp:44:22: note:   template argument deduction/substitution failed:
prog.cpp:48:42: note:   couldn't deduce template parameter ‘Key’
prog.cpp:49:41: error: no matching function for call to ‘min_height(std::vector<int>&, int&, int&)’
prog.cpp:49:41: note: candidate is:
prog.cpp:44:22: note: template<class Key, class Value> BSTNode<Key, Value>* min_height(std::vector<int>&, int, int)
prog.cpp:44:22: note:   template argument deduction/substitution failed:
prog.cpp:49:41: note:   couldn't deduce template parameter ‘Key’
prog.cpp: In function ‘int main()’:
prog.cpp:63:45: error: no matching function for call to ‘min_height(std::vector<int>&, int, int)’
prog.cpp:63:45: note: candidate is:
prog.cpp:44:22: note: template<class Key, class Value> BSTNode<Key, Value>* min_height(std::vector<int>&, int, int)
prog.cpp:44:22: note:   template argument deduction/substitution failed:
prog.cpp:63:45: note:   couldn't deduce template parameter ‘Key’
prog.cpp:63:22: warning: unused variable ‘root’ [-Wunused-variable]
4

1 に答える 1

7

戻り値の型に基づいてテンプレートの型を推測することはできません。

ただし、明示的に指定できます。

BSTNode<int, int>* root = min_height<int, int>(v, 0, 5);

ただし、これを機能させるには、関数を への呼び出しで明示的に更新する必要もありますmin_height。

node->left = min_height<Key, Value>(v, left, mid - 1);
node->right = min_height<Key, Value>(v, mid + 1, right);

しかし、見た目では、min_heightは常に と に整数を入れていKeyますValue。vector一部のを取得することでより一般的にすることができ、その型をおよびType型として使用することでより明示的にすることができます。KeyValue

template<typename Type>
BSTNode<Type, Type>* min_height(vector<Type> &v, int left, int right ) {
    if(left<=right) {
        int mid = left + (right - left)/2;
        BSTNode<Type, Type>* node = new BSTNode<Type, Type>(v[mid], v[mid]);
        node->left = min_height(v, left, mid - 1);
        node->right = min_height(v, mid+1, right);
        return node;
    }
}

使用法：

BSTNode<int, int>* root = min_height(v, 0, 5);
于 2013-03-11T22:06:49.810 に答える