Median of a Vector assignment

Question

I've been reading Bjarne's Principles in Programming and was given some code to demonstrate the usage of vectors and how we can return specific values for certain functionality such as mean and median. However, in the chapter I noticed that the code he provided was purposely made so that it doesn't always calculate the median correctly which was correct, he had purposely made it so we had to go back and alter the code as follows:

#include "../../std_lib_facilities.h"

int main()
{
  vector<double> temps;
  for (double temp; cin >> temp;)
      temps.push_back(temp);

  sort(temps);
  cout << "Median temperature: " << temps[temps.size() / 2] << '\n';
}

However, when asked in a question format it states:

If we define the median of a sequence as “a number so that exactly as many elements come before it in the sequence as come after it,” fix the program in 4.6.3 so that it always prints out a median. Hint: A median need not be an element of a sequence.

I assumed he meant that we want equal values on both sides of our median as the previous algorithm only divides the vector size by 2 and returns, if odd the middle index + 1, therefore I'm assuming that he wanted the exact median value of the range rather than a specific element within the array? Regardless, the code I had created follows:

//Program to compute the median of a temperature vector
#include "../../std_lib_facilities.h"

int main()
{
    //Define variables and Read in values
    double median_value;
    vector<double> temps;
    for (double temp; cin >> temp;)
        temps.push_back(temp);

    //Compute Median Temperatures
    sort(temps);

    if (temps.size() % 2 == 0)
        median_value = (temps[temps.size() / 2] + temps[temps.size() / 2 - 1]) / 2;
    else 
        median_value = temps[temps.size() / 2];

    cout << "Median Temperature of input values: " << median_value << '\n';
    for (int i = 0; i < temps.size(); ++i) cout << temps[i] << ", ";
}

I'm assuming this is what he meant by “a number so that exactly as many elements come before it in the sequence as come after it". I've probably missed the point of this exercise hence the post for some verification that I completed the exercise correctly.

Answer 1

#include "../../std_lib_facilities.h"

While PPP is structured around using this header, you will eventually be including only what you really need to make your code self-sufficiently compilable. So instead of including a bunch of libraries you don't need, just include what you use.

#include <iostream>
#include <vector>

The header Stroustrup provides also imports all visible symbols in namespace std into the global namespace. The global namespace is then polluted with a bunch of names that could lead to collisions. The compiler could resolve function overloads in unexpected ways. Essentially, using namespace std; is considered bad practice. If you must use using directives, keep the use in the narrowest scope possible. Otherwise, qualify names with their namespace as the namespace will help the reader understand what is being called and from where.

---

    double median_value;

Avoid declaring variables before you need them. This technique is an artifact of older programming languages that didn't allow initialization of variables and constants after a statement. Errors commonly associated with this technique include use-before-set, incorrectly initialized variables, and possibly non-contextual reuse due to programmer laziness.

The simplest solution is to declare the variable as close to its initialization point.

    double median_value;
    if (temps.size() % 2 == 0)
        median_value = ...;

Even better, directly initialize the variable with a value.

    const auto median_value = median(temps);

This reduces the chance of errors happening as well as reducing the cognitive load for readers. Directly initializing variables also allows you to take advance of const/constexpr.

---

    sort(temps);

Do you need to sort the entire container? When we're looking to find the median, we're only interested in picking out either the middle value or the middle two values. Rather than sort, we would rather select. C++ implementations typically provide introselect for its selection algorithm (std::nth_element).

As you learn more about <algorithm> and iterators, keep this in mind.

---

        median_value = (/* ... */ + temps[temps.size() / 2 - 1]) / 2;

It's really important to keep in mind the possible states a variable can represent. In the case of temps, that std::vector<double> could represent any number of doubles as well as nothing. When temps is empty, temps.size() / 2 - 1 evaluates to 0 / 2 - 1. It's important to note that temps.size() returns size_type, an alias for an unsigned value. Thus, subtracting one from unsigned zero results in the maximum value held by std::vector<double>::size_type. It's essentially a really large value almost guaranteed to be out of bounds when used in your context. Out of bound index access is a common case of undefined behavior.

If the user doesn't provide you with values, you can't calculate a median. temps having at least one value is a precondition for calculating the median. Check your preconditions and notify the user if they mess up. How you notify the user is up to you, but keep this in mind as you go over chapters on error and exception handling.

---

    for (int i = 0; i < temps.size(); ++i) cout << temps[i] << ", ";

As stated before, temps.size() returns an unsigned value. The comparison i < temps.size() is a signed-unsigned mismatch. If temps contains more values than i can represent, you'll have a bug.

If you are simply accessing the elements and don't need to apply transformations on the index, use the range-based for loop.

    for (auto temp : temps) std::cout << temp << ", ";