1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ you need to take of the case where temps.size() == 0, because it fits the temps.size() % 2 == 0 but then temps[temps.size() / 2 - 1] will backfire \$\endgroup\$ – papagaga Oct 30 '18 at 0:13
  • \$\begingroup\$ besides you can't solve the problem in certain cases, such as a vector of even size filled with only one number ( [2,2,2,2] for instance): there's is no number such as "exactly as many elements come before it in the sequence as come after it". So what will you do about it? \$\endgroup\$ – papagaga Oct 30 '18 at 0:17
  • \$\begingroup\$ I was thinking about that and the only method I could think of was to print the vector and in the middle show the median value between the exact number of elements adjacent to computed value. \$\endgroup\$ – Ulivax Oct 30 '18 at 0:20
  • \$\begingroup\$ Printing is an idea but I feel like it's not pertinent here. You should be able to use the median after computing it. At this point, you could consider that the problem wasn't well thought out in the first place, or consider that certain inputs are invalid (empty vector, or uniform, even-sized vector) and ask for another one. \$\endgroup\$ – papagaga Oct 30 '18 at 0:30
3
\$\begingroup\$
#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 << ", ";
\$\endgroup\$

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.