Monday, February 17, 2003

Multi-source file solution (K&M §4.3)

multifile.zip: Same as main2.cpp discussed on Friday except that it has been decomposed over several files.

Using sequential containers (K&M Chapter 5)

We introduce the fgrade() predicate function to determine whether or not a student has passed the course:

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

This function calls the appropriate grade() which determines whether the given student passed or failed. The function has been added to the grade.cpp source module.

We then use this function to write a function that will partition a vector of student's into those who passed and those who failed:

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

using std::vector;

// separate passing and failing student records: first try
vector<Student_info> extract_fails(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;
}

This function can be called in our main() program as follows.

#include <algorithm>
#include <vector>
#include <iostream>
#include <string>

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

//driver program for grade partitioning examples

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

using std::max;

vector<Student_info> extract_fails(vector<Student_info>& v);

int main()
{
        vector<Student_info> vs;
        Student_info s;
        string::size_type maxlen = 0;
        while (read(cin, s)) {
                maxlen = max(maxlen, s.name.size());
                vs.push_back(s);
        }

        sort(vs.begin(), vs.end(), compare);

	vector<Student_info> fails = extract_fails(vs);

	for (vector<Student_info>::size_type i = 0; i < fails.size(); ++i)
		cout << fails[i].name << " " << grade(fails[i]) << endl;

	return 0;
}

Unfortunately, our first attempt at the extract_fails() function requires that we hold two copies in memory of the vector storing the students (just prior to the students = pass; assignment). We can do better by removing the actual failures from the list as we encounter them during our iteration.

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

using std::vector;

// second try: correct but potentially slow
vector<Student_info> extract_fails(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;
}

We can achieve a similar effect by using iterators. Note that no indexing is being done by this solution. We were accessing the vector sequentially anyway --- by using iterators below, we are merely demonstrating the sequential access order more explicitly.

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

using std::vector;

// version 3: iterators but no indexing; still potentially slow
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;
}

This solution is correct but it is still very inefficient because deletion from (and insertion into) the middle of a vector can be very inefficient.

Last modified: Mon Feb 17 15:23:21 2003