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.