C++ Почему появляется ошибка "нет соответствующей функции", когда она на 100% выглядит так, как будто они совпадают?

Question

Я не понимаю, почему я получаю сообщение об ошибке, в котором говорится, что моя функция не соответствует моей определенной функции шаблона. Для меня они выглядят точно так же. Вот ошибка в моей отладке:

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

Так что я могу лучше изучить и написать общие функции и шаблоны, что мне нужно изменить, чтобы эта ошибка исчезла? (Просто чтобы прояснить, я не прошу помощи с моим алгоритмом сортировки слиянием - я знаю, что у него есть проблемы, но я их решу.)

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