how to find the median of a vector if the method is const?

Question

I've created a method called Collect that adds a bunch of values to a vector (shown below)

void Median::Collect(double datum)
{
  myVector.push_back(datum);
}

I need to create a method that calculates the median of all of the values I collected in the vector in the method above. The function definition is written below

/* Calculates the median of the data (datum) from the Collect method.
 */
 double Median::Calculate() const
{

}

So I know that I first need to sort the vector in order to find the median. Below is my attempt:

    double Median::Calculate() const
  {
    std::sort(myVector.begin(), myVector.end());
    double median;
    if (myVector.size() % 2 == 0)
    {// even
        median = (myVector[myVector.size() / 2 - 1] + myVector[myVector.size() / 2]) / 2;
    }
    else
    {// odd
        median = myVector[myVector.size() / 2];
    }
    return median;
  }

But I realized that this wasn't compiling because the method is const, so sorting the values of the vector would alter the vector, which isn't allowed in a const function. So what am I supposed to be doing for this method?

Answer 1

Make a copy of myVector, sort it and then calculate the median of that.

We can do a little better than just using std::sort. We don't need to sort the vector completely in order to find the median. We can use std::nth_element to find the middle element. Since the median of a vector with an even number of elements is the average of the middle two, we need to do a little more work to find the other middle element in that case. std::nth_element ensures that all elements preceding the middle are less than the middle. It doesn't guarantee their order beyond that so we need to use std::max_element to find the largest element preceding the middle element.

Another thing that you may not have considered is the case where myVector is empty. Finding the median of an empty vector doesn't really make any sense. For this example, I just used an assert but you might want to throw an exception or something.

double Median::calculate() const {
  assert(!myVector.empty());
  std::vector<double> myVectorCopy = myVector;
  const auto middleItr = myVectorCopy.begin() + myVectorCopy.size() / 2;
  std::nth_element(myVectorCopy.begin(), middleItr, myVectorCopy.end());
  if (myVectorCopy.size() % 2 == 0) {
    const auto leftMiddleItr = std::max_element(myVectorCopy.begin(), middleItr);
    return (*leftMiddleItr + *middleItr) / 2.0;
  } else {
    return *middleItr;
  }
}

Another option is to use a different container to ensure that elements are always sorted. You might consider using std::set. When you insert into an std::set, the set remains sorted so don't have to use std::sort, std::nth_element or std::max_element to find the median. You would get the middle element.

Answer 2

A const method is a method that can be called only on const instances of the class it belongs to. So, if you have declared a class Median and you declare a const method on it, then it can only be called with const instances of the Median class. There's no possibility to affect a different class, like std::vector with that.

Anyway, in case you decide to derive a new class from std::vector and consider adding to it a method median to calculate the median, you had better to declare it const. The reason for this is that you don't need to modify the array to get it's median (see below).

In the case you need to sort the array, then you can make a copy, or even better, consider using an array of pointers to the array elements, then sort that array instead, based on the values of the pointed to values, and then consider the central element of that array. In this way, you are not touching the original instance and can still maintain the const attribute for the method.

Answer 3

You could declare your myVector as mutable. This will allow for the data to change in it, even if you are in a const function.

If, for some reason, that is not an option, you can consider using some datatype that keeps your data sorted and inserts new data in a correct position. Then you will not need to sort it each time you run this function, but you will slow down inserts. Consider what is going to happen more often: inserts or getting the median.

---

A harder approach would be to have the best of both worlds. Your vector would remain unchanged, and the second run of the same function would actually return the answer faster than the first.

You can then do the following:

// Median.hpp
class Median
{
  std::vector<double> myVector;
  mutable double median;
  mutable bool medianCalculated;
// the rest is the same
};

// Median.cpp
double Median::calculate() const
{
  if(!medianCalculated)
  {
    std::vector<double> copyVector = myVector;
    std::sort(copyVector.begin(), copyVector.end();
    const auto m1 = copyVector.begin() + (copyVector.size() / 2);
    const auto m2 = copyVector.begin() + ((copyVector.size() + 1) / 2);
    median = (*m1 + m2) / 2; // m1==m2 for even sized vector m1+1==m2 for odd sized
    medianCalculated=true;
  }
  return median;  
}
void Median::Collect(double datum)
{
  myVector.push_back(datum);
  medianCalculated=false;
}