推导模板参数

Question

我编写了构建二进制搜索树的代码，还编写了一个bfs --一个二进制搜索树来测试它是否工作，但是我发现了很多错误，我调试了很长一段时间，却找不到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);
}

编译器错误：

prog.cpp:在函数‘BSTNode* min_height(std：：Value>* &，int，int)’中: prog.cpp:48:42: prog.cpp:48:42:没有调用‘min_height’的匹配函数(std:向量&，int& )prog.cpp:48:42:注意:候选人是: prog.cpp:44:22:注意: template BSTNode*min_height(std:向量&，int，prog.cpp:44:22:注意:模板参数演绎/替换失败: prog.cpp:48:42:注意:无法推断模板参数‘Key’prog.cpp:49:41: error:对‘min_height’调用没有匹配函数(std：：向量&，int& ) prog.cpp:49:41:注意:候选人是: prog.cpp:44:22:注意:注意: template BSTNode* min_height(std：：Vector&Int，int，prog.cpp:44:22:注意:模板参数演绎/替换失败: prog.cpp:49:41:注意:无法推断模板参数‘Key’prog.cpp: In function‘int()：prog.cpp:63:45: prog.cpp:63:45:没有匹配函数调用’min_height(std::vector&，int，int)‘prog.cpp:63:45:min_height:min_height: prog.cpp:44:22: note: template BSTNode* min_height(std:Vector&int，int，( prog.cpp:44:22:注意:模板参数演绎/替换失败: prog.cpp:63:45:注意:无法推断模板参数‘Key’prog.cpp:63:22:警告:未使用变量‘root’-未使用变量-变量

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