4

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?

  • So I know that I need to sort the vector in order to find the median -- You don't need to call std::sort. Use std::nth_element (see example) – PaulMcKenzie Apr 20 at 20:33
  • Depending on what exactly the functional requirements for your program are, you could consider moving your sort to your Collect() method so your vector is always sorted. Also you may want to take a look at this answer:stackoverflow.com/questions/15843525/… – DNT Apr 20 at 20:40
  • 3
    @PaulMcKenzie It's faster but std::nth_element still changes the vector. Probably the simple approach would be to copy the vector locally and use nth_element on that to return the median. No state change and const is enforced. – doug Apr 20 at 20:52
  • 1
    I believe this is a homework assignment problem. Just a while ago, there was a similar question relating to finding the mean posted by OP. That question was answered by a user and discussed in comments. After a day, the question was totally modified to calculate the median and then subsequently deleted. Now a new question has been posted which is exactly the same as the modified question. I recommend asking separate questions and not deleting original posts. Thank you! – Mukul Gupta Apr 20 at 20:53
  • If median is only occasionally called, you could make a copy of the vector and sort or quick select the copy (note - quick select has worst case time of O(n^2)). – rcgldr Apr 21 at 0:03
11

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.

  • 1
    @JeJo I think the OP just accepted the first answer they saw and then left – Kerndog73 Apr 21 at 9:23
  • @Kerndog73 this answer actually makes a lot more sense to me than the mutable one haha. I accepted the first answer that “unbroke” my code because i was on a deadline but I really appreciate the thoroughness of your answer + explanation and understand why it would be better programming practice – Sarah Apr 21 at 18:24
-1

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.

-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;
}
  • Since this is for a school assignment having a mutable vector is probably fine. However this probably isn't the best solution since as someone using this function I would expect calculating the median to leave it's ordering unchanged. Best solution is to copy or if the median function will be called very often some other tricks – Mitchel Paulin Apr 20 at 21:35
  • 3
    Ugh.. I think this answer might lead to the conclusion of "Hmm, if I have a problem with a const method, just make the members mutable to make it compile." There are other answers that solve the problem better, without breaking constness. – Andre Kostur Apr 21 at 6:17
  • 1
    @MitchelPaulin since this is an assignment for someone learning, using mutable to break constness is a bad thing to learn. I'm with Andre Kostur here. mutable should be use to handle "logical" constness when "bitwise" constness cannot be guaranteed. here a good explanation IMHO – Gian Paolo Apr 21 at 6:55
  • @MitchelPaulin Interesting, i guess we have different expectations. I would expect for the second calculation of a median on the same dataset to produce a faster result. I guess i will update an answer to show a better solution. – v010dya Apr 22 at 15:49
  • 1
    @LuisColorado and v010dya I appreciate y'all's effort to help me but I would appreciate it even more if you would stop beefing over const methods in the stack overflow comments lmao – Sarah Apr 25 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.