C++为什么当100%看起来匹配时出现错误"无匹配功能"？

Question

我不明白为什么我收到一个错误,指出我的函数与我定义的模板函数不匹配.对我来说,它们看起来完全一样.这是我的调试中的错误:

error: no matching function for call to 'mergesort' newVec = mergesort(vec.begin(),vec.end());

所以我可以学习和编写更好的通用函数和模板,我需要更改什么才能使错误消失？(为了清楚起见,我不是要求我的mergesort算法帮助 - 我知道它有问题,但我会解决它们.)

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
vector<T> mergesort(typename vector<T>::iterator, typename vector<T>::iterator);

int main() {
    vector<int> vec{ 50, 5, 40, 10, 30, 15, 20, 20, 10, 25 };
    vector<int> newVec;

    newVec = mergesort(vec.begin(),vec.end()); //Doesn't match???

    cout << "before:";
    for (auto x : vec) cout << x << ' '; cout << '\n';
    cout << "after :";
    for (auto x : newVec) cout << x << ' '; cout << '\n';
    return 0;
}

template <typename T>
vector<T> mergesort(typename vector<T>::iterator begin, typename vector<T>::iterator end){
    vector<T> newVector;
    copy(begin, end, newVector);

    if(begin!=end){
        vector<T> tmp1;
        vector<T> tmp2;

        auto dist = distance(newVector.begin(),newVector.end());
        auto distance1 = dist/2;
        auto distance2 = (dist/2+1);

        auto mid1 = newVector.begin();
        auto mid2 = newVector.begin();

        advance(mid1,distance1);
        advance(mid2,distance2);

        tmp1 = mergesort(newVector.begin(), mid1);
        tmp2 = mergesort(mid2, newVector.end());

        merge(tmp1.begin(), mid1, mid2, tmp2.end(), newVector.begin());

        return newVector;
    } else {
        return newVector;
    }
}

Answer 1

问题是这是一个非推断的上下文:

template <typename T>
vector<T> mergesort(typename vector<T>::iterator, typename vector<T>::iterator);
                    ^^^^^^^^^^^^^^^^^^^^          ^^^^^^^^^^^^^^^^^^^^

为什么这个函数调用无法编译有两个 很好的答案.

至于如何解决它 - 即使上面的代码确实有效,也没有理由将你的功能限制为vector迭代器.您也可以合并排序其他容器.所以只需推导出任何迭代器:

template <typename Iterator>
vector<T> mergesort(Iterator, Iterator);

此外,通常我们通常希望合并修改提供的范围,而不是返回新的容器.所以真的更喜欢:

template <typename Iterator>
void mergesort(Iterator, Iterator);

您的代码中还有一些其他问题.致电std::merge():

merge(tmp1.begin(), mid1, mid2, tmp2.end(), newVector.begin());

newVector在此调用之前是空的,所以我们只是要覆盖它不拥有的内存.你想要做的:

newVector.reserve(dist);
merge(tmp1.begin(), mid1, mid2, tmp2.end(), std::back_inserter(newVector));