Accelerated C++ Solution to Exercise 5-3

Exercise 5-3

By using a typedef, we can write one version of the program that implements either a vector-based solution or a list-based on. Write and test this version of the program.

Solution

To do this, I have essentially re-engineered the Chapter 5 program / my Solution to Exercise 5-0 (Part 1/3). The following outlines the change:

  1. I have replaced the old extract_fails.cpp (that contains the four extract_fail functions with different names – v1/v2/v3/v4), with two partitioned files, namely extract_fails_v3.cpp, and extract_fails_v4.cpp. The corresponding headers are also split – i.e. I now have extract_fails_v3.h and extract_fails.v4.h. Splitting the file into two files enable me to have two functions both called the same name. i.e. extract_fail(). The idea is that, when it comes to writing the main() program, I can #include either the v3 or v4 header file – I only include one of these functions at a time.
  2. I moved the bool fgrade() function to the grade.cpp file, and declared in the corresponding grade.h header file. This is to enable me to do that file splitting as mentioned above.
  3. Generalise the main() program so that I can switch between running the vector-based (v3) list-based (v4) functions easily. Only two line changes are required at the main() program level – i.e. (1) the #include line, and (2) the typedef line. I have highlighted this in the main program.
  4. Remove the sort part in the main program. Note that because the syntax for the algorithm sort is different between vector and list, I have to exclude the sorting part here for simplicity. (Based on a number of internet forum, apparently the Author wanted to use this exercise to demonstrate the needs of C++ templates, which will be taught in later chapters).
  5. Also for simplicity, I shall remove the bits about formatting (e.g. padding the Student’s name for fix-wdith outlook). I shall also exclude the try / catch / throw bits in the main program for better readability.

The Project

Because so much re-engineering has been done, I shall summarise the now re-engineered files here. I have learnt also a bit more about the use of header files and #include directives – i.e. a good combination usage of the two enable us to include only what we need for the particular file / program – so we don’t have ambiguity.

Acpp5p3MgntTree

main.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "Student_info.h"
#include "grade.h"

// ********************** AMEND THIS  *************************
// Solution to Exercise 5-3: Pick one of the followings (v3 or v4)
// #include "extract_fails_v3.h"      // vector<Student_info>
#include "extract_fails_v4.h"      // list<Student_info>
// ************************************************************

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::string;
using std::vector;
using std::list;

int main()
{

    // ********************* AMEND THIS ***************************
    // Solution to Exercise 5-3: Pick one of the followings
    //typedef vector<Student_info> Student_group;
    typedef list<Student_info> Student_group;
    // ************************************************************

    Student_group students;
    Student_info record;

    // read and store all the student's data.
    while (read(cin, record))
        students.push_back(record);

    // Extract the failed students
    Student_group students_failed = extract_fails(students);

    // sort vector and sort list are different
    // so we remove from here for now.

    cout << endl;

    // Report passing students
    cout << "These students have passed." << endl;
    for (Student_group::const_iterator iter = students.begin();
         iter != students.end(); ++iter)
        cout << iter->name << " (" << grade(*iter) << ")" << endl;

    cout << endl;

    // Report failing students
    cout << "These students have failed." << endl;
    for (Student_group::const_iterator iter = students_failed.begin();
         iter != students_failed.end(); ++iter)
        cout << iter->name << " (" << grade(*iter) << ")" << endl;

    return 0;
}

extract_fails_v3.h

#ifndef GUARD_EXTRACT_FAILS_V3_H
#define GUARD_EXTRACT_FAILS_V3_H

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

std::vector<Student_info> extract_fails(std::vector<Student_info>& students);

#endif // GUARD_EXTRACT_FAILS_V3_H

extract_fails_v3.cpp

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

using std::vector;

// separate passing and failing student records
// version 3: iterators but no indexing; still potentially slow
// (S5.3/82)
vector<Student_info> extract_fails(vector<Student_info>& students)
{
    vector<Student_info> fail;
    vector<Student_info>::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

extract_fails_v4.h

#ifndef GUARD_EXTRACT_FAILS_V4_H
#define GUARD_EXTRACT_FAILS_V4_H

// extract_fails_v4.h
#include <list>
#include "Student_info.h"

std::list<Student_info> extract_fails(std::list<Student_info>& students);

#endif // GUARD_EXTRACT_FAILS_V4_H

extract_fails_v4.cpp

#include "Student_info.h"
#include "grade.h"
#include <list>

using std::list;

// separate passing and failing student records
// version 4: use list instead of vector (essentially the same as version 3 otherwise)
// (S5.5/85)
list<Student_info> extract_fails(list<Student_info>& students)
{
    list<Student_info> fail;
    list<Student_info>::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

grade.h

#include "Student_info.h"
#include "grade.h"
#include <list>

using std::list;

// separate passing and failing student records
// version 4: use list instead of vector (essentially the same as version 3 otherwise)
// (S5.5/85)
list<Student_info> extract_fails(list<Student_info>& students)
{
    list<Student_info> fail;
    list<Student_info>::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

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

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

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

#endif // GUARD_MEDIAN_H

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

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

Test Program and Results

For all tests below (vector based and list based) I shall supply this set of 10 lines student’s info as the input.

Kate 88.88 88.88 88.88 88.88 88.88
John 55.55 55.55 55.55 55.55 55.55
Pat 66.66 66.66 66.66 66.66 66.66
Joe 100.00 100.00 100.00 100.00 100.00
Mary 11.11 11.11 11.11 11.11 11.11
Bill 33.33 33.33 33.33 33.33 33.33
Jay 22.22 22.22 22.22 22.22 22.22
Bob 4.00 4.00 4.00 4.00 4.00
Fred 77.77 77.77 77.77 77.77 77.77
Louis 44.44 44.44 44.44 44.44 44.44

We shall see that both tests yield the same result.

Test 1 – vector based version

Amend the #include line and the typdef line accordingly.

// ********************** AMEND THIS  *************************
// Solution to Exercise 5-3: Pick one of the followings (v3 or v4)
#include "extract_fails_v3.h"      // vector<Student_info>
// #include "extract_fails_v4.h"      // list<Student_info>
// ************************************************************
// ********************* AMEND THIS ***************************
// Solution to Exercise 5-3: Pick one of the followings
typedef vector<Student_info> Student_group;
// typedef list<Student_info> Student_group;
// ************************************************************

Test 1 Result

These students have passed.
Kate (88.88)
Pat (66.66)
Joe (100)
Fred (77.77)

These students have failed.
John (55.55)
Mary (11.11)
Bill (33.33)
Jay (22.22)
Bob (4)
Louis (44.44)

Test 2 – list based version

Amend the #include line and the typdef line accordingly.

// ********************** AMEND THIS  *************************
// Solution to Exercise 5-3: Pick one of the followings (v3 or v4)
// #include "extract_fails_v3.h"      // vector<Student_info>
#include "extract_fails_v4.h"      // list<Student_info>
// ************************************************************
// ********************* AMEND THIS ***************************
// Solution to Exercise 5-3: Pick one of the followings
//typedef vector<Student_info> Student_group;
typedef list<Student_info> Student_group;
// ************************************************************

Test 2 Result

These students have passed.
Kate (88.88)
Pat (66.66)
Joe (100)
Fred (77.77)

These students have failed.
John (55.55)
Mary (11.11)
Bill (33.33)
Jay (22.22)
Bob (4)
Louis (44.44)

Reference

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

One thought on “Accelerated C++ Solution to Exercise 5-3”

  1. Thank you very much for this blog. I did read one by one. It is very useful for learning this book.

    The grade.h is incorrect. I guess when you copy, you copy it from wrong file which is the extract_fails_v4

    It supposes to be

    #ifndef GUARD_GRADE_H
    #define GUARD_GRADE_H

    //grade.h
    #include
    #include “Student_info.h”

    double grade(double, double, double);
    double grade(double, double, const std::vector&);
    double grade(const Student_info&);
    bool fgrade(const Student_info& s);

    #endif // GUARD_GRADE_H

Leave a reply