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

Question

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

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

/*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());
}

2

c++selection sorting template-deduction templates

Решение

Другие решения

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

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

3

Источник

Accepted Answer

У вас есть необнаруженный параметр шаблона 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 (упражнение для читателя)

7