This is Part 1 of the 3-part Solution to Exercise 5-0.

Exercise 5-0 (Part 1 / 3)

We extend the Solution to Exercise 4-0 (i.e. the student grading program) to include a capability that split the set of students (objects) into two groups – namely the passing students and failing students. This capability is enabled by a new “home-made” function called extract_fails. This function can be written in 4 different versions in which all 4 versions deliver the same result, with the slight difference in terms of efficiency. It goes from version 1 being the most primitive / inefficient, to version 4 being the most elegant / efficient. We will describe and test out each version one-by-one.

The Problem

The objective of this exercise is to enhance the Chapter 4 program so that we are able to determine, out of the entire Student_info object population, which ones belong to the passing group, and which ones belong to the failing group.

The Solution Strategy

There are many good ways to implement this Chapter 5 example program. Here is my strategy:

Make a copy of the entire Chapter 4 project. i.e. the Project as per Solution to Exercise 4-0.
Add a C++ source file extract_fails.cpp. It contains the 4 versions of the extract_fail function. To make it easy to test later, I simply create 4 functions. Namely: extract_fails_v1, extract_fails_v2, extract_fails_v3, extract_fails_v4. The function fgrade is also stored in this file.
Add a corresponding C++ header file. i.e. extract_fails.h.
Adjust the main function to make it suitable for testing. Note that extract_fail version 1, 2 and 3 use vector<Student_info> container, whereas version 4 uses list<Student_info> container. Because of this, I will have two versions of main program for the testing – i.e. no1_main() for testing out extract_fail version 1, 2, 3. no2_main() for testing out extract_fail version 4.

The Project

I partition the program into smaller chunks – i.e. in C++ source files and header files. This diagram below shows what the Code::Block Management Tree look like after successful creation of these files.

Acpp5p0p1MgntTree

Note that majority of these files are straight copies of the Chapter 4 Program. (i.e. Solution to Exercise 4-0). (the ones that are NOT circled in red)

In this exercise we add these files (circled in red as per snapshot diagram above): extract_fails.cpp, extract_fails.h. We also amend the main.cpp accordingly so that we are able to test out the newly written functions using tailored main program.

C++ Source Files

main.cpp – (Adjust accordingly) this is the first program that is run during the implementation phase.
extract_fails.cpp – (New!) contains the fgrade function, and the 4 versions extract_fail functions.
grade.cpp – (From Chapter 4) contains all functions relating to computing grades.
median.cpp – (From Chapter 4) contains all functions relating to computing median.
Student_info.cpp – (From Chapter 4) contains all functions relating to handling a Student_info object.

C++ Header Files

extract_fails.h – (New!) declare the functions as defined in extract_fails.cpp.
grade.h – (From Chapter 4) declare the functions as defined in grade.cpp.
median.h – (From Chapter 4) declare the functions as defined in median.cpp
Student_info.h – (From Chapter 4) declare the functions as defined in Student_info.cpp, plus defining the data structure of the Student_info (object) type.

Source Files

main.cpp (Adjust accordingly)

#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include <list>
#include "grade.h"
#include "Student_info.h"
#include "extract_fails.h"

using std::cin;
using std::cout;
using std::endl;
using std::domain_error;
using std::max;
using std::setprecision;
using std::sort;
using std::streamsize;
using std::string;
using std::vector;
using std::list;

// There are two main programs here.
//   - The top one is used to test out extract_fails version 1, 2, and 3.
//   - The bottom one is for testing out extract_fails version 4.
// Simply replace the no1_main() or no2_main() with main() to activate the main program to run

// for testing extract_fails_v1 / v2 / v3 - that uses vector
int no1_main()
{
    vector<Student_info> students;
    Student_info record;

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

    // Extract the failed students (use extract_fails_v1 / v2 / v3)
    vector<Student_info> students_failed = extract_fails_v3(students);

    // sort vectors
    sort(students.begin(),students.end(),compare);
    sort(students_failed.begin(),students_failed.end(),compare);

    // Report passing students
    cout << "These students have passed." << endl;
    for (vector<Student_info>::const_iterator i = students.begin();
         i != students.end(); ++i)
        cout << i->name << endl;

    // Report failing students
    cout << "These students have failed." << endl;
    for (vector<Student_info>::const_iterator i = students_failed.begin();
         i != students_failed.end(); ++i)
        cout << i->name << endl;

    return 0;
}


// for testing extract_fails_v4 - that uses list
int no2_main()
{
    list<Student_info> students;
    Student_info record;

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

    // Extract the failed students
    list<Student_info> students_failed = extract_fails_v4(students);

    // sort lists
    students.sort(compare);
    students_failed.sort(compare);

    // Report passing students
    cout << "These students have passed." << endl;
    for (list<Student_info>::const_iterator i = students.begin();
         i != students.end(); ++i)
        cout << i->name << endl;

    // Report failing students
    cout << "These students have failed." << endl;
    for (list<Student_info>::const_iterator i = students_failed.begin();
         i != students_failed.end(); ++i)
        cout << i->name << endl;

    return 0;
}

extract_fails.cpp

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

using std::vector;
using std::list;


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

// separate passing and failing student records
// version 1: maintain two vectors (pass and fail) within local scope
// Can use up lots of memory resource.
// (S5.1/76)
vector<Student_info> extract_fails_v1(vector<Student_info>& students)
{
    vector<Student_info> pass, fail;

    for (vector<Student_info>::size_type i = 0;
         i != students.size(); ++i)
         if (fgrade(students[i]))
            fail.push_back(students[i]);
         else
            pass.push_back(students[i]);

    students = pass;
    return fail;
}

// separate passing and failing student records
// version 2: maintain one vector (fail) within local scope. Update pass vector by reference.
// correct but potentially slow. (Still use up lots of memory resource but less than version 1)
// (S5.1.1/77)
vector<Student_info> extract_fails_v2(vector<Student_info>& students)
{
    vector<Student_info> fail;
    vector<Student_info>::size_type i = 0;

    // invariant: elements [0,i) of students represent passing grades
    while (i != students.size())
    {
        if (fgrade(students[i]))
        {
            fail.push_back(students[i]);
            students.erase(students.begin() + i);
        }
        else
            ++ i;
    }
    return fail;
}

// separate passing and failing student records
// version 3: iterators but no indexing; still potentially slow
// (S5.3/82)
vector<Student_info> extract_fails_v3(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;
}

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

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

extract_fails.h

#ifndef GUARD_EXTRACT_FAILS_H
#define GUARD_EXTRACT_FAILS_H

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

bool fgrade(const Student_info&);
std::vector<Student_info> extract_fails_v1(std::vector<Student_info>&);
std::vector<Student_info> extract_fails_v2(std::vector<Student_info>&);
std::vector<Student_info> extract_fails_v3(std::vector<Student_info>&);
std::list<Student_info> extract_fails_v4(std::list<Student_info>&);

#endif // GUARD_EXTRACT_FAILS_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 - final version
#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

We need to do four tests to test out the extract_fails function version 1, 2, 3, and 4 accordingly.

As seen in the main.cpp, I have made a note on how to do this:

// There are two main programs here.
//   - The top one is used to test out extract_fails version 1, 2, and 3.
//   - The bottom one is for testing out extract_fails version 4.
// Simply replace the no1_main() or no2_main() with main() to activate the main program to run

For clarity purpose I will list out exactly how to change the main.cpp accordingly for this program testing.

To test extract_fails version 1:

Inside no1_main(), replace the extract_fails_XX to extract_fails_v1.
Replace no1_main() with main().

To test extract_fails version 2:

Inside no1_main(), replace the extract_fails_XX to extract_fails_v2.
Replace no1_main() with main().

To test extract_fails version 3:

Inside no1_main(), replace the extract_fails_XX to extract_fails_v3.
Replace no1_main() with main().

To test extract_fails version 4:

Inside no2_main(), replace the extract_fails_XX to extract_fails_v4.
Replace no2_main() with main().

Notes

Note again, no1_main() focuses on vector<string>, whereas no2_main() focuses on list<string>.

I have also taken the liberty to test out the sort function (highlighted in S5.1.1/86 of the text book). i.e.

To sort a vector, do:

    // sort vectors
    sort(students.begin(),students.end(),compare);
    sort(students_failed.begin(),students_failed.end(),compare);

To sort a list, do:

    // sort lists
    students.sort(compare);
    students_failed.sort(compare);

Results

I have run through all 4 versions above and confirm that all give the same result. Some snapshots captured below.

Recall that the finalGrade = ( 20% x midTermGrade ) + (40% x finalTermGrade) + (40% x medianOfHomeworkGrades)

To simplify the test, I know that, if I provide the same value for midTermGrade, finalTermGrade, and homeworkGrades, then the finalGrade should technically be the same value. e.g. if all grades are 90, then the finalGrade is bound to be 90 also. The idea is that, I know the passing grade is 60 or above (and likewise, failing grade is less than 60). By providing the grades for a list of students, I can easily determine (using my head) whether the student should pass or fail. I can then compare with the test result computed by the program. If the program is working as expected, both set of test results should match. (And they indeed do).

Test 1

Aim of this test is to prove that the program is able to split the group of students into two groups – the passing and failing groups.

aaa 90 90 90 90 90
bbb 80 80 80 80 80
ccc 70 70 70 70 70
ddd 60 60 60 60 60
eee 50 50 50 50 50
fff 40 40 40 40 40
ggg 30 30 30 30 30
hhh 10 10 10 10 10
iii 0 0 0 0 0
^Z
^Z
These students have passed.
aaa
bbb
ccc
ddd
These students have failed.
eee
fff
ggg
hhh
iii

Test 2

Aim of this test is essentially the same as test 1, plus the ability to sort.

fff 40 40 40 40 40
bbb 80 80 80 80 80
ccc 70 70 70 70 70
iii 0 0 0 0 0
eee 50 50 50 50 50
aaa 90 90 90 90 90
hhh 10 10 10 10 10
ddd 60 60 60 60 60
ggg 30 30 30 30 30
^Z
^Z
These students have passed.
aaa
bbb
ccc
ddd
These students have failed.
eee
fff
ggg
hhh
iii

Test 3

Aim of this test is to show that the program runs okay when all students have passing grades.

aaa 90 90 90 90 90
bbb 80 80 80 80 80
ccc 70 70 70 70 70
ddd 60 60 60 60 60
^Z
^Z
These students have passed.
aaa
bbb
ccc
ddd
These students have failed.

Test 4

Aim of this test is to show that the program runs okay when all students have failing grades.

eee 50 50 50 50 50
fff 40 40 40 40 40
ggg 30 30 30 30 30
hhh 10 10 10 10 10
iii 0 0 0 0 0
^Z
^Z
These students have passed.
These students have failed.
eee
fff
ggg
hhh
iii

Test 5

Aim of this test is to show that the program runs okay even when we provide no input data at all.

^Z
These students have passed.
These students have failed.

Conclusion

We have successfully put all the files and sub-programs together, implemented the algorithm in an IDE like Code::Block, in a “partitioned” manner (as suggested by the Author at S4.3/65).
We have tested all 4 versions of the extract_fail function. Though I have not proved it here, we know that (according to the Author) that version 1 is least efficient and version 4 is most efficient (2 and 3 are somewhat in the middle).
We have learnt abut iterator, vector and list. Our confident level with using C++, have gone up another notch.

Reference

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

4 thoughts on “Accelerated C++ Solution to Exercise 5-0 (Part 1 / 3)”

Hao Wu says:

April 21, 2015 at 21:42
Thank you Johnny for awesome answers. I had really hard time with compiling code sample in this chapter.
Here’s my makefile based on this solution.
```
CXX = g++
CC = g++

all: main

Student_info.o: Student_info.cc Student_info.h

grade.o: grade.cc grade.h median.h Student_info.h

extract_fails.o: extract_fails.cc extract_fails.h Student_info.h

main.o: main.cc grade.h median.h Student_info.h extract_fails.h

median.o: median.cc median.h

main: main.o grade.o median.o Student_info.o extract_fails.o

test: all
./main <../data/single_grade
./main <../data/single_grade
./main <../data/grades
./main <../data/grades

clobber:
rm -f *.o *.exe core main
```
1. Johnny says:
  
  April 22, 2015 at 06:58
  
  Hi Hao, I’m glad this helped. I did recall this exercise took me ages to implement back then, so well done for getting this far! (btw I have blocked quoted your solution with three backticks (above and below the codes) so it displays slightly better (part of the WordPress Markdown feature). And thank you for the kind words – it means a lot to me!
Jame says:

July 27, 2015 at 00:09

Hey, wanted to say I do appreciate the work you put into this!
anand says:

November 18, 2019 at 06:28

hey,i think even read grade etc. need manipulation as we are using vector to read something that we will store in list

Comments are closed.

M	T	W	T	F	S	S
« Jul				Sep »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Mathalope

Accelerated C++ Solution to Exercise 5-0 (Part 1 / 3)

Exercise 5-0 (Part 1 / 3)

The Problem

The Solution Strategy

The Project

C++ Source Files

C++ Header Files

Source Files

main.cpp (Adjust accordingly)

extract_fails.cpp

grade.cpp

median.cpp

Student_info.cpp

Header Files

extract_fails.h

grade.h

median.h

Student_info.h

Test Program

To test extract_fails version 1:

To test extract_fails version 2:

To test extract_fails version 3:

To test extract_fails version 4:

Notes

Results

Test 1

Test 2

Test 3

Test 4

Test 5

Conclusion

Reference

4 thoughts on “Accelerated C++ Solution to Exercise 5-0 (Part 1 / 3)”

A Scientific Programming Sketchbook

Exercise 5-0 (Part 1 / 3)

The Problem

The Solution Strategy

The Project

C++ Source Files

C++ Header Files

Source Files

main.cpp (Adjust accordingly)

extract_fails.cpp

grade.cpp

median.cpp

Student_info.cpp

Header Files

extract_fails.h

grade.h

median.h

Student_info.h

Test Program

To test extract_fails version 1:

To test extract_fails version 2:

To test extract_fails version 3:

To test extract_fails version 4:

Notes

Results

Test 1

Test 2

Test 3

Test 4

Test 5

Conclusion

Reference

Share this:

4 thoughts on “Accelerated C++ Solution to Exercise 5-0 (Part 1 / 3)”

A Scientific Programming Sketchbook