Exercise 5-4

Look again at the driver functions you wrote in the previous exercise. Note that it is possible to write a driver that differs only in the declaration of the type for the data structure that holds the input file. If your vector and list test drivers differ in any other way, rewrite them so that they differ only in this declaration.

Solution

The objective is to further streamline the program, so that the only change required for switching between running a vector-based and list-based workstream is a one-liner change at the declaration level.

My Solution to Exercise 5-3 require 2-line change (rather than just 1-line), so obviously there are opportunities to improve. I also see that the program contains two near identical set of source and header files (i.e. extract_fails_v3.cpp/.h, extract_fails_v4.cpp/.h) – it is very likely that we can consolidate into just one set (i.e. extract_fails.cpp/.h) – as the only difference resides on the fact that one uses vector and the other uses list – other than that, the codes are effectively the same.

So here is a rather neat way to achieve our objective (and it works!)

1. Create a new Student_info.h to store the a new type Student_group (defined by typedef) – which may be either vector or list based. To switch between using vector-based Student_group or list-based Student_group, we just need to do a one-liner change in this file. All other files are intact.
2. Consolidate extract_fails_v3.cpp/.h (vector based) and extract_fails_v4.cpp/.h (list based) into one extract_fails.cpp/.h. (generic Student_group based)
3. Refresh the #include directives within the codes as required.

The Project

For completeness I shall include all the files here.

• main.cpp
• extract_fails.h
• extract_fails.cpp
• grade.h
• grade.cpp
• median.h
• median.cpp
• Student_info.h
• Student_info.cpp
• Student_group.h

main.cpp

#include <iostream>
#include "Student_info.h"
#include "Student_group.h" // switch between vector and list based Student_group here
#include "grade.h"
#include "extract_fails.h"

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

int main()
{

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

#ifndef GUARD_EXTRACT_FAILS_H
#define GUARD_EXTRACT_FAILS_H

// extract_fails.h
#include "Student_group.h"

Student_group extract_fails(Student_group&);

#endif // GUARD_EXTRACT_FAILS_H

extract_fails.cpp

#include "Student_info.h"
#include "Student_group.h"
#include "grade.h"

// separate passing and failing student records
// derived from S5.5/85
Student_group extract_fails(Student_group& students)
{
    Student_group fail;
    Student_group::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

#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&);
bool fgrade(const Student_info&);

#endif // GUARD_GRADE_H

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

Student_group.h

#ifndef GUARD_STUDENT_GROUP_H
#define GUARD_STUDENT_GROUP_H

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

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

#endif // GUARD_STUDENT_GROUP_H

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 Student_group.h accordingly (one-liner change).

// ********************* AMEND THIS ***************************
// Solution to Exercise 5-4: Pick one of the followings
typedef std::vector<Student_info> Student_group;
// typedef std::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 Student_group.h accordingly (one-liner change).

// ********************* AMEND THIS ***************************
// Solution to Exercise 5-4: Pick one of the followings
// typedef std::vector<Student_info> Student_group;
typedef std::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)

Conclusion

Overall this is a very good exercise to train our ability to be more “generalise” about writing codes. e..g reduce duplication. It has been suggested by the Author that this exercise builds the grounds for the C++ template topic later on in the book.

Reference

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

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.

• main.cpp
• extract_fails_v3.h
• extract_fails_v3.cpp
• extract_fails_v4.h
• extract_fails_v4.cpp
• grade.h
• grade.cpp
• median.h
• median.cpp
• Student_info.h
• Student_info.cpp

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

Exercise 5-2

Write the complete new version of the student-grading program, which extracts records for failing students, using vectors. Write another that uses lists. Measure the performance difference on input files of 10 lines, 1,000 lines, and 10,000 lines.

Solution

The objective of this exercise is to compute the overall job run duration for the function vector<Student_info> extract_fails, and another function list<Student_info> extract_fails. These two functions are essentially the same, except one uses vector and the other uses list.

Fortunately the codes in Chapter 5 of the book (version 3 for vector and version 4 for list), or my Solution to Exercise 5-0 (Part 1/3) has already provided the skeleton structure for this. All I need to do is to adjust the program slightly to incorporate the followings:

1. Have a pair of start and end time-stamps just before and after the extract_fails function.
2. Compute the duration by taking the time difference between the end and start time.
3. Display the duration.

Once we have these new features in our revised program, we are then able to re-run the program using varying number of input (lines).

As I did not recall there were any mentions about time-stamping in the book, I did a Google search and found this very clever clock_t technique (by Dolph) on the Stack Overflow Forum, in conjunction with the clock_t documentation on the cplusplus.com website.

i.e. the <ctime> directive, clock_t , clock(), and CLOCKS_PER_SEC.

This is how to use it.

    clock_t startTime = clock();
    doWhateverFunctionHere();
    clock_t endTime = clock();
    clock_t clockTicksTaken = endTime - startTime;
    double timeInSeconds = clockTicksTaken / (double) CLOCKS_PER_SEC;

The strategy is therefore:

1. Make a copy of the entire project as per Solution to Exercise 5-0 (Part 1/3).
2. Create a new extract_fails.cpp that contains two functions: Function test_extract_fails_v3 computes and displays the duration for the vector<Student_info> case. Function test_extract_fails_v4 is similar but for the list<Student_info> case. Wrap these under a header file extract_fails.h.
3. Simplify the main program to enable easy invocation of each function.

The Project

For clarity sake I include the high level project tree here. Note that majority of the files are from Solution to Exercise 5-0 (Part 1/3) – any files that are not mentioned below are mentioned in that post. In this post I shall only include the new / revised files.

• main.cpp – revised for easy invocation of the functions test_extract_fails_v3 and Function test_extract_fails_v4.
• test_extract_fails.cpp – contains the functions test_extract_fails_v3 and test_extract_fails_v4.
• test_extract_fails.h – declare the functions in test_extract_fails.cpp.

main.cpp

#include "test_extract_fails.h"

int main()
{
    // invoke either one of the following as required
    // test_extract_fails_v3();
    test_extract_fails_v4();

    return 0;
}

test_extract_fails.cpp

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

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


// There are two functions here.
//   - The top one is used to test out extract_fails version 3 (vector<Student_info>).
//   - The bottom one is for testing out extract_fails version 4 (list<Student_info>).

// for testing extract_fails_v3 - that uses vector<Student_info>
int test_extract_fails_v3()
{
    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_v3) and time-stamp it!
    clock_t startTime = clock();
    vector<Student_info> students_failed = extract_fails_v3(students);
    clock_t endTime = clock();
    clock_t clockTicksTaken = endTime - startTime;
    double timeInSeconds = clockTicksTaken / (double) CLOCKS_PER_SEC;

    streamsize prec = cout.precision();
    cout << "Elapsed (in seconds): " << setprecision(30) << timeInSeconds
         << setprecision(prec) << endl;

    return 0;
}


// for testing extract_fails_v4 - that uses list<Student_info>
int test_extract_fails_v4()
{
    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 and time-stamp it!

    clock_t startTime = clock();
    list<Student_info> students_failed = extract_fails_v4(students);
    clock_t endTime = clock();
    clock_t clockTicksTaken = endTime - startTime;
    double timeInSeconds = clockTicksTaken / (double) CLOCKS_PER_SEC;

    streamsize prec = cout.precision();
    cout << "Elapsed (in seconds): " << setprecision(30) << timeInSeconds
         << setprecision(prec) << endl;

    return 0;
}

test_extract_fails.h

#ifndef GUARD_TEST_EXTRACT_FAILS_H
#define GUARD_TEST_EXTRACT_FAILS_H

int test_extract_fails_v3();
int test_extract_fails_v4();

#endif // GUARD_TEST_EXTRACT_FAILS_H

Test Program

I’ve run 3 trials for every individual tests and use these to compute the average job run duration for the extract_fail_v3 (vector) and extract_fail_v4 (list).

This is my sample set of 10 input lines.

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

To test out the case of 100, 1000, and 10000 lines, I simply “copy and paste” these 10 lines to fill the required number of lines. (This seems logical as our objective for this exercise is to compare performance of vector and list)

Test Result

File size	Extract_fails_v3 (vector<Student_info>)	Extract_fails_v4 (list<Student_info>)
10 lines	0.000 seconds	0.000 seconds
100 lines	0.003 seconds	0.001 seconds
1,000 lines	0.165 seconds	0.006 seconds
10,000 lines	9.300 seconds	0.045 seconds

From this we have just verified the hypothesis in S5.2.2/87 of the book – in which the Author suggested the exponential increase of job-run time when the input volume go beyond the magnitude of 10,000 lines.

Reference

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