1

I am going through accelerated C++ and I am stuck in exercise 10.3 and I have literally no clue how to even start. I would like to mention here that its not homework exercise and I am reading it just to gain confidence in C++ . The question is shown below .

Rewrite the median function from §8.1.1/140 so that we can call it with either a vector or a built-in array. The function should allow containers of any arithmetic type.

The code for above question is given below

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

I have no clue what to do next. Any help or criticism will be beneficial to me. Thanks and regards

samantha
  • 565
  • 3
  • 13
  • 29
  • 1
    Hint: standard library pass iterators to specify ranges to be processed. You could do something similar. – juanchopanza Feb 20 '13 at 00:08
  • 2
    Use `std::begin` and `std::end`. – Mooing Duck Feb 20 '13 at 00:09
  • If I am not wrong std::begin is a part of C++11 and I am using mac with gcc 4.2 and it doesnt support .. so I am wondering if I Can use other method? – samantha Feb 20 '13 at 00:21
  • 1
    Yes, you can. Since an array's elements are contiguous, you can pass a pointer to the first element, and one to one past the end of the last element. Pointers satisfy many of the requirements of iterators. See [here](http://stackoverflow.com/questions/713309/c-stl-can-arrays-be-used-transparently-with-stl-functions) for example. Although I would suggest implementing your own `begin` and `end` functions. – juanchopanza Feb 20 '13 at 00:25
  • Thanks juanchopanza, Mooing duck, I guess with the hints you guys have provided , I think I will be able to solve the problem. Will give a try tomorrow evening as its pretty late here. Thanks a lot agian for quick reply. I was bit scared that I might get lot of negative points here .. – samantha Feb 20 '13 at 00:32

2 Answers2

1

The comments from juanchopanza and Mooing Duck with hints on iterators is probably the right approach for the book exercise. However, in a practical application, I may instead write a wrapper function that would accept an array, and call the original function that accepts the vector:

template <class T, size_t N>
T median (const T (&a)[N])
{
    return median(std::vector<T>(a, a+N));
}
jxh
  • 69,070
  • 8
  • 110
  • 193
  • The exercise calls for a function that can be called with both though. – juanchopanza Feb 20 '13 at 00:41
  • @juanchopanza: I am not disputing that. With function overloading, my suggestion provides a function name that can be called by both (not a single function). – jxh Feb 20 '13 at 01:22
  • Seems to be not very performant to create a temporary vector and copying all the data (on the other hand we have a sort for the median). – Sebastian May 17 '22 at 19:50
  • @Sebastian It will depend on how large `T` is whether you want to adjust the strategy to sort references to objects or the objects themselves. – jxh May 17 '22 at 21:32
1

I realize that the question is quite old but as I'm currently working through the same book I figured I would post my solution in the hope that it may help someone else.

// median.hpp

#include <algorithm>          // sort
#include <stdexcept>          //domain_error
#include <vector>

template <typename T, typename In>
T median(In begin, In end)
{
    if (begin == end)
        throw std::domain_error("median of an empty vector");
    
    std::vector<T> v { };
    while (begin != end)
    {
        v.push_back(*begin++);
    }
    
    std::sort(v.begin(), v.end());
    
    typedef typename std::vector<T>::size_type vec_sz;
    
    vec_sz vSize = v.size();
    vec_sz mid = vSize/2;
    
    return vSize % 2 == 0   ? ( v[mid] + v[mid - 1] ) / 2
                            : v[mid];
}
Vilhelmo De Okcidento
  • 33
  • 3