推导模板参数 [英] Deducing template arguments

问题描述

我写了代码构建二叉搜索树和一个二进制搜索树来测试它是否有效，但我有很多错误，我调试它们很长时间，并找不到错误。

 ＃include< vector> 
 
 template< typename Key，typename Value> 
 struct BSTNode {
 Key key; 
值值; 
 BSTNode * left; 
 BSTNode * right; 
 BSTNode（Key k，Value v，BSTNode * l = NULL，BSTNode * r = NULL）：
 key（k），value（v），left（l），right 
}; 
 
 template< typename Key，typename Value> 
 BSTNode< Key，Value> * min_height（std :: vector< int>& v，int left，int right）{
 if（left< = right）{
 int mid =左+（右 - 左）/ 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）; 
} 
  

编译器错误：

< blockquote>

  prog.cpp：在函数'BSTNode< Key，Value> * min_height（std :: vector< int>& int，int） 
 prog.cpp：48：42：error：没有匹配的函数调用'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注意：模板参数扣除/替换失败：
 prog。 cpp：48：42：注意：不能推导模板参数'Key'
 prog.cpp：49：41：error：没有匹配函数调用'min_height（std :: vector< int& int& amp; 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注意：模板参数扣除/替换失败：
 prog。 cpp：49：41：注意：无法推导模板参数'Key'
 prog.cpp：在函数'int main（）'：
 prog.cpp：63：45：error：函数调用'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注意：模板参数扣除/替换失败：
 prog。 cpp：63：45：注意：无法推导模板参数'Key'
 prog.cpp：63：22：warning：未使用的变量'root'[-Wunused-variable] 
  

解决方案

类型。

您可以显式：

  BSTNode< int ，int> * root = min_height< int，int>（v，0,5） 
  

为了这个工作，你还需要更新你的函数， code> min_height ：

  node-> left = min_height< Key，Value& （v，left，mid-1）; 
 node-> right = min_height< Key，Value>（v，mid + 1，right）; 
  

但是，看起来， min_height 总是将整数放入键和 Value 。你可以通过取一些类型的向量来更通用，并且通过使用该类型作为键和值。

  template< typename类型> 
 BSTNode< Type，Type> * min_height（vector< Type>& v，int left，int right）{
 if（left< = right）{
 int mid = 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）; 
  

I wrote code to construct binary search tree and also a bfs a binary search tree to test whether it works, but i got a lot of bugs, I debug them for a long time and cannot find the bug.

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

Compiler error:

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]

解决方案

You can't deduce template types based upon the return type.

You can be explicit though:

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

For this to work though, you also need to update your function to be explicit in its calls to min_height:

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

However, by the looks of it, min_height is always putting integers into Key and Value. You could make it more generic by taking a vector of some Type, and more explicit by using that type as the Key and Value types.

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

Usage:

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

这篇关于推导模板参数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！