Нет вызова соответствующей функции для функции сортировки с шаблонами (C++)

Question

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

/*selection sort*/
template <typename InputIterator, typename T>
void selection_sort(InputIterator first, InputIterator last){
    InputIterator min;
    for(; first != last - 1; ++first){
        min = first;

        for(T i = (first + 1); i != last ; ++i)
        {
            if(*first < *min)
                min = i;
        }
        myswap(*first, *min);
    }
}

int main(){
    int a[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    vector<int> v(a, a+10);
    selection_sort(v.begin(),v.end());
}

Answer 1

У вас есть необнаруженный параметр шаблона T, поэтому вам нужно 1) переместить typename T в качестве первого параметра шаблона:

// now InputIterator will be deduced
template <typename T, typename InputIterator>
void selection_sort(InputIterator first, InputIterator last)
{
    // your implementation
}

и 2) чтобы квалифицировать ваш звонок для сортировки как selection_sort<int>(v.begin(), v.end());

Кстати, вот немного более общая реализация сортировки выбора, обратите внимание, что она принимает только итератор и функцию сравнения в качестве параметров шаблона, а функция сравнения принимает тип значения, на который указывает итератор (это код C++11 из-за значения по умолчанию параметр шаблона функции, для компиляторов C++98 необходимо иметь 2 перегрузки, с функцией сравнения или без нее)

template< typename ForwardIterator, typename Compare = std::less<typename std::iterator_traits<ForwardIterator>::value_type> >
void selection_sort(ForwardIterator first, ForwardIterator last, Compare cmp = Compare())
{
        for (auto it = first; it != last; ++it) {
                auto const selection = std::min_element(it, last, cmp);
                std::iter_swap(selection, it);
        }
}

Призыв к std::min_element эквивалентно вашему для цикла, а iter_swap равно вашему собственному свопу. Преимущество использования алгоритмов STL состоит в том, что они с большей вероятностью будут правильными (очень часты ошибки в рукописном коде)

PS: аналогичным образом вы можете написать алгоритм inserttion_sort в 2 строки, используя std::upper_bound а также std::rotate ( упражнение для читателя)

Answer 2

Проблема в том, что typename T который, кажется, не используется, не может быть выведен компилятором. Вы должны будете указать типы явно:

selection_sort<vector<int>::iterator, int>(v.begin(),v.end());