Exercise 6-8

Write a single function that can be used to classify students based on criteria of your choice. Test this function by using it in place of the extract_fails program, and use it in the program to analyse student grades.

Some Background

In the Solution to Exercise 6-7 we created a new extractDidnt function by making a copy of the original “one-pass” extract_fails function, followed by making minor adjustments (such as replacing the predicate pgrade to did_all_hw). The downside of this approach (i.e. making a copy of a skeleton code and adjusting it) is that we may end up with many near-duplicated codes (with only minor differences). Having to maintain so many codes may become difficult to manage in long run. The author asks us to create a single (more generic) function that is capable to deal with multiple similar scenarios – so at the end of the day we only need to maintain 1 single piece of code, instead of (say) a hundred.

Solution

If we look at the extract_fail and extractDidnt codes that we wrote in Solution to Exercise 6-7, we note that the one most important difference is third argument called by the stable_partition function – pgrade vs did_all_hw (which are both predicates). Both of these are essentially some sort of criteria that return true or false.

The new extractOnCriteria function

Building on the skeleton extract_fail function, this is my version of that “one single (more generic)” function:

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if
#include "Student_info.h"     // Student_info

using std::vector;

// a more generic version of extract_fail code (originated (S6.3.2/119))
vector<Student_info> extractOnCriteria(vector<Student_info>& students,
                                       bool criteria(const Student_info&))
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), criteria);

  vector<Student_info> extracted(students.begin(), iter);  // changed
  students.erase(students.begin(), iter);                  // changed

  return extracted;
}

This diagram summarises what this implementation does:

Note these adjustments:

• The third argument (a predicate) is now renamed to something more generic – criteria.
• Added a second parameter bool criteria(const Student_info&) to enable us to parse the criteria into the implementation. For example, when we call the extractOncriteria from the main program, we can parse either the pgrade or did_all_hw via the second argument.
• The two lines above the return statement – note that the range is now from students.begin() to iter – instead of iter to students.end() as per the extract_fail function. (Why you may ask? Well, instead of trying to convince you, I would suggest you to just simply compare the above diagram with the ones in Solution to Exercise 6-7 – things will become clear then.)

The Project

Just to wrap things up and enable ease of testing, I now summarise the C++ source and header files here.

Source File List

• main.cpp
• did_all_hw.cpp
• extractOnCriteria.cpp
• fgrade.cpp
• grade.cpp
• median.cpp
• Student_info.cpp

Header File List

• did_all_hw.h
• extractOnCriteria.h
• fgrade.h
• grade.h
• median.h
• Student_info.h

Source Files

main.cpp

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

#include "Student_info.h"                // Student_info

#include "extractOnCriteria.h"           // extractOnCriteria

#include "did_all_hw.h"                  // did_all_hw
#include "fgrade.h"                      // fgrade

#include "grade.h"                       // grade

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

int main()
{
  // read the student records
  Student_info student;
  vector<Student_info> students;
  while (read(cin, student))
    students.push_back(student);

  // identify students who did and didnt do all homework
  vector<Student_info> didnt = students;
  vector<Student_info> did = extractOnCriteria(didnt, did_all_hw);

  cout << "nThese students did all homework:" << endl;
  for (vector<Student_info>::const_iterator i = did.begin();
       i != did.end(); ++i)
    cout << (i->name) << endl;

  cout << "nThese students didn't do all homework:" << endl;
  for (vector<Student_info>::const_iterator i = didnt.begin();
       i != didnt.end(); ++i)
    cout << (i->name) << endl;


  // identify students who have passed or failed
  vector<Student_info> passed = students;
  vector<Student_info> failed = extractOnCriteria(passed, fgrade);

  cout << "nThese students have passed:" << endl;
  for (vector<Student_info>::const_iterator i = passed.begin();
       i != passed.end(); ++i)
    cout << (i->name) << " (" << grade(*i) << ")" << endl;

  cout << "nThese students have failed:" << endl;
  for (vector<Student_info>::const_iterator i = failed.begin();
       i != failed.end(); ++i)
    cout << (i->name) << " (" << grade(*i) << ")" << endl;

  return 0;
}

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());
}

extractOnCriteria.cpp

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if
#include "Student_info.h"     // Student_info

using std::vector;

// a more generic version of extract_fail code (originated (S6.3.2/119))
vector<Student_info> extractOnCriteria(vector<Student_info>& students,
                                       bool criteria(const Student_info&))
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), criteria);

  vector<Student_info> extracted(students.begin(), iter);  // changed
  students.erase(students.begin(), iter);                  // changed

  return extracted;
}

fgrade.cpp

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

// predicate to determine whether a student failed
// (S5.1/75)
bool fgrade(const Student_info& s)
{
    return grade(s) < 60;
}

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);
}

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];
}

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;
}

header Files

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

extractOnCriteria.h

#ifndef GUARD_EXTRACTONCRITERIA_H
#define GUARD_EXTRACTONCRITERIA_H

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

std::vector<Student_info>
extractOnCriteria(std::vector<Student_info>&,
                  bool criteria(const Student_info&));

#endif // GUARD_EXTRACTONCRITERIA_H

fgrade.h

#define GUARD_FGRADE_H

// fgrade.h

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

bool fgrade(const Student_info&);

#endif // GUARD_FGRADE_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

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

#endif // GUARD_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

Test Program

As we see in the main program, we are going to use the extractOnCriteria twice – once against the fgrade predicate (to extract failed students), and once against the did_all_hw (to extract students who did all homework). We then display to confirm that the single extractOnCriteria function works! (and it does indeed).

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

These students did all homework:
pete
mary
ken

These students didn't do all homework:
jon
anna
gary
bob
jay
bill

These students have passed:
pete (100)
bob (60)
ken (65.6)

These students have failed:
jon (54)
mary (50)
anna (24)
gary (48)
jay (51.4)
bill (39.2)

Reference

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

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:

 

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:

 

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).

Source File List

• main.cpp
• average.cpp
• average_grade.cpp
• did_all_hw.cpp
• doAnalysis.cpp
• extractDidnt.cpp
• grade.cpp
• grade_aux.cpp
• median.cpp
• optimistic_median.cpp
• Student_info.cpp
• write_analysis.cpp

Header File List

• average.h
• average_grade.h
• did_all_hw.h
• doAnalysis.h
• extractDidnt.h
• grade.h
• grade_aux.h
• median.h
• optimistic_median.h
• Student_info.h
• write_analysis.h

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

Exercise 6-6

Note that the function from the previous exercise and the function from S6.2.2/113 and 6.2.3/115 do the same task. Merge these three analysis functions into a single function.

Some Background

This is regarding the “Compare Grading Scheme” sample codes as presented in chapter 6 of the book. The original codes may be found at Solution to Exercise 6-0 (Part 5 / 7).

One disclosure: though I eventually managed to complete this exercise and adjust all the codes, following a combination of trial-and-error (and a bit of Google-ing!), I have found it not an easy task to explain the solution to this entire problem – in some way I do find the idea of parsing a function as an argument to another function pretty abstract (and I believe things will only get better only after I have completed more C++ exercises and read on more.). For now, I shall do my best to explain my solution based on my understanding, which I hope will make sense! Please do forgive me if you ended up finding the following quite difficult to follow. I do wish I know a more systematic and simplified way to explain this solution! If you are not put off by this, read on!

Some Observations

OK. If you have also had a go running through the entirety of the “Compare Grading Scheme” project, you would likely have noticed that we have 3 very similar functions:

• average_analysis
• median_analysis
• optimistic_median_analysis

I shall recall these 3 functions below – note that they are pretty much identical, apart from the 4th argument of the transform function which corresponds to the associating grading scheme, respectively:

• average_grade
• grade_aux
• optimistic_median

average_analysis:

double average_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), average_grade);
  return median(grades);
}

median_analysis:

double median_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(), back_inserter(grades), grade_aux);
  return median(grades);
}

optimistic_median_analysis:

double optimistic_median_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), optimistic_median);
  return median(grades);
}

Opportunity to merge these 3 functions into one? Oh yes definitely!

Merging the three Analysis Functions into one

We note that the 3 functions are pretty much identical, apart from the 4th argument called by the transform function which corresponds to the associating grading scheme.

To merge the three functions into one, simply follow this strategy:

1. Make a copy of one of the analysis function (say, the median_analysis function) and use it as our new baseline for building up the new “merged” function. Rename the function to something that sounds more generic. Let’s rename it to doAnalysis.
2. Within the now doAnalysis function, rename that 4th argument called by the transform function with a more generic name. Let’s rename it to useGradeScheme. i.e. we use this as an “adaptor” for the 3 grading schemes (average_grade, grade_aux, and optimistic_median).
3. Add a second parameter useGradeScheme to the doAnalysis function so we can parse the grade scheme into the doAnalysis implementation itself. We need to ensure this parameter takes the same form as grade_aux (which has the same form as average_grade, which also has the same form as optimistic_median). i.e. they all take this form: double XXXX(const Student_info&). To make things consistent, this new second parameter must also be of the same form. i.e. the second parameter shall be written as double useGradeScheme(const Student_info&).

I summarise this strategy into a picture (which I hope will make it easier to understand).

Once we have completed the change, the new “merged” doAnalysis function shall look like this.

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);
}

Update the functions that are still calling the legacy analysis functions

Now that we have merged the 3 analysis functions into 1 new “merged” functions, we need to ensure all the whatever implementations that are still calling these 3 analysis functions (average_analysis, median_analysis, and optimistic_median_analysis) are also adjusted to use the new “merged” function. Otherwise those implementations would bump into errors as the 3 legacy analysis functions no longer exist! Our next task is therefore to identify the impacted implementations and make changes accordingly.

Fortunately, there is only one implementation impacted – the main function. The main function contains the following 3 lines, which still calls the legacy analysis functions (average_analysis, median_analysis, and optimistic_median_analysis) – as an argument to the function write_analysis.

  write_analysis(cout, "median", median_analysis, did, didnt);
  write_analysis(cout, "average", average_analysis, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median_analysis, did, didnt);

Because these analysis functions are used as an argument (which in this case, the 3rd argument) to another function, we must pay attention to that “another function” – write_analysis as we will likely need to adjust that as well.  So let’s take a look at the write_analysis function:

void write_analysis(ostream& out,
                    const string& name,
                    double analysis(const vector<Student_info>&),
                    const vector<Student_info>& did,
                    const vector<Student_info>& didnt)
{
  out << name << ": median(did) = " << analysis(did) <<
                 ": median(didnt) = " << analysis(didnt) << endl;
  return;
}

We know that the 3rd parameter double analysis(const vector<Student_info>&) corresponds to the legacy analysis function. When, say, median_analysis (as an argument) is parsed into this implementation (via this 3rd parameter) all the downstream analysis(XXX) within this implementation essentially get resolved into median_analysis(XXX). (likewise for the other two analysis functions).

As we have already mentioned, the median_analysis function shall be replaced by the new “merged” function called doAnalysis, which take this new form:

double doAnalysis(const vector<Student_info>& students,
                  double useGradeScheme(const Student_info&))

We must therefore adjust the analysis(XXX) accordingly to doAnalysis(XXX, XXX). i.e. we can replace the following:

  out << name << ": median(did) = " << analysis(did) <<
                 ": median(didnt) = " << analysis(didnt) << endl;

… with …

  out << name << ": median(did) = " << doAnalysis(did, useGradeScheme) <<
                 ": median(didnt) = " << doAnalysis(didnt, useGradeScheme) << endl;

We can declare the doAnalysis by simply doing a #include of the corresponding file.

For the useGradeScheme part however, we must parse it via the parameter. One way to do this is to replace the double analysis(const vector<Student_info>&), which we no longer need, to double useGradeScheme(const Student_info&), which we now need. I summarise this via a diagram below:

i.e. the now revised write_analysis function will look like this:

#include "doAnalysis.h"     // doAnalysis

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;
}

Now that we have updated the write_analysis function, the logical next step is to update whatever implementation that call this write_analysis function, and adjust accordingly.

Let’s go back to the main function and look at the 3 lines again:

  write_analysis(cout, "median", median_analysis, did, didnt);
  write_analysis(cout, "average", average_analysis, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median_analysis, did, didnt);

We know from our new write_analysis function above, that the 3rd parameter is of the form double useGradeScheme(const Student_info&). It is therefore logical to parse an argumenet that satisfy this form. And we know that the useGradeScheme correspond to: average_grade, grade_aux, and optimistic_median. So, let’s do the replacement accordingly – I summarise this via a diagram.

The revised 3 lines in the main function will now look like this:

  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);

That’s pretty much all the changes required to solve this problem! (As I mentioned at the top of the post, I do find explaining the solution to this exercise not an easy task – if you still do not understand, I would recommend you to try compiling the files in the Project section below, run the program, test it out, confirm that it works, and try to understand how and why it has worked.

To see the complete project / source files, read on and try out!

The Project

To wrap things up, as usual, I shall publish my entire project here, including the source files and header files.

Source File List

• main.cpp
• average.cpp
• average_grade.cpp
• did_all_hw.cpp
• doAnalysis.cpp
• grade.cpp
• grade_aux.cpp
• median.cpp
• optimistic_median.cpp
• Student_info.cpp
• write_analysis.cpp

Header File List

• average.h
• average_grade.h
• did_all_hw.h
• doAnalysis.h
• grade.h
• grade_aux.h
• median.h
• optimistic_median.h
• Student_info.h
• write_analysis.h

Source Files

main.cpp

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

#include "Student_info.h"                // Student_info
#include "did_all_hw.h"                  // did_all_hw
#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;

// Compare the Grading Scheme
// (S6.2.3/114)
int main()
{
  // students who did and didn't do all their homework
  vector<Student_info> did, didnt;

  // read the student records and partition them
  Student_info student;
  while (read(cin, student)) {
    if (did_all_hw(student))
      did.push_back(student);
    else
      didnt.push_back(student);
  }

  // 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);
}

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

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

#ifndef GUARD_WRITE_ANALYSIS_H
#define GUARD_WRITE_ANALYSIS_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

Exercise 6-5

Write an analysis function to call optimistic_median.

Solution

This is covered under my Solution to Exercise 6-0 (Part 5 / 7). The analysis function is called optimistic_median_analysis (stored in the source file optimistic_median_analysis.cpp). It essentially parses the (pointer or memory address of the) optimistic_median function as an argument to another (transform) function. For this to work the optimistic_median function must not be overloaded.

Reference

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

Exercise 6-4

Correct the program you wrote in the previous exercise to copy from u into v. There are at leaset two possible ways to correct the program. Implement both, and describe the relative advantages and disadvantages of each approach.

Solution

In the previous exercise (See my Solution to Exercise 6-3), it contains the following statement which will crash the system due to attempt to copy additional elements to an empty vector without dynamically growing the vector size up-front (with the like of back_inserter or inserter).

copy(u.begin(), u.end(), v.begin());

As we have already mentioned, we can fix this by using back_inserter or inserter to grow the vector size dynamically.

copy with back_inserter

copy(u.begin(), u.end(), back_inserter(v));

copy with inserter

copy(u.begin(), u.end(), inserter(v, v.begin()));

back_inserter vs inserter

This table summarises my “educational guess” regarding relative advantages and disadvantages of back_inserter and inserter in the context of being used within the copy function.

	back_inserter	inserter
Advantages	Relatively faster element appending (to the back of the base vector) as this is what it is designed to do.	capable of inserting elements at the beginning or middle of the base vector.
Disadvantages	Not capable of inserting elements at the beginning or middle of the base vector.	Relatively slower element appending (to the back of the base vector) as it is designed for flexibility over performance.

The Project

We can perform a test by submitting the following program.

main.cpp

#include <iostream>     // cout, endl
#include <vector>       // vector
#include <algorithm>    // copy

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

int main()
{
  vector<int> u(10, 100);

  cout << "vector<int> u looks like this:" << endl;
  for (vector<int>::const_iterator i = u.begin(); i != u.end(); ++i)
    cout << (*i) << endl;

  vector<int> v1;
  copy(u.begin(), u.end(), back_inserter(v1));  // use back_inserter to grow v

  cout << "vector<int> v1 looks like this (back_inserter):" << endl;
  for (vector<int>::const_iterator i = v1.begin(); i != v1.end(); ++i)
    cout << (*i) << endl;

  vector<int> v2;
  copy(u.begin(), u.end(), inserter(v2, v2.begin())); // use inserter to grow v2

  cout << "vector<int> v2 looks like this (inserter):" << endl;
  for (vector<int>::const_iterator i = v2.begin(); i != v2.end(); ++i)
    cout << (*i) << endl;
  return 0;
}

Test Program

Submitting the Revised Program gives us the following, which is as expected (and resolved the system crash issue discovered in previous exercise).

vector<int> u looks like this:
100
100
100
100
100
100
100
100
100
100
vector<int> v1 looks like this (back_inserter):
100
100
100
100
100
100
100
100
100
100
vector<int> v2 looks like this (inserter):
100
100
100
100
100
100
100
100
100
100

Reference

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

Exercise 6-3

What does this program fragment do?

vector<int> u(10, 100)
vector<int> v;
copy(u.begin(), u.end(), v.begin());

Solution

Let’s look at the 3 lines one-by-one.

The First Line

Starting with the first line:

vector<int> u(10, 100);

This statement creates a vector<int> container named u. It allocates system memory and give the container a size of 10 as defined by the first argument (i.e. having the ability to store 10 int elements), and immediately create 10 int elements each has an initial value of 100, as defined by the second argument. i.e. We expect u to contains 10 int elements, each has a value of 100.

I can test this out easily via a simple program like this:

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

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

int main()
{
  vector<int> u(10, 100);

  for (vector<int>::const_iterator i = u.begin(); i != u.end(); ++i)
    cout << (*i) << endl;

  return 0;
}

Running this program gives the followings as expected.

100
100
100
100
100
100
100
100
100
100

Note that if I change the statement slightly to instead:

vector<int> u(10);

This statement would create 10 elements for u with the default initial value of 0 (determined by the <int> part).

The Second Line

This second line is very easy:

vector<int> v;

This statement creates a vector<int> container v with no elements (and a size of zero).

The Third Line

Now the third line:

copy(u.begin(), u.end(), v.begin());

Though at first sight this statement appears to copy all the elements from the vector<int> container u, to the beginning of the empty vector<int> container v, this line will crash the program. Why? Because v initially has zero elements and has a container size of zero. In order to copy additional elements to this empty container v, we must first have a means to grow the container size dynamically by using utilities like back_inserter or inserter (page 121 of the book). In fact, in the next Exercise we shall correct this program using these utilities.

For now, let me illustrate that running the following program as it is will indeed crash the system:

#include <iostream>     // cout, endl
#include <vector>       // vector
#include <algorithm>    // copy

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

int main()
{
  vector<int> u(10, 100);

  cout << "vector<int> u looks like this:" << endl;
  for (vector<int>::const_iterator i = u.begin(); i != u.end(); ++i)
    cout << (*i) << endl;

  vector<int> v;
  //copy(u.begin(), u.end(), v.begin());  // program crashes!

  cout << "vector<int> v looks like this:" << endl;
  for (vector<int>::const_iterator i = v.begin(); i != v.end(); ++i)
    cout << (*i) << endl;

  return 0;
}

Program crashes! (on my Vista system it gives a return code of -1073741819 (0xC0000005) )

Conclusion

This exercises illustrates that in order for the copy function to work, we must have a means to grow the vector dynamically, such as using the utilities back_inserter or inserter, as we shall see in my Solution to Exercise 6-4.

Reference

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

Exercise 6-2

Write a program to test the find_urls function.

Solution

This is covered under my Solution to Exercise 6-0 (Part 4 / 7).

Reference

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

Exercise 6-1

Reimplement the frame and hcat operations from S5.8.1/93 and $5.8.3/94 to use iterators.

Solution

The ask for this exercise is to reimplement the frame.cpp and hcat.cpp (as seen in Chapter 5 / my Solution to Exercise 5-0 (Part 3/3)), from index-base access iterator-base access.

I personally think this is a very good exercise to enable us to practice a bit on accessing vector elements by either index or iterator. This is summarised by the diagram below:

Bearing this in mind, it is in fact not that difficult, to convert frame and hcat operations from using index to iterators.

The Project

All the source and header files are essentially the same as my Solution to Exercise 5-0 (Part 3/3). In this exercise we, however, amend the frame.cpp and hcat.cpp to use iterator (instead of using index). I have also updated the main.cpp to enable us to test out the change easily. (i.e. use the Project structure as per Exercise 5-0 (Part 3/3) but use the new main.cpp, frame.cpp, and hcat.cpp. Then run the program to test.

Source File List (Newly re-written)

• main.cpp
• frame.cpp
• hcat.cpp

Source Files (Newly re-written)

main.cpp

#include <iostream>  // cin, cout, endl, getline
#include <vector>    // vector
#include <string>    // string
#include "frame.h"   // frame
#include "hcat.h"    // hcat
#include "vcout.h"   // vcout

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

int main()
{
    string s;            // line
    vector<string> p;    // paragraph

    // read multiple lines to make a paragraph
    while (getline(cin, s))
        p.push_back(s);

    // have a play, manipulate and display paragraph (p) in multiple ways

    cout << "-----------------------------------------------------\n"
            "Display: hcat(p, frame(p))                           \n"
            "-----------------------------------------------------\n";
    vcout(hcat(p,frame(p)));

    cout << "-----------------------------------------------------\n"
            "Display: hcat(frame(p), p)                           \n"
            "-----------------------------------------------------\n";
    vcout(hcat(frame(p),p));


    return 0;
}

frame.cpp

#include <string>      // string
#include <vector>      // vector
#include <algorithm>   // max

using std::string;
using std::vector;
using std::max;

string::size_type width(const vector<string>& v)
{
    string::size_type maxlen = 0;
    for(vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
        maxlen = max(maxlen, i->size());
    return maxlen;
}

vector<string> frame(const vector<string>& v)
{
    vector<string> ret;
    string::size_type maxlen = width(v);
    string border(maxlen + 4, '*');

    // write the top border
    ret.push_back(border);

    // write each interior row, bordered by an asterisk and a space
    for (vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
        ret.push_back("* " + (*i) + string(maxlen - i->size(), ' ') + " *");

    // write the bottom border
    ret.push_back(border);

    return ret;
}

hcat.cpp

#include <string>      // string
#include <vector>      // vector
#include "frame.h"     // width

using std::string;
using std::vector;

vector<string> hcat(const vector<string>& left, const vector<string>& right)
{
    vector<string> ret;

    // add 1 to leave a space between pictures
    string::size_type width1 = width(left) + 1;

    // indices to look at elements from left and right respectively
    vector<string>::const_iterator i = left.begin();
    vector<string>::const_iterator j = right.begin();

    // continue until we've seen all rows from both pictures
    while (i != left.end() || j != right.end())
    {
        // construct new string to hold characters from both pictures
        string s;

        // copy a row from the left-hand side, if there is one
        if (i != left.end())
            s = *(i++);

        // pad to full width
        s += string(width1 - s.size(), ' ');

        // copy a row from teh right-hand side, if there is one
        if (j != right.end())
            s += *(j++);

        // add s to the picture we are creating
        ret.push_back(s);
    }

    return ret;
}

Test Program

Running the program gives us the output as expected. This effectively demonstrates that, if the code is written correctly, there is virtually no difference between accessing vector elements by index or by iterators.

Hello world
how are
we today?
^Z
-----------------------------------------------------
Display: hcat(p, frame(p))
-----------------------------------------------------
Hello world ***************
how are     * Hello world *
we today?   * how are     *
            * we today?   *
            ***************
-----------------------------------------------------
Display: hcat(frame(p), p)
-----------------------------------------------------
*************** Hello world
* Hello world * how are
* how are     * we today?
* we today?   *
***************

Reference

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

Exercise 6-0

Compile, execute, and test the programs in this chapter.

Solution

In Chapter 6 of the textbook there are 7 core concepts / programs introduced. For ease of documentation I shall dice this up into 7 parts as followings – simply click the hyperlink to drill down to see the post corresponding to the particular part.

Exercise 6-0 (Part 1 / 7): Relating to section 6.1 of the textbook (page 101-103). There are many ways to append elements from container B to container A (the base). In this post I shall implement and test out 3 known ways to do this: (1) pusb_back method, (2) insert method, and (3) copy method. The test confirms that all 3 methods produce the same results.

Exercise 6-0 (Part 2 / 7): Relating to section 6.1.1 of the textbook (page 103-105). Implement and test out an alternative way to split a line into words using the find_if utility from the <algorithm> directive. The original split function method was first introduced in S5.6/88 of the book.

Exercise 6-0 (Part 3 / 7): Relating to section 6.1.2 of the textbook (page 105). Implement and test out the home-made isPalindrome function (created using the equal utility). Note that this is a more neat / compact version to the created in my previous Solution to Exercise 5-10.

Exercise 6-0 (Part 4 / 7): Relating to section 6.1.3 of the textbook (page 105-109). Implement and test out the “Finding URLs” program. The program scans a line of input text, and automatically detect and display all the URL addresses within that line of text.

Exercise 6-0 (Part 5 / 7): Relating to section 6.2 of the textbook (page 110-116). Implement and test out the “Comparing Grading Schemes” program. This program reads in a set of student’s grades (from mid-term exam, final exam, and individual homework grades), compute the student’s final grades using the 3 grading schemes (median homework, average homework, and optimistic-median homework), split the students into two groups (did and didn’t do all homework), and for each group compute the group medians associating with the grading schemes. i.e. the end result consists of 6 total grades: medians computed using the 3 schemes for group A (students who did all homework), and medians computed using the 3 schemes for group B (students who didn’t do all homework). The exercise introduces one key idea: parsing a function as an argument to another function. From Chapter 10 we shall see this is actually facilitated by the “hidden” pointer and array mechanism.

Exercise 6-0 (Part 6 / 7): Relating to section 6.3.1 of the textbook (page 117-118). Implement and test out the “two-pass extract_fails” program. This program essentially split the students into two groups – failed and passed students. This version of extract_fails function uses remove_copy_if and erase from the <algorithm> directive. (Note that the original version of extract_fails function was first introduced in Chapter 5 / my Solution to Exercise 5-0.

Exercise 6-0 (Part 7 / 7): Relating to section 6.3.2 of the textbook (page 119-120). Building on the previous exercise the author introduces an even better “one-pass extract_fails” program which takes half the time to run in comparison to the “two-pass” version. This version of extract_fails function uses the stable_partition and erase from the <algorithm> directive.

Reference

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

This is Part 7 of the 7-part Exercise 6-0. Click here to see the other parts.

Exercise 6-0 (Part 7 / 7)

Relating to section 6.3.2 of the textbook (page 119-120). Building on the previous exercise the author introduces an even better “one-pass extract_fails” program which takes half the time to run in comparison to the “two-pass” version. This version of extract_fails function uses the stable_partition and erase from the <algorithm> directive.

The Project

Note that the project for this exercise is exactly the same as the one shown in my Solution to Exercise 6-0 (Part 6 / 7). Except for one file as follows:

extract_fails.cpp

#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;
}

Test Program

Using the same set of student grades as per Exercise 6-0 (Part 6 / 7), the result is the same as expected.

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
These students have passed.
bob (60)
ken (65.6)
pete (100)
These students have failed.
anna (24)
bill (39.2)
gary (48)
jay (51.4)
jon (54)
mary (50)

Reference

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