Error with templates: no matching function call

Question

I'm working my way through accelerated C++ & have hit a problem with Ex. 10.2 The questions involves rewriting a median function from a previous chapter, so that now median can be called with a vector or built-in array. The median function should also allow containers of any arithmetic type.

I cannot make the two calls to median detailed below - I receive the error message

No matching function for call to 'median'

I gather from some research that when Templates are used the Type should be known at compile time. Might this be the underlying issue? Is there a way to somehow pass the Type as a template argument?

Here is my code so far:

#include <iostream>
#include <vector>
#include <stdexcept>
#include <algorithm>
#include <cstddef>

using namespace std;

template <class Iterator, class Type>
Type median(Iterator begin, Iterator end)
{
    vector<Type> vec(begin,end);
    typedef typename vector<Type>::size_type container_sz;
    container_sz size = vec.size();

    if (size == 0) {
        throw domain_error("median of an empty vector");
    }

    sort(vec.begin(), vec.end());

    container_sz mid = size/2;
    return size % 2 ==  0 ? (vec[mid] + vec[mid - 1]) / 2 : vec[mid];
}

int main()
{
    vector<int> grades;

    for (int i = 0; i != 10; ++i){
        grades.push_back(i);
    }

    const int int_array[] = {2, 9, 4, 6, 15};
    size_t array_size = sizeof(int_array)/sizeof(*int_array);

    cout << median(int_array, int_array + array_size) << endl;   //error here: Semantic Issue, No matching function for call to 'median' 
    cout << median(grades.begin(), grades.end()) << endl;        //error here: Semantic Issue, No matching function for call to 'median' "

    return 0;
}

Answer 1

The best way to tackle this issue, generally, is by using iterator_traits as described above. However in order to answer the particular question 10.2 from the book (which does not assume Iterator_trait knowledge), one can proceed as follows: - Note class Type must be listed first, instead of class Iterator. Also, one must call median<int>(grades.begin(), grades.end()) as opposed to median(grades.begin(), grades.end())

#include <iostream>
#include <vector>
#include <stdexcept>
#include <algorithm>
#include <cstddef>

using namespace std;

template <class Type, class Iterator>       //the order allows the second template parameter type to be deduced (Iterator)                                           
Type median(Iterator begin, Iterator end)   //while requiring you still provide the first type
{

    vector<Type> vec(begin,end);

    //typedef typename vector<Type>::size_type container_sz;
    //container_sz size = vec.size()
    auto size = vec.size();

    if (size == 0) {
        throw domain_error("median of an empty vector");
    }

    sort(vec.begin(), vec.end());

    //container_sz mid = size/2
    auto mid = size/2;

    Type ret = size % 2 ==  0 ? (vec[mid] + vec[mid - 1]) / 2 : vec[mid];

    return ret;
}


int main()
{

    vector<int> grades = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    const int int_array[] = {2, 9, 4, 6, 15};

    size_t array_size = sizeof(int_array)/sizeof(*int_array);

    cout << median<int>(int_array, int_array + array_size) << endl;  //must provide int here, in order to give the template the return type at compile time
    cout << median<int>(grades.begin(), grades.end()) << endl;


return 0;

}

Answer 2

Your error is rooted in the deduction of Type which is not possible with the arguments provided. You can do this using the standard library class iterator_traits as follows:

template <
    class Iterator, 
    class Type = typename std::iterator_traits<Iterator>::value_type>
Type median(Iterator begin, Iterator end)
{
    vector<Type> vec(begin,end);

    typedef typename vector<Type>::size_type container_sz;

    container_sz size = vec.size();

    if (size == 0) {
        throw domain_error("median of an empty vector");
    }

    sort(vec.begin(), vec.end());

    container_sz mid = size/2;

    return size % 2 ==  0 ? (vec[mid] + vec[mid - 1]) / 2 : vec[mid];
}

The class iterator_traits dissects the Iterator type provided to determine what it is actually iterating (a little more complicated than that, but that is a decent summary). For more information on how it works, see the documentation of class iterator_traits. It is a most-handy mechanism for determining iterator value types.

Note: to ensure no unintended bypasses of the default template parameter Type declaration you can also do this:

template <class Iterator>
typename std::iterator_traits<Iterator>::value_type median(Iterator begin, Iterator end)
{
    if (begin == end)
        throw domain_error("median of an empty vector");

    typedef typename std::iterator_traits<Iterator>::value_type Type;
    std::vector<Type> vec(begin,end);
    sort(vec.begin(), vec.end());

    typename std::vector<Type>::size_type mid = vec.size()/2;
    return vec.size() % 2 ==  0 ? (vec[mid] + vec[mid - 1]) / 2 : vec[mid];
}

Its a little dense, and throws out most of the intermediate stuff, but if you stare at it long enough you'll understand how it works, and it reduces your template parameter list to only use the one thing you really care about; the Iterator type, which is trivially deduced by the parameters you provide to the function.