Sign in to follow this  
eyechild

C++ template functions

Recommended Posts

I'm currently learning C++ using the book "Accelerated C++", working through many of the exercises at the end of each chapter. One particular exercise at the end of chapter 10 asks you to rewrite the following template function so it can be called with any container which supports random access iterators, rather than just STL vectors:
template <class T>
T median(vector<T> v)
{
    typedef typename vector<T>::size_type vec_sz;

    vec_sz size = v.size();
    if (size == 0)
        throw domain_error("median of an empty vector");

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

    vec_sz mid = size/2;

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

My solution is as follows:
template <class T, class Ran>
T median(Ran begin, Ran end)
{
    typename typedef vector<T>::size_type vec_sz;

    if (begin == end)
        throw domain_error("median of an empty vector");

    // Copy all elements from begin to end-1 to a new vector
    vector<T> v(begin, end);

    vec_sz size = v.size();
    vec_sz mid = size/2;
    sort(v.begin(), v.end());

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

When calling this function, I need to type median<double>(begin, end), where begin and end are random access iterators on a container. My question is, is there any way to just call median(begin, end)? Right now, if I try that, my code won't compile (I'm guessing this is because the compiler has no way of knowing what type T is). Is there a better way of solving this problem that I've missed?

Share this post


Link to post
Share on other sites
Unfortunately, there is no way to avoid the median<double>() syntax if you work with random ierators. The compiler need to know the T type, and it can't deduce it.

On a side note, you can use std::sort() with random iterators too (it may not be a good idea since you'll end up by sorting the user supplied data, something he may not want).

Regards,

Share this post


Link to post
Share on other sites
What you can do though is take a non-const reference as a parameter for storing the result in, as is done with functions such as std::accumulate.

template <class T, class Ran>
T median(Ran begin, Ran end, T& result)
{
//...
result = ...;
return result;
}

Share this post


Link to post
Share on other sites
Just speculating wildly here, but is there any reason you could not return an iterator pointing to the mid value rather than the result directly?

Then the prototype would become:

template<class T> T median(T begin,T end);

and I would have thought the type would be deduced from the arguments.

Appreciate I may be missing something and talking through my hat here.

Share this post


Link to post
Share on other sites
Quote:
Original post by EasilyConfused
Just speculating wildly here, but is there any reason you could not return an iterator pointing to the mid value rather than the result directly?


The median isn't necessarily one of the values already in the data set. For example, the median of (1,2,3,4) is 2.5

EDIT: While this isn't strictly true (the median could be anything between and including 2 and 3), that's what his original code to modify was doing.

Share this post


Link to post
Share on other sites
Quote:
Original post by EasilyConfused
Just speculating wildly here, but is there any reason you could not return an iterator pointing to the mid value rather than the result directly?


I think the problem with that would be that if the container you're working with has an even number of elements, there isn't an element which is exactly in the middle, so the median is halfway between the two middle elements. Therefore I think you would have to return an iterator pointing to the element just before the middle, then expect the caller of the function to know that they have to also get the next value and then find the average. That really should be dealt with within the median function.

I'm not too sure that what I was doing before was really wrong now I come to think of it. I just thought that ideally you should be able to call template functions without using the function_name<type> syntax. Anyway, thanks for the replies, I appreciate it.

EDIT: Looks like Joanus beat me to it on the median explaination

Share this post


Link to post
Share on other sites
Quote:
Original post by Emmanuel Deloget
Unfortunately, there is no way to avoid the median<double>() syntax if you work with random ierators. The compiler need to know the T type, and it can't deduce it.

The type T is no problem, we can use std::iterator_traits<Ran>::value_type to get that (header <iterator>). Or we could just use Ran::value_type, but that would remove the possibility to pass pointers.

I guess you could just do this:
template <class Ran>
typename std::iterator_traits<Ran>::value_type
median(Ran begin, Ran end)
{
typedef typename std::iterator_traits<Ran>::value_type val_t;
typedef typename std::vector< val_t >::size_type vec_sz;

if (begin == end)
throw std::domain_error("median of an empty container");

// Copy all elements from begin to end-1 to a new vector
std::vector<val_t> v(begin, end);

vec_sz size = v.size();
vec_sz mid = size/2;
std::sort(v.begin(), v.end());

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


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this