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

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
• @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
• 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

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.

• @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

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.

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
• 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
• @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
• @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