演繹模板參數

Question

我編寫代碼構建二叉搜索樹，並且還編寫了一個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] 

Answer 1

不能推斷基於返回類型的模板類型。

你可以明確不過：

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來更通用，並且通過使用該類型作爲Key和Value類型更明確。

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);