Accelerated C++ Solution to Exercise 6-7

Exercise 6-7

The portion of the grading analysis program from S6.2.1/110 that read and classified student records depending on whether they did (or did not) do all the homework is similar to the problem we solved in extract_fails. Write a function to handle this subproblem.

Solution

The “one-pass” extract_fail program (as per S6.3.2/119 of the textbook) takes in a vector<Student_info> container, extracts out the failed students, and leave the passed students in that input vector<Student_info> container. The objective of this exercise is to reuse this concept on a somewhat scenario. i.e. to takes in the same vector<Student_info> container, extracts out the students who didn’t did all the homework, and leave the students who did the homework in that input vector<Student_info> container – we can build a function called (say) extractDidnt that builds on the extract_fail program.

The Skeleton extract_fail function

The original “one-pass” extract_fail function looks like this:

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if

#include "Student_info.h"
#include "fgrade.h"
#include "pgrade.h"

using std::vector;

// A single-pass solution to extract the failed students
// (S6.3.2/119)
vector<Student_info> extract_fails(vector<Student_info>& students)
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), pgrade);

  vector<Student_info> fail(iter, students.end());
  students.erase(iter, students.end());

  return fail;
}

The implementation does the following:

Acpp6p7Pic1

 

  1. Process directly an input vector<Student_info> students container. Uses stable_parition to put the passed students to the front of that vector – with the help of its third argument pgrade as a predicate.
  2. Instantiate a vector<Student_info> fail container to include only the failed students. We return this container at the end.
  3. Erase those failed students from the original input vector<Student_info> students container, essentially keeping only the passed students.

The end result is, a new vector<Student_info> fail container that contains only the failed students, and a “reduced” vector<Student_info> students container that now contains only the passed Students.

The new extractDidnt function

Applying the same concept our new extractDidnt function may look like the following.

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if

#include "Student_info.h"
#include "did_all_hw.h"

using std::vector;

// A single-pass solution to extract the students who didn't do all homework
// adjusted version of S6.3.2/119) - for exercise 6-7
vector<Student_info> extractDidnt(vector<Student_info>& students)
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), did_all_hw);

  vector<Student_info> didnt(iter, students.end());
  students.erase(iter, students.end());

  return didnt;
}

The implementation does the following:

Acpp6p7Pic2

 

  1. Process directly an input vector<Student_info> students container. Uses stable_parition to put the “did-all-homework” students to the front of that container – with the help of its third argument did_all_hw as a predicate.
  2. Instantiate a new vector<Student_info> didnt container to include only the “did-not-do-all-homework” students. We return this container at the end.
  3. Erase those “did-not-do-all-homework” students from the original input vector<Student_info> students container, essentially keeping only the passed students.

The end result is, a new vector<Student_info>  didnt container that contains only the “did-not-do-all-homework” students, and a “reduced” vector<Student_info> students container that now contains only the “did-all-homework” Students.

The Project

I now wrap the entire projects here, including all the source and header files used. Note that this project is built on the Project within my Solution to Exercise 6-6. (i.e. I have merely amended the main.cpp file, and added the extractDidnt.cpp file).

Acpp6p7MgntTree

Source File List

Header File List

Source Files

main.cpp

#include <iostream>                      // cin, cout, endl
#include <vector>                        // vector

#include "Student_info.h"                // Student_info
#include "extractDidnt.h"                // extractDidnt
#include "write_analysis.h"              // write_analysis

#include "grade_aux.h"                   // grade_aux
#include "average_grade.h"               // average_grade
#include "optimistic_median.h"           // optimistic_median

using std::cin;
using std::cout;
using std::endl;
using std::vector;

int main()
{
  // read the student records
  Student_info student;
  vector<Student_info> did;       // to store students who did all homework
  while (read(cin, student))
    did.push_back(student);

  // extract out the students who didnt do all homework
  vector<Student_info> didnt = extractDidnt(did);

  // verify that the analyses will show us something
  if (did.empty()) {
    cout << "No student did all the homework!" << endl;
    return 1;
  }
  if (didnt.empty()) {
    cout << "No student did all the homework!" << endl;
    return 1;
  }

  // do the analyses
  write_analysis(cout, "median", grade_aux, did, didnt);
  write_analysis(cout, "average", average_grade, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median, did, didnt);

  return 0;
}

average.cpp

#include <vector>  // vector
#include <numeric>  // numeric

using std::vector;
using std::accumulate;

// Compute average of elements
// (S6.2.3/115)
double average(const vector<double>& v)
{
  return accumulate(v.begin(), v.end(), 0.0) / v.size();
}

average_grade.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include "average.h"  // average

// Compute the final grade using average of homework
// (S6.2.3/115)
double average_grade(const Student_info& s)
{
  return grade(s.midterm, s.final, average(s.homework));
}

did_all_hw.cpp

#include <algorithm>  // find
#include "Student_info.h"  // Student_info

// Has the student done all the homework?
// (S6.2.1/110)
bool did_all_hw(const Student_info& s)
{
  return ((find(s.homework.begin(), s.homework.end(), 0)) == s.homework.end());
}

doAnalysis.cpp

#include <vector>                    // vector
#include <algorithm>                 // transform
#include "Student_info.h"            // Student_info
#include "median.h"                  // median

using std::vector;
using std::transform;

// Exercise 6-6: a consolidated auxiliary function
double doAnalysis(const vector<Student_info>& students,
                  double useGradeScheme(const Student_info&))
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), useGradeScheme);
  return median(grades);
}

extractDidnt.cpp

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if

#include "Student_info.h"
#include "did_all_hw.h"

using std::vector;

// A single-pass solution to extract the students who didn't do all homework
// adjusted version of S6.3.2/119) - for exercise 6-7
vector<Student_info> extractDidnt(vector<Student_info>& students)
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), did_all_hw);

  vector<Student_info> didnt(iter, students.end());
  students.erase(iter, students.end());

  return didnt;
}

grade.cpp

#include <stdexcept>
#include <vector>
#include "grade.h"
#include "median.h"
#include "Student_info.h"

using std::domain_error;
using std::vector;

// definitions for the grade functions from S4.1/52, S4.1.2/54, S4.2.2/63

// compute a student's overall grade from midterm and final exam
// grades and homework grade (S4.1/52)
double grade(double midterm, double final, double homework)
{
    return 0.2 * midterm + 0.4 * final + 0.4 * homework;
}

// compute a student's overall grade from midterm and final exam grades
// and vector of homework grades.
// this function does not copy its argument, because median (function) does it for us.
// (S4.1.2/54)
double grade(double midterm, double final, const vector<double>& hw)
{
    if (hw.size() == 0)
        throw domain_error("student has done no homework");
    return grade(midterm, final, median(hw));
}

// this function computes the final grade for a Student_info object
// (S4.2.2/63)
double grade(const Student_info& s)
{
    return grade(s.midterm, s.final, s.homework);
}

grade_aux.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include <stdexcept>  // domain_error

using std::domain_error;

// Auxiliary function to be parsed as argument to a function
// (S6.2.2/113)
double grade_aux(const Student_info& s)
{
  try {
    return grade(s);
  } catch (domain_error) {
    return grade(s.midterm, s.final, 0);
  }
}

median.cpp

// source file for the median function
#include <algorithm>
#include <stdexcept>
#include <vector>

using std::domain_error;
using std::sort;
using std::vector;

// compute the median of a vector<double>
double median(vector<double> vec)
{
    typedef vector<double>::size_type vec_sz;

    vec_sz size = vec.size();
    if (size == 0)
        throw domain_error("median of an empty vector");

    sort(vec.begin(),vec.end());

    vec_sz mid = size/2;

    return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];
}

optimistic_median.cpp

#include <vector>  // vector
#include <algorithm>  // remove_copy, back_inserter
#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include "median.h"  // median

using std::vector;

// median of the nonzero elements of s.homework, or 0 if no such elements exist
double optimistic_median(const Student_info& s)
{
  vector<double> nonzero;
  remove_copy(s.homework.begin(), s.homework.end(),
              back_inserter(nonzero), 0);
  if (nonzero.empty())
    return grade(s.midterm, s.final, 0);
  else
    return grade(s.midterm, s.final, median(nonzero));
}

Student_info.cpp

#include "Student_info.h"

using std::istream;
using std::vector;

// we are interested in sorting the Student_info object by the student's name
bool compare(const Student_info& x, const Student_info& y)
{
    return x.name < y.name;
}

// read student's name, midterm exam grade, final exam grade, and homework grades
// and store into the Student_info object
// (as defined in S4.2.2/62)
istream& read(istream& is, Student_info& s)
{
    // read and store the student's name and midterm and final exam grades
    is >> s.name >> s.midterm >> s.final;

    // read and store all the student's homework grades
    read_hw(is, s.homework);
    return is;
}

// read homework grades from an input stream into a vector<double>
// (as defined in S4.1.3/57)
istream& read_hw(istream& in, vector<double>& hw)
{
    if (in)
    {
        // get rid of previous contents
        hw.clear();

        // read homework grades
        double x;
        while (in >> x)
            hw.push_back(x);

        // clear the stream so that input will work for the next student
        in.clear();
    }
    return in;
}

write_analysis.cpp

#include <iostream>         // ostream, endl;
#include <vector>           // vector
#include <string>           // string
#include "Student_info.h"   // Student_info
#include "doAnalysis.h"     // doAnalysis

using std::ostream;
using std::endl;
using std::string;
using std::vector;

// Output result to compare the two groups of students who did and
// who didn't do all of their homework.
// (S6.2.3/113) | updated for Exercise 6-6
void write_analysis(ostream& out,
                    const string& name,
                    double useGradeScheme(const Student_info&),
                    const vector<Student_info>& did,
                    const vector<Student_info>& didnt)
{
  out << name << ": median(did) = " << doAnalysis(did, useGradeScheme) <<
                 ": median(didnt) = " << doAnalysis(didnt, useGradeScheme) <<
                 endl;
  return;
}

Header Files

average.h

#ifndef GUARD_AVERAGE_H
#define GUARD_AVERAGE_H

// average.h
#include <vector>

double average(const std::vector<double>&);

#endif // GUARD_AVERAGE_H

average_grade.h

#ifndef GUARD_AVERAGE_GRADE_H
#define GUARD_AVERAGE_GRADE_H

// average_grade.h
#include "Student_info.h"  // Student_info

double average_grade(const Student_info&);

#endif // GUARD_AVERAGE_GRADE_H

did_all_hw.h

#ifndef GUARD_DID_ALL_HW_H
#define GUARD_DID_ALL_HW_H

// did_all_hw.h
#include "Student_info.h"  // Student_info

bool did_all_hw(const Student_info&);

#endif // GUARD_DID_ALL_HW_H

doAnalysis.h

#ifndef GUARD_DOANALYSIS_H
#define GUARD_DOANALYSIS_H

#include <vector>
#include "Student_info.h"

double doAnalysis(const std::vector<Student_info>&,
                  double useGradeScheme(const Student_info&));

#endif // GUARD_DOANALYSIS_H

extractDidnt.h

#ifndef GUARD_EXTRACTDIDNT_H
#define GUARD_EXTRACTDIDNT_H

#include <vector>            // vector
#include "Student_info.h"    // Student_info

std::vector<Student_info> extractDidnt(std::vector<Student_info>&);

#endif // GUARD_EXTRACTDIDNT_H

grade.h

#ifndef GUARD_GRADE_H
#define GUARD_GRADE_H

// grade.h
#include <vector>
#include "Student_info.h"

double grade(double, double, double);
double grade(double, double, const std::vector<double>&);
double grade(const Student_info&);

#endif // GUARD_GRADE_H

grade_aux.h

#ifndef GUARD_GRADE_AUX_H
#define GUARD_GRADE_AUX_H

// grade_aux.h
#include "Student_info.h"  // Student_info

double grade_aux(const Student_info&);

#endif // GUARD_GRADE_AUX_H

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

// median.h
#include <vector>
double median(std::vector<double>);

#endif // GUARD_MEDIAN_H

optimistic_median.h

#ifndef GUARD_OPTIMISTIC_MEDIAN_H
#define GUARD_OPTIMISTIC_MEDIAN_H

// optimistic_median.h

#include "Student_info.h"  // Student_info

double optimistic_median(const Student_info&);

#endif // GUARD_OPTIMISTIC_MEDIAN_H

Student_info.h

#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

// Student_info.h
#include <iostream>
#include <string>
#include <vector>

struct Student_info
{
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};

bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);

#endif // GUARD_STUDENT_INFO_H

write_analysis.h

#include <iostream>  // ostream;
#include <vector>  // vector
#include <string>  // string
#include "Student_info.h"  // Student_info

void write_analysis(std::ostream&,
                    const std::string&,
                    double useGradeScheme(const Student_info&),
                    const std::vector<Student_info>&,
                    const std::vector<Student_info>&);

#endif // GUARD_WRITE_ANALYSIS_H

Test Program

I now submit the same input (as the test to the original program / Solution to Exercise 6-0 (Part 5 / 7)). The test shows that we get the same result, implying the code updates are not causing observable issues.

pete 100 100 100 100 100
jon 90 90 0 0 0
mary 50 50 50 50 50
anna 40 40 0 0 0
gary 80 80 0 80 0
bob 100 100 100 0 0
ken 20 88 99 44 66
jay 99 39 40 80 0
bill 20 88 0 39 0
^Z
^Z
median: median(did) = 65.6: median(didnt) = 49.7
average: median(did) = 67.0667: median(didnt) = 52.7
median of homework turned in: median(did) = 65.6: median(didnt) = 57.1

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000

Leave a reply