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

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

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

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• extract_fails.cpp
• fgrade.cpp
• grade.cpp
• median.cpp
• pgrade.cpp
• Student_info.cpp

Header File List

• extract_fails.h
• fgrade.h
• grade.h
• median.h
• pgrade.h
• Student_info.h

Source Files

main.cpp

#include <iostream>          // std::cin, std::cout, std::endl
#include <string>            // std::string
#include <vector>            // std::vector
#include <algorithm>         // std::sort
#include "Student_info.h"    // Student_info, read
#include "extract_fails.h"   // extract_fails
#include "grade.h"  // grade

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

int 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
    vector<Student_info> students_failed = extract_fails(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 << " (" << grade(*i) << ")" << 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 << " (" << grade(*i) << ")" << endl;

    return 0;
}

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 two-pass solution to extract the failed students
// (S6.3.1/117)
vector<Student_info> extract_fails(vector<Student_info>& students)
{
  vector<Student_info> fail;
  remove_copy_if(students.begin(), students.end(),
                 back_inserter(fail), pgrade);
  students.erase(remove_if(students.begin(), students.end(), fgrade),
                 students.end() );
  return fail;
}

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>
// (S4.1.1/53)
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];
}

pgrade.cpp

#include "Student_info.h"  // Student_info
#include "fgrade.h"        // fgrade

// predicate to determine whether a student has passed (not failed)
// (S6.3.1/117)
bool pgrade(const Student_info& s)
{
    return !fgrade(s);
}

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

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

#endif // GUARD_EXTRACT_FAILS_H

fgrade.h

#ifndef GUARD_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

pgrade.h

#ifndef GUARD_PGRADE_H
#define GUARD_PGRADE_H

// pgrade.h

#include "Student_info.h"  // Student_info

bool pgrade(const Student_info&);

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

I now provide a set of student grades. The program separate the students to the pass and fail groups 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

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

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.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• average.cpp
• average_analysis.cpp
• average_grade.cpp
• did_all_hw.cpp
• grade.cpp
• grade_aux.cpp
• median.cpp
• median_analysis.cpp
• optimistic_median.cpp
• optimistic_median_analysis.cpp
• Student_info.cpp
• write_analysis.cpp

Header File List

• average.h
• average_analysis.h
• average_grade.h
• did_all_hw.h
• grade.h
• grade_aux.h
• median.h
• median_analysis.h
• optimistic_median.h
• optimistic_median_analysis.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 "median_analysis.h"  // median_analysis
#include "average_analysis.h"  // average_analysis
#include "optimistic_median_analysis.h"  // optimistic_median_analysis

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

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

#include <vector>  // vector
#include <algorithm>  // transform
#include "Student_info.h"  // Student_info
#include "average_grade.h"  // average_grade
#include "median.h"  // median

using std::vector;
using std::transform;

// Perform average analysis
// (S6.2.3/115)
double average_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), average_grade);
  return median(grades);
}

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

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

median_analysis.cpp

#include <vector>  // vector
#include <algorithm>  // transform
#include "Student_info.h"  // Student_info
#include "grade_aux.h"  // grade
#include "median.h"  // median

using std::vector;
using std::transform;

// S6.2.2/112
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.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));
}

optimistic_median_analysis.cpp

#include <vector>  // vector
#include <algorithm>  // transform
#include "Student_info.h"  // Student_info
#include "optimistic_median.h" // optimistic_median
#include "median.h"  // median

using std::vector;
using std::transform;

// Auxiliary function
// (S6.2.3/115) - adjust accordingly
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);
}

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

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

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

#ifndef GUARD_AVERAGE_ANALYSIS_H
#define GUARD_AVERAGE_ANALYSIS_H

// average_analysis.h

#include <vector>

double average_analysis(const std::vector<Student_info>&);

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

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

median_analysis.h

#ifndef GUARD_MEDIAN_ANALYSIS_H
#define GUARD_MEDIAN_ANALYSIS_H

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

double median_analysis(const std::vector<Student_info>&);

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

optimistic_median_analysis.h

#ifndef GUARD_OPTIMISTIC_MEDIAN_ANALYSIS_H
#define GUARD_OPTIMISTIC_MEDIAN_ANALYSIS_H

// optimistic_median_analysis.h

#include <vector>

double optimistic_median_analysis(const std::vector<Student_info>&);

#endif // GUARD_OPTIMISTIC_MEDIAN_ANALYSIS_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 analysis(const std::vector<Student_info>&),
                    const std::vector<Student_info>&,
                    const std::vector<Student_info>&);

#endif // GUARD_WRITE_ANALYSIS_H

Test Program

I now submit a set of hypyethetical student grades. As expected, the optimistic scheme (3rd one), gives higher median grades for the students who didn’t do all the homework.

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

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

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.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• find_urls.cpp
• not_url_char.cpp
• url_beg.cpp
• url_end.cpp
• vcout.cpp

Header File List

• find_urls.h
• not_url_char.h
• url_beg.h
• url_end.h
• vcout.h

Source Files

main.cpp

#include <iostream>  // cin, cout, endl
#include <string>  // string
#include <vector>  // vector
#include "find_urls.h"  // find_url
#include "vcout.h"  // vcout

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

int main()
{
    cout << "Enter a line. This program automatically find URLs..." << endl;

    // Read a line of input, then find and display URLs.
    string line;
    vector<string> urls;
    while (getline(cin, line)) {
      vector<string> urls = find_urls(line);
      vcout(urls);
    }

    return 0;
}

find_urls.cpp

#include <string>  // string
#include <vector>  // vector
#include "url_beg.h"  // url_beg
#include "url_end.h"  // url_end

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

vector<string> find_urls(const string& s)
{
  vector<string> ret;
  typedef string::const_iterator iter;
  iter b = s.begin(), e = s.end();

  // look through the entire input
  while (b != e) {

    // look for one or more letters followed by ://
    b = url_beg(b, e);

    // if we found it
    if (b != e) {
      // get the rest of the URL
      iter after = url_end(b, e);

      // remember the URL
      ret.push_back(string(b, after));

      // advance b and check for more URLs on this line
      b = after;
    }
  }
  return ret;
}

not_url_char.cpp

<br />#include <string>          // string, isalnum
#include <algorithm>       // find

using std::string;

bool not_url_char(char c)
{
  // characters, in addition to alphanumerics, that can appear in a URL
  static const string url_ch = "~;/?:@=&$-_.+!*'(),";

  // see whether c can appear in a URL and return the negative
  return !(isalnum(c) || find(url_ch.begin(), url_ch.end(), c) != url_ch.end() );
}

url_beg.cpp

#include <string>  // string, isalpha
#include <algorithm>  // search
#include "not_url_char.h"  // not_url_char

using std::string;

string::const_iterator
url_beg(string::const_iterator b, string::const_iterator e)
{
  static const string sep = "://";
  typedef string::const_iterator iter;

  // i marks where the separator was found
  iter i = b;

  while ((i = search(i, e, sep.begin(), sep.end() )) != e) {

    // make sure the separator isn't at the beginning or end of the line
    if (i != b && i + sep.size() != e) {

      // beg marks the beginning of the protocol-name
      iter beg = i;
      while (beg != b && isalpha(beg[-1]))
        --beg;

      // is there at least one appropriate character before and after the separator?
      if (beg != i && !not_url_char(i[sep.size()]))
        return beg;
    }

    // the separator we found wasn't part of a URL; advance i past this separator
    i += sep.size();
  }
  return e;
}

url_end.cpp

#include <string>  // string
#include <vector>  // vector
#include <algorithm>  // find_if
#include "not_url_char.h"  // not_url_char

using std::string;

string::const_iterator
url_end(string::const_iterator b, string::const_iterator e)
{
  return find_if(b, e, not_url_char);
}

vcout.cpp

#include <iostream>
#include <string>    // string
#include <vector>    // vector

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

int vcout(const vector<string>& v)
{
  for (vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
    cout << (*i) << endl;

  return 0;
}

Header Files

find_urls.h

#ifndef GUARD_FIND_URLS_H
#define GUARD_FIND_URLS_H

#include <vector>
#include <string>

std::vector<std::string> find_urls(const std::string&);

#endif // GUARD_FIND_URLS_H

not_url_char.h

#ifndef GUARD_NOT_URL_CHAR_H
#define GUARD_NOT_URL_CHAR_H

bool not_url_char(char);

#endif // GUARD_NOT_URL_CHAR_H

url_beg.h

#ifndef GUARD_URL_BEG_H
#define GUARD_URL_BEG_H

std::string::const_iterator
url_beg(std::string::const_iterator, std::string::const_iterator);

#endif // GUARD_URL_BEG_H

url_end.h

#ifndef GUARD_URL_END_H
#define GUARD_URL_END_H

#include <string>

std::string::const_iterator
url_end(std::string::const_iterator, std::string::const_iterator);

#endif // GUARD_URL_END_H

vcout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

int vcout(const std::vector<std::string>&);

#endif // GUARD_VCOUT_H

Test program

Let’s do some simple tests:

• Submitting the line “Have you tried http://google.co.uk and http://bbc.co.uk ?”, the program should return: “http://google.co.uk” and “http://bbc.co.uk”.
• Submitting the line “Have you tried http:// or google.co.uk or http://google.co.uk ?”, the program should return: “http://google.co.uk”.
• Submitting the line “Have you tried http or :// or http://bbc.co.uk ?”, the program should return: “http://bbc.co.uk “.

Reference

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

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

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.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• isPalindrome.cpp
• vcout.cpp

Header File List

• isPalindrome.h
• vcout.h

Source Files

main.cpp

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

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

int main()
{
  string word;
  vector<string> words;
  vector<string> palindromes;

  // Populate vector
  while (cin >> word) {
    if (isPalindrome(word))
      palindromes.push_back(word);
  }

  // Print palindrome
  cout << "\nThese are the palindromes identified: " << endl;
  vcout(palindromes);

  return 0;
}

isPalindrome.cpp

#include <string>

using std::string;

bool isPalindrome(const string& s)
{
  return equal(s.begin(), s.end(), s.rbegin() );
}

vcout.cpp

#include <iostream>
#include <string>    // string
#include <vector>    // vector

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

int vcout(const vector<string>& v)
{
  for (vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
    cout << (*i) << endl;

  return 0;
}

Header Files

isPalindrome.h

#ifndef GUARD_ISPALINDROME_H
#define GUARD_ISPALINDROME_H

#include <string>

bool isPalindrome(const std::string&);

#endif // GUARD_ISPALINDROME_H

vcout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

int vcout(const std::vector<std::string>&);

#endif // GUARD_VCOUT_H

Test Program

I know enter a list of words. The program should automatically identify and display the palindrome. Note that for simplicity sake the program is case sensitive – in this test I shall strictly stick to lower case letters. I shall type in the following lines:

• good morning bob
• lol what a beautiful moon
• eeeeeeeee aaaaaaa banana

The the program should identify these words as palindromes (as they spell the same in both directions): bob, lol, a, eeeeeeeee, aaaaaaa

good morning bob
lol what a beautiful moon
eeeeeeeee aaaaaaa banana
^Z

These are the palindromes identified:
bob
lol
a
eeeeeeeee
aaaaaaa

Reference

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

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

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.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• split.cpp
• vcout.cpp

Header File List

• split.h
• vcout.h

Source Files

main.cpp

</p>

<h1>include &lt;iostream&gt;</h1>

<h1>include &lt;string&gt;</h1>

<h1>include &lt;vector&gt;</h1>

<h1>include &quot;vcout.h&quot;</h1>

<h1>include &quot;split.h&quot;</h1>

<p>using std::string;
using std::vector;
using std::cin;
using std::cout;
using std::endl;</p>

<p>int main()
{
    // Read a line of input, split into words, and display
    string line;
    vector&lt;string&gt; words;
    while (getline(cin, line)) {
      vector&lt;string&gt; words = split(line);
      vcout(words);
    }</p>

<pre><code>return 0;
</code></pre>

<p>}</p>

<p>

split.cpp

</p>

<h1>include &lt;string&gt;    // string</h1>

<h1>include &lt;vector&gt;    // vector</h1>

<h1>include &lt;cctype&gt;    // isspace</h1>

<h1>include &lt;algorithm&gt;  // find_if</h1>

<p>using std::vector;
using std::string;
using std::isspace;
using std::find_if;</p>

<p>// true if the argument is whitespace, false otherwise
// (S6.1.1/103)
bool space(char c)
{
  return isspace(c);
}</p>

<p>// false if the argument is whitespace, true otherwise
// (S6.1.1/103)
bool not_space(char c)
{
  return !isspace(c);
}</p>

<p>// Scan a line and split into words. Return a vector that contains these words.
// (S6.1.1/103)
vector&lt;string&gt; split(const string&amp; str)
{
  typedef string::const_iterator iter;
  vector&lt;string&gt; ret;</p>

<p>iter i = str.begin();
  while (i != str.end()) {</p>

<pre><code>// Ignore leading blanks
i = find_if(i, str.end(), not_space);

// Find end of next word
iter j = find_if(i, str.end(), space);

// Copy the characters in ([i, j)
if (i != str.end())
  ret.push_back(string(i, j));

// Re-initialize
i = j;
</code></pre>

<p>}
  return ret;
}</p>

<p>

vcout.cpp

</p>

<h1>include &lt;iostream&gt;</h1>

<h1>include &lt;string&gt;    // string</h1>

<h1>include &lt;vector&gt;    // vector</h1>

<p>using std::cout;
using std::endl;
using std::string;
using std::vector;</p>

<p>int vcout(const vector&lt;string&gt;&amp; v)
{
  for (vector&lt;string&gt;::const_iterator i = v.begin(); i != v.end(); ++i)
    cout &lt;&lt; (*i) &lt;&lt; endl;</p>

<p>return 0;
}</p>

<p>

Header Files

split.h

</p>

<h1>ifndef GUARD_SPLIT_H</h1>

<h1>define GUARD_SPLIT_H</h1>

<h1>include &lt;vector&gt;</h1>

<h1>include &lt;string&gt;</h1>

<p>std::vector&lt;std::string&gt; split(const std::string&amp;);</p>

<h1>endif // GUARD_SPLIT_H</h1>

<p>

vcout.h

</p>

<h1>ifndef GUARD_VCOUT_H</h1>

<h1>define GUARD_VCOUT_H</h1>

<h1>include &lt;string&gt;</h1>

<h1>include &lt;vector&gt;</h1>

<p>int vcout(const std::vector&lt;std::string&gt;&amp;);</p>

<h1>endif // GUARD_VCOUT_H</h1>

<p>

Test Program

By entering a text line, say, “The quick brown fox jumped over the fence”, the program should be able to dice in into words and display accordingly.

The quick brown fox jumped over the fence
The
quick
brown
fox
jumped
over
the
fence
^Z

Reference

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