C++ Why does error "no matching function" appear when it 100% looks like they match?

Question

I don't understand why I'm getting an error that states my function doesn't match my defined template function. To me, they look exactly the same. Here is the error in my debug:

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

So I can learn and write better generic functions and templates, what do I need to change to make that error go away? (Just to be clear, I'm not asking for help with my mergesort algorithm - I know it has problems, but I'll work them out.)

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

@T.C. - that phase has been really useful, and now I understand that my compiler isn't able to deduce it. But I've tried what is shown in several examples, especially this one: http://stackoverflow.com/questions/25245453/what-is-a-nondeduced-context ... I still just can't wrap my head around this - I'm sure it's a simple concept, but I just don't get what I did wrong. — NonCreature0714, May 08 '16 at 23:58
Why are you using `typename vector::iterator` rather than `vector::iterator`? — Charles, May 09 '16 at 00:38
Because my compiler said I required it in debug, and a huge amount of error messages went away when I did. I know that's not a good answer, but that's why. — NonCreature0714, May 09 '16 at 00:40
@c650 [Where and why do I have to put the “template” and “typename” keywords?](http://stackoverflow.com/q/610245/2069064) — Barry, May 09 '16 at 00:42
@Barry I know about `template`, but I've gotten _this_ far without using `typename` as it is used above. — Charles, May 09 '16 at 00:44

score 8 · Accepted Answer · edited May 23 '17 at 11:59

The problem is that this is a non-deduced context:

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

There are two good answers for why this function call fails to compile.

As to how to fix it - even if the above code did work, there's no reason to limit your functionality to vector iterators anyway. You can merge-sort other containers too. So just deduce any iterator:

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

Moreover, typically we'd typically expect the merge to be modifying the range provided, not returning a new container. So really prefer:

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

There's a few other issues in your code. The call to std::merge() here:

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

newVector is empty before this call, so we're just going to overwrite memory that it doesn't own. You'll want to do:

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

Good answer, that got me to the right direction - thanks! – NonCreature0714 May 09 '16 at 01:06 — NonCreature0714, May 09 '16 at 01:06

C++ Why does error "no matching function" appear when it 100% looks like they match?

1 Answers1

Linked