Public Group

# C++ template functions

This topic is 4308 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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 on other sites
Quote:
 Original post by EasilyConfusedJust 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 on other sites
Quote:
 Original post by EasilyConfusedJust 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 on other sites
Oh yeah. Sorry. Obvious really.

##### Share on other sites
Quote:
 Original post by Emmanuel DelogetUnfortunately, there is no way to avoid the median() 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 on other sites
I'd be tempted to take a range (std::pair of iterators) and return a range (std::pair of iterators).

Alternatively, you could take a container and return container::value_type

1. 1
2. 2
3. 3
4. 4
5. 5
Rutin
17

• 10
• 12
• 9
• 12
• 37
• ### Forum Statistics

• Total Topics
631420
• Total Posts
2999987
×