no matching function call for selection sort funct

问题:

I'm playing around with templates and I was wondering why I'm getting a no matching function error using templates.

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

回答1:

You have an undeduced template parameter T, so you need 1) move your typename T as the first template parameter:

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

and 2) to qualify your call to sort as selection_sort<int>(v.begin(), v.end());

BTW, here's a somwhat more generic implementation of selection sort, note it takes only an iterator and comparison function as template parameters, with the comparison function taking the value type that the iterator points to (this is C++11 code because of the default function template parameter, for C++98 compilers you need to have 2 overloads, with or without the comparison function)

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

The call to std::min_element is equivalent to your for loop, and the iter_swap is equal to your own swap. The advantage of using STL algorithms is that they are much more likely to be correct (off-by-one errors in handwritten code are very common)

PS: you can similarly write an insertion_sort algorithm in 2 lines using std::upper_bound and std::rotate (exercise for the reader)

回答2:

The problem is that typename T which seems not to be used, can't be deduced by the compiler. You will have to specify the types explicitly:

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