Tag Archives: Solutions

Accelerated C++ Solution to Exercise 5-11

Exercise 5-11

In text processing it is sometimes useful to know whether a word has any ascenders or descenders. Ascenders are the parts of lowercase letters that extend above the textline; in the English alphabet, the letters, b, d, f, h, k, l, and t have ascenders. Similarly, the descenders are the parts of lowercase letters that descend below the line; In English, the letters g, j, p, q, and y have descenders. Write a program to determine whether a word has any ascenders or descenders. Extend that program to find the longest word in the dictionary that has neither ascenders nor descenders.

Solution

This exercise is somewhat similar to the one we have just completed (Solution to Exercise 5-10), in which the user provides a list of words and the program filter and display the words that satisfy certain conditions.

Solution Strategy

Here is our Solution Strategy:

  1. Have a (bool type) function hasAscender to determine whether a given (string) word contains any ascenders (i.e. the letters b, d, f, h, k, l).
  2. Have a (bool type) function hasDescender to determine whether a given (string) word contains any Descenders (i.e. the letters g, j, p, q, and y).
  3. Use the usual while / cin / push_back method to read in a set of words.
  4. If the word contains any ascenders or descenders, append that word to a vector<string> container called interestingWords. Otherwise, append to another vector<string> container called boringWords.
  5. Have a function findLongest that is able to scan through a vector<string> container and return the longest (string) word.
  6. Print the vector<string> containers interestingWords and boringWords – in response to the challenge: Write a program to determine whether a word has any ascenders or descenders.
  7. Print the longest (string) word of the vector<string> container boringWords – in response to the challenge: Extend that program to find the longest word in the dictionary that has neither ascenders nor descenders.

A Side Note

The writing of the functions hasAscender and hasDescender will involve iterating through the letters within the given word, using multiple “hard-coded” if-conditions to determine whether the words container any ascenders / descenders. I do this because I wish to only use the techniques that have learnt so far. In this particular turns out to be okay as there is only a small handful of conditions need to be written. If we are faced with lots more conditions however, the if-condition techniques might not be as efficient (or the code might get too long).

A disclosure I would therefore like to make here is that in Chapter 6 (next chapter), the author would introduce a more compact method to deal with this type of scenario – using the standard library’s find function. Like the previous exercise, it looks like the author is trying to build up some grounds here before introducing us with the more compact methods.

The Project

This section summarise all the C++ source and header files that I use to accomplish this challenge.

Acpp5p11MgntTree

Source File List

Header File List

Source Files

main.cpp

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

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

int main()
{
  string word;
  vector<string> interestingWords;   // Words that contain either ascenders
                                     // or descenders
  vector<string> boringWords;  // Words that contain neither ascenders
                               // nor descenders

  // Populate vector
  while (cin >> word) {
    if (hasAscender(word) || hasDscender(word))
      interestingWords.push_back(word);
    else
      boringWords.push_back(word);
  }

  // Print the interesting words
  cout << "\nInteresting words (i.e. having ascenders or descenders):"
       << endl;
  vcout(interestingWords);

  // Print the boring words
  cout << "\nBoring words (i.e. having neither ascenders nor descenders):"
       << endl;
  vcout(boringWords);

  // Print the longest boring word
  cout << "\nThis is the longest boring word: " << findLongest(boringWords)
       << endl;

  return 0;
}

findLongest.cpp

#include <string>
#include <vector>

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

string findLongest(const vector<string>& words)
{
  string longestWord;
  for (vector<string>::const_iterator i = words.begin(); i != words.end(); ++i) {
    if ( i->size() > longestWord.size() )
      longestWord = *i;
  }
  return longestWord;
}

hasAscender.cpp

#include <string>

using std::string;

bool hasAscender(const string& s)
{
  for (string::const_iterator i = s.begin(); i != s.end(); ++i) {
    if (*i == 'b' || *i == 'd' || *i == 'f' || *i == 'h' || *i == 'k' ||
        *i == 'l' )
      return true;
  }
  return false;
}

hasDescender.cpp

#include <string>

using std::string;

bool hasDscender(const string& s)
{
  for (string::const_iterator i = s.begin(); i != s.end(); ++i) {
    if (*i == 'g' || *i == 'j' || *i == 'p' || *i == 'q' || *i == 'y')
      return true;
  }
  return false;
}

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 iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Header Files

findLongest.h

#ifndef GUARD_FINDLONGEST_H
#define GUARD_FINDLONGEST_H

#include <string>
#include <vector>

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

#endif // GUARD_FINDLONGEST_H

hasAscender.h

#ifndef GUARD_HASASCENDER_H
#define GUARD_HASASCENDER_H

#include <string>

bool hasAscender(const std::string&);

#endif // GUARD_HASASCENDER_H

hasDescender.h

#ifndef GUARD_HASDESCENDER_H
#define GUARD_HASDESCENDER_H

#include <string>

bool hasDscender(const std::string&);

#endif // GUARD_HASDESCENDER_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 now run the program, and provide the list of words. As expected the program correctly identified the words containing (and not-containing) either ascenders or descenders. It also resolves the (first observed) longest word that has neither ascenders nor descenders.

the quick brown fox
jumped over the fence
eeeeeee aceimnorsvwxz
nnnn
i love c++
^Z

Interesting words (i.e. having ascenders or descenders):
the
quick
brown
fox
jumped
the
fence
love

Boring words (i.e. having neither ascenders nor descenders):
over
eeeeeee
aceimnorsvwxz
nnnn
i
c++

This is the longest boring word: aceimnorsvwxz

Reference

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

Accelerated C++ Solution to Exercise 5-10

Exercise 5-10

Palindromes are words that are spelled the same right to left as left to right. Write a program to find all the palindromes in a dictionary. Next, find the longest palindrome.

Solution

Just a bit of disclosure before moving on. In chapter 6 (i.e. the next chapter) the author will introduce a more compact technique to auto detect palindromes. In this post however, I shall build up the solution using only the knowledge we have learnt so far (up to chapter 5). I believe the author is trying to build up the grounds before introducing new C++ techniques.

The solution strategy:

  1. As usual, have a means to read in words – using the while / cin / push_back method.
  2. Have a home-made function isPalindrome that takes in a string and do the “magic” – return (bool type) true if the string is a palindrome.
  3. Have a home-made function lowcase to convert all the letters of a word to lower case. This is to aid the letter comparison process within the isPalindrome function.
  4. Have a home-made findLongest function to determine the longest (string) palindrome,
  5. Re-use the home-made vcout function to display the string elements witin a vector<string> container. e.g. the vector containing the palindromes.

The isPalindrome Algorithm

A palindrome is a word that read the same in both directions. This function essentially require two iterators a and b, in which iterator a start from the first to last letter of the word, whereas iterator b (is vice versa, ) start from the last to the first of the word. The function compare the two underlying letters regardless of case. (To do this I have a home-made lowcase function that will convert all the letters to lower case first prior the comparing – the lowcase function is very simple, rather than explaining in-depth here, just look at the code lowcase.cpp under the Project section.). The following diagram summarise the isPalindrome function logic.

Acpp5p10Pic1

See the Project section for the full code for isPalindrome.

The Project

Wrapping up all the source and header files here all in one place.

Acpp5p10MgntTree

Source File List

Header File List

Source Files

main.cpp

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

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

  // Print longest palindrome (take first observed)
  cout << "\nThe (first observed) longest palindrome is:\n"
       << findLongest(palindromes) << endl;

  return 0;
}

findLongest.cpp

#include <string>
#include <vector>

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

string findLongest(const vector<string>& words)
{
  string longestWord;
  for (vector<string>::const_iterator i = words.begin(); i != words.end(); ++i) {
    if ( i->size() > longestWord.size() )
      longestWord = *i;
  }
  return longestWord;
}

isPalindrome.cpp

#include <string>
#include "lowcase.h"

using std::string;

bool isPalindrome(const string& s)
{

  string word = lowcase(s);

  string::const_iterator a = word.begin();
  string::const_iterator b = word.end() - 1;

  while ( a <= b && a != word.end()) {
    if ( *a != *b )
      return false;
    ++a;
    --b;
  }
  return true;
}

lowcase.cpp

#include <string>
#include <cctype>

using std::string;
using std::tolower;

string lowcase(const string& s)
{
    string ret;
    for (string::size_type i = 0; i != s.size(); ++i)
    {
        ret.push_back(tolower(s[i]));
    }
    return ret;
}

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 iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Header Files

findLongest.h

#ifndef GUARD_FINDLONGEST_H
#define GUARD_FINDLONGEST_H

#include <string>
#include <vector>

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

#endif // GUARD_FINDLONGEST_H

isPalindrome.h

#ifndef GUARD_ISPALINDROME_H
#define GUARD_ISPALINDROME_H

#include <string>

bool isPalindrome(const std::string&);

#endif // GUARD_ISPALINDROME_H

lowcase.h

#ifndef GUARD_LOWCASE_H
#define GUARD_LOWCASE_H

#include <string>

std::string lowcase(const std::string&);

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

The program allows us to enter a list of words, and automatically display the palindromes (if any), followed by the longest palindrome.

bib good Morning bob dad Abba
Hello Deed Civic Solos
Redder Kelly DEIfied rOtaToR
^Z

These are the palindromes identified:
bib
bob
dad
Abba
Deed
Civic
Solos
Redder
DEIfied
rOtaToR

The (first observed) longest palindrome is:
DEIfied

As expected, the determination of palindromes is regardless of upper / lower case letters.

Further Readings

Purely out of curosity, palindrome applies not only to words, but also to phrases. For instance, the following phrases read the same in both direction.

(Reference: http://www.highlightpress.com.au/list-of-palindromes.html)

  • Able I was ere I saw Elba
  • Ah, Satan sees Natasha
  • A man, a plan, a canal: Panama
  • Do geese see God?
  • Live not on evil
  • Murder for a jar of red rum
  • Never odd or even
  • No, it is opposition

What about, to write a C++ program to determine palindrome sentences? That would be interesting.

I guess the algorithm would be just a matter of:

  1. Using the standard C++ getline function to read and parse in the whole sentences instead of just words.
  2. Removing all the special characters such as punctuations and empty spaces within the sentences.
  3. Converting all letters to lower cases.
  4. Applying the isPalindrome function against the newly formatted sentences. (i.e. treat the formatted sentences as “words”)

Something for later maybe!

Reference

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

Accelerated C++ Solution to Exercise 5-9

Exercise 5-9

Write a program to write the words in the input that do not contain any uppercase letters followed by words that contain one or more uppercase letters.

Solution

To clarify, the objective of this exercise is to:

  • read in a list of words
  • print the words that are all pure lower case.
  • print the words that contain at least one upper case letter.

To do this, we will need to:

  1. Use the usual while/cin/push_back method to read in a list of words.
  2. Create a function hasUpcaseLetters to determine whether a word contains any upper case letters at all.
  3. If word contains no upper case letters, append to vector<string> allLowcaseLetterWords.
  4. Otherwise if word contains at least one upper case letters, append to vector<string> someUpcaseLetterWords.
  5. (Optional) re-use the home-made function vcout to print the two word lists to the console output.

The Project

These are the files that I use. The main program should sum up the logic job flow.

Acpp5p9MgntTree

 

Source File List

Header File List

Source Files

main.cpp

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

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

int main()
{
    string word;
    vector<string> allLowcaseLetterWords;
    vector<string> someUpcaseLetterWords;

    // Populate vectors
    while (cin >> word) {
        if (hasUpcaseLetters(word))
            someUpcaseLetterWords.push_back(word);
        else
            allLowcaseLetterWords.push_back(word);
    }

    // Print words with at least 1 upper case letter
    cout << "\nThese words contain at least one upper case letter: " << endl;
    vcout(someUpcaseLetterWords);

    // Print pure lower case words
    cout << "\nThese words are pure lower case letters: " << endl;
    vcout(allLowcaseLetterWords);

    return 0;
}

hasUpcaseLetters.cpp

#include <cctype>  // isupper
#include <string>  // string

using std::isupper;
using std::string;

bool hasUpcaseLetters(const string& aWord)
{
    for (string::const_iterator i = aWord.begin(); i != aWord.end(); ++i) {
        if (isupper(*i))
            return true;
    }
    return false;
}

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 iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Header Files

hasUpcaseLetters.h

#ifndef GUARD_HASUPCASELETTERS_H
#define GUARD_HASUPCASELETTERS_H

#include <string>

bool hasUpcaseLetters(const std::string&);

#endif // GUARD_HASUPCASELETTERS_H

vcout.h

#ifndef GUARD_HASUPCASELETTERS_H
#define GUARD_HASUPCASELETTERS_H

#include <string>

bool hasUpcaseLetters(const std::string&);

#endif // GUARD_HASUPCASELETTERS_H

Test Result

A simple test shows the program works as expected.

Apple
apple
APPLE
aPpLe
applE
orange
oRange
ORANGE
orangE
^Z

These words are pure lower case letters:
apple
orange

These words contain at least one upper case letter:
Apple
APPLE
aPpLe
applE
oRange
ORANGE
orangE

Reference

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

Accelerated C++ Solution to Exercise 5-8

Exercise 5-8

In the hcat function from S5.8.3/95, what would happen if we defined s outside the scope of the while? Rewrite and execute the program to confirm your hypothesis.

Solution

Note: the original hcat function may be found in my Solution to Exercise 5-0 (Part 3/3). The objective of this exercise is to understand what may happen should we vary the hcat function a little bit.

In short, defining the string s outside the while loop will cause problems for certain horizontal concatenation scenarios (this will explained shortly below). It is however ok to define that string s outside the while loop, as long as we also add a one-line statement inside the while loop (this will also be explained shortly below).

Potential Problem

This is what the hcat function looks like if we simply move the string s outside (or just before) the while loop.

Acpp5p8BuggyCode

Assuming we wish to use the hcat function to concatenate the following (left and right) vectors:

Acpp5p8LeftRight

When the hcat function is invoked, the following tables summarise what happens:

Acpp5p8BuggyInitialization

Acpp5p8BuggyWhileLoop

Note that at the beginning of the second loop, because we did not re-initialise the string s, it causes the the s.size() to become larger than width1 (which is the maximum length of the longest string element within the left vector). This effectively results in negative string length when we apply the s += string(width1 – s.size(), ‘ ‘). The C++ implementation will likely bump into a string length error – highlighted in red.

Below shows what happens if we attempt to run this code as it is.

Acpp5p8TestBuggy

Acpp5p8TestBuggy2

i.e. the program crashes as a result of negative string length. This can be fixed easily however – read on!

Resolution

To fix that string length error as described above, simply add a one-line statement within the while loop to re-initialise the string s at the beginning of each loop.

Acpp5p8CorrectedCode

Again, assuming we wish to use the hcat function to concatenate the following (left and right) vectors:

Acpp5p8LeftRight

When the hcat function is invoked, the following tables summarise what happens:

Acpp5p8CorrectedInitialization

Acpp5p8CorrectedWhileLoop

Below shows what happens if we attempt to run this corrected code – it should run smoothly as expected.

Acpp5p8TestCorrect

The Project

To wrap up the source and header files that I use to test my codes.

Acpp5p8MgntTree

C++ Source File List

C++ Header File List

C++ Source Files

main.cpp

#include <iostream>  // cin, cout, endl, getline
#include <vector>    // vector
#include <string>    // string
#include "frame.h"   // width, frame
/*#include "vcat.h"    // vcat */
#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 line1;            // line
    vector<string> para1;    // paragraph
    cout << "define vector<string> para1 below..." << endl;
    // read multiple lines to make a paragraph
    while (getline(cin, line1))
        para1.push_back(line1);
    cin.clear();

    string line2;            // line
    vector<string> para2;    // paragraph
    cout << "define vector<string> para2 below..." << endl;
    // read multiple lines to make a paragraph
    while (getline(cin, line2))
        para2.push_back(line2);
    cin.clear();

    cout << "-----------------------------------------------------\n"
            "Display: hcat(para1, para2)                          \n"
            "-----------------------------------------------------\n";
    vcout(hcat(para1, para2));

    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>::size_type i = 0; i != v.size(); ++i)
        maxlen = max(maxlen, v[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>::size_type i = 0; i != v.size(); ++i)
        ret.push_back("* " + v[i] + string(maxlen - v[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>::size_type i = 0, j = 0;

    string s;
    // continue until we've seen all rows from both pictures
    while (i != left.size() || j != right.size())
    {
        // construct new string to hold characters from both pictures
        //string s;
        s = "";

        // copy a row from the left-hand side, if there is one
        if (i != left.size())
            s = left[i++];

        // pad to full width
        s += string(width1 - s.size(), ' ');

        // copy a row from the right-hand side, if there is one
        if (j != right.size())
            s += right[j++];

        // add s to the picture we are creating
        ret.push_back(s);
    }

    return ret;
}

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 iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

C++ Header Files

frame.h

#ifndef GUARD_FRAME_H
#define GUARD_FRAME_H

#include <string>
#include <vector>

std::string::size_type width(const std::vector<std::string>&);
std::vector<std::string> frame(const std::vector<std::string>&);

#endif // GUARD_FRAME_H

hcat.h

#ifndef GUARD_HCAT_H
#define GUARD_HCAT_H

#include <string>
#include <vector>

std::vector<std::string> hcat(const std::vector<std::string>&, const std::vector<std::string>&);

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

Conclusion

For the hcat function to work, we must re-initialise the string s at the beginning of each loop, as illustrated above.

Reference

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

Accelerated C++ Solution to Exercise 5-7

Exercise 5-7

Given the implementation of frame in S5.8.1/93, and the following code fragment

vector<string> v;
frame(v);

describe what happens in this call. In particular, trace through how both the width function and the frame function operate. Now, run this code. If the results differ from your expectations, first understand why your expectations and the program differ, and then change one to match the other.

Solution

The frame function has a return type of vector<string>. To “frame” the vector<string> v means to pad all the string elements within v to the full optimum width as defined by the width function. (i.e. the length of the longest string element in v).

My expectation of running this code fragment:

  1. The first statement of the code fragment creates an empty vector<string> v.
  2. The second statement of the code fragment attempts to frame this empty vector<string> v.
  3. When we apply frame(v), the width function returns a maxlen of 0 (i.e. the initialised maxlen value) – i.e. implying no elements in v.
  4. The frame function by default however, always return a top and bottom border of four asterisks (*). So even though the for loop within the frame function processes an empty vector<string> v, at a minimum, frame(v) should return the top and bottom borders. i.e. element 0 contains “****”, and element 1 contains “****”. This is it!

If we however populate the vector<string> v with some elements, the frame function should behave as demonstrated in the text book Chapter 5, or Solution to Exercise 5-0 (Part 3/3). i.e. equal length string elements with width of at least 5. e.g. if vector<string> v contains just one string element “a”, then,  frame(v) will return:

  • element 0: “*****”
  • element 1:”* a *”   (note there is a space around the string element)
  • element 2: “*****

Test Program

Though we have used the frame function multiple times in the previous exercises already, for completeness sake I shall include my test program here and run a couple of tests, for prove of concept purposes – to confirm the test result agrees with my expectation.

main.cpp

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

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

string::size_type width(const vector<string>& v)
{
    string::size_type maxlen = 0;
    for(vector<string>::size_type i = 0; i != v.size(); ++i)
        maxlen = max(maxlen, v[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>::size_type i = 0; i != v.size(); ++i)
        ret.push_back("* " + v[i] + string(maxlen - v[i].size(), ' ') + " *");

    // write the bottom border
    ret.push_back(border);

    return ret;
}

int main()
{
    string s;            // line
    vector<string> v;    // paragraph
    while (getline(cin, s))
        v.push_back(s);

    vector<string> framedV = frame(v);

    for (vector<string>::const_iterator iter = framedV.begin();
         iter != framedV.end(); ++iter)
    {
        cout << (*iter) << endl;
    }

    return 0;
}

Test 1 – empty vector<string> v

As expected, if we frame an empty vector<string> v, by default the frame function should return the top and bottom border at the minimum default width of four asterisks (*).

^Z
****
****

Test 2 – non-empty vector<string> v

If we frame a non-empty vector<string> v, the output should be just as described in Chapter 5 – equal length string elements, with the width determined by the longest string (line) element.

This is
a test
over over
^Z
*************
* This is   *
* a test    *
* over over *
*************

Let’s do one more. Let’s verify our expectation if we only submit a string element “a”.

a
^Z
*****
* a *
*****

Bingo!

Reference

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

Accelerated C++ Solution to Exercise 5-6

Exercise 5-6

Rewrite the extract_fails function from S5.1.1/77 so that instead of erasing each failing student from the input vector students, it copies the records for the passing students to the beginning of students, and then uses the resize function to remove the extra elements from the end of students. How does the performance of this version compare with the one in S5.1.1/77?

Solution

The original (version 2) extract_fail function in the text book S5.1.1/77 looks like this – it uses the vector<XXX>::erase function.

{
    Student_group fail;
    Student_group::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;
}

Note that I have used the technique developed from my Solution to Exercise 5-4, in which all the vector<Student_info> are replaced by Student_group, using the C++ typedef. (Just trust me for now there is a typdef somewhere else that defines Student_group) I believe it makes sense to build on what we have learnt!

The newly “re-written” function will look like this it uses a combination of vector<XXX>::insert and vector<XXX>::resize functions.

Student_group extract_fails_v2_5p6(Student_group& students)
{
    Student_group fail;
    typedef Student_group::size_type VecSize;
    VecSize countPass = 0;

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

    return fail;
}

If after skimping through this new code and you fully understand the concepts / what’s going on, then congratulation you are done!

From a series of tests the new version happens to take 50% more time than the original version (when reaching around 10,000 lines of input) – performance results can be found at the bottom of the page under the Test Result section.

If you however would like to know more in details, such as how I derive this new code logic, then read on!

Code Logic – The insert/resize Method

The way I derive the eventual code was simply doing some sketches on paper (In face this is how I usually solve problems – making sketches and pictures!). Below shows the diagrams that I drawn – essentially I started with a hypothetical example and just work my way through using logic. Some notes:

  • The countPass is a counter to keep track of the number of passing students – this will be used later on to feed the vector<XXX>::resize function.
  • The i, is just an incrementing variable (our good old friend), to facilitate a while loop.

Acpp5p6Pic1a

Acpp5p6Pic1b

Acpp5p6Pic2a

Acpp5p6Pic2b

Have we reached the end of the vector? (yes)

Acpp5p6Pic3a

Use the resize function to keep only the passing students in vector<Student_info> students.

Acpp5p6Pic3b

And these are the final output!

Acpp5p6Pic3c

An Important Learning – iterator

This exercise has exposed an interesting fact: iterator does NOT work when the underlying vector changes size! i.e. the following code will not work (even though it looks correct). One must use vector indexing instead! (I spent an hour debugging this – a hard lesson learnt!). Must be a feature of vector iterator vs vector index.

Student_group extract_fails_v2_5p6(Student_group& students)
{
    Student_group fail;
    Student_group::iterator i = students.begin();
    Student_group::size_type countPass = 0;

    // invariant: elements [0,i) of students represent passing grades
    while (i != students.end())
    {
        if (fgrade(*i))
            fail.push_back(*i);
        else
        {
            students.insert(students.begin(), *i);
            ++countPass;
            ++i;
        }
        ++i;
    }
    students.resize(countPass);

    return fail;
}

The Project

Here are the complete set of header and source files that enable me to perform the test.

Source File List

Header File List

Source Files

main.cpp

#include <iostream>
#include <iomanip>
#include <ios>
#include <ctime>
#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;
using std::setprecision;
using std::streamsize;

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 and time-stamp it!
    clock_t startTime = clock();
    Student_group students_failed = extract_fails_v2(students);
    /* Student_group students_failed = extract_fails_v2_5p6(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;

    // Uncomment the following block to display passing and failing students
    /*
    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.cpp

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

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

// Required by Exercise 5-6
Student_group extract_fails_v2_5p6(Student_group& students)
{
    Student_group fail;
    typedef Student_group::size_type VecSize;
    VecSize countPass = 0;

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

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

Student_group extract_fails_v2(Student_group&);
Student_group extract_fails_v2_5p6(Student_group&);

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

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

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

Just simply amend the following line in the main() program accordingly for test purposes.

Student_group students_failed = extract_fails_v2(students);
/* Student_group students_failed = extract_fails_v2_5p6(students); */

Performance Comparison

I’ve run a few tests and recorded the job run time for the extract_fail step. from this it looks like the insert/resize method is actually slower than the erase method. But then, I guess it depends on the input file – i.e. depending on the ratio of passing students to failing students, the sequence of the passing and failing students, and potentially other factors.

v2 (erase) v2_5p6 (insert/resize)
10 lines 0.001 seconds 0.000 seconds
100 lines 0.003 seconds 0.004 seconds
1,000 lines 0.156 seconds 0.212 seconds
10,000 lines 9.79 seconds 16.6 seconds

Reference

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

Accelerated C++ Solution to Exercise 5-5

Exercise 5-5

Write a function named center(const vector<string>&) that returns a picture in which all the lines of the original picture are padded out to their full width, and the padding is as evenly divided as possible between the left and right sides of the picture. What are the properties of pictures for which such a function is useful? How can you tell whether a given picture has these properties?

Solution

When I first saw this question, straight away it reminded me of the frame function that the author built in Chapter 5 / my Solution to Exercise 5-0 (Part 3/3). The original frame function effectively pad all the strings with empty spaces, making all strings equal width and left aligned, and put a frame around it to make it “box-like” when we display the vector<string> line by line vertically – like a formatted article.

Also recall that in my Solution to Exercise 5-1 (about building a permuted index page), I modified the frame function so that it takes on additional parameters regarding whether the padding should be left-aligned or right-aligned. So instead of creating a brand new function center(const vector<string>&), I may as well reuse the frame function and enhance it so that we have an extra option to center-aligned.

In this post I shall describe how I modify the frame function to allow user to center-align the vector<string> “picture text”.

Algorithm

We know what the algorithm looks like for left-align and right-align for the frame function from Solution to Exercise 5-1. The algorithm for center-aligned is very similar. i.e. we use the width function to identify the max length of the string (within the vector<string>). We then compute how many padding spaces are required on both (left and right) sides of each individual text string – the padding on the left should be more or less the same as the right. The diagram below essentially summarises the equations in computing the various lengths required.

Acpp5p5Pic1

These equations are reflected in the enhanced frame.cpp code below.

The Project

Let me wrap up the whole project here – we should be able to figure out how the enhanced frame function works, and how we can easily use it. (Note that I have reused the knowledge / experience gained from the previous exercises in Chapter 5).

(The enhanced frame function is the answer to the exercise – the other codes are wrapped together for demonstration purposes.)

Acpp5p5MgntTree

  • main.cpp
  • frame.h
  • frame.cpp
  • read_lines.h
  • read_lines.cpp
  • vout.h
  • vout.cpp

Source and Header Files

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include "read_lines.h"
#include "frame.h"
#include "vcout.h"

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

int main()
{

    // read lines via standard console input and append to article
    vector<string> article = read_lines();

    // padded each line of the article
    vector<string> paddedArticle = frame(article,"center",'*');

    // display the now padded article
    vcout(paddedArticle);

    return 0;
}

frame.h

#ifndef GUARD_FRAME_H
#define GUARD_FRAME_H

#include <string>
#include <vector>

std::string::size_type width(const std::vector<std::string>&);
std::vector<std::string> frame(const std::vector<std::string>&, const std::string&, const char);

#endif // GUARD_FRAME_H

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>::size_type i = 0; i != v.size(); ++i)
        maxlen = max(maxlen, v[i].size());
    return maxlen;
}

vector<string> frame(const vector<string>& v, const string& align, char c)
{
    vector<string> ret;

    typedef string::size_type stringSize;
    stringSize  maxlen = width(v);
    string symbol(1, c);
    string border(maxlen + 4, c);

    // write the top border
    ret.push_back(border);

    // write each interior row, bordered by an asterisk and a space
    for (vector<string>::size_type i = 0; i != v.size(); ++i)
        if (align == "left")
            ret.push_back(symbol + " " + v[i] + string(maxlen - v[i].size(), ' ') + " " + symbol);
        else if (align == "right")
            ret.push_back(symbol + " " + string(maxlen - v[i].size(), ' ') + v[i]  + " " + symbol);
        else if (align == "center")
        {
            stringSize leftPadSize = (maxlen - v[i].size() ) / 2 ;
            stringSize midLineSize = v[i].size();
            stringSize rightPadSize = maxlen - leftPadSize - midLineSize;
            string padLine = symbol + " " + string(leftPadSize, ' ')
                             + v[i] + string(rightPadSize, ' ') + " " + symbol;
            ret.push_back(padLine);
        }

    // write the bottom border
    ret.push_back(border);

    return ret;
}

read_lines.h

#ifndef GUARD_READ_LINES_H
#define GUARD_READ_LINES_H

#include <string>
#include <vector>

std::vector<std::string> read_lines();

#endif // GUARD_READ_LINES_H

read_lines.cpp

#include <string>    // string
#include <vector>    // vector
#include <iostream>   // cin, getline

using std::string;
using std::vector;
using std::cin;
using std::getline;

// Read lines and return the line collection
vector<string> read_lines()
{
    string line;
    vector<string> ret;
    while (getline(cin, line))
        ret.push_back(line);

    return ret;
}

vout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

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

#endif // GUARD_VCOUT_H

vout.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 iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Test Program

Test 1 – Center Align

Update this line in main program:

vector<string> paddedArticle = frame(article,"center",'*');

Test Result:

this is an
example
to
illustrate
framing
^Z
**************
* this is an *
*  example   *
*     to     *
* illustrate *
*  framing   *
**************

Test 2 – Left Align

Update this line in main program:

vector<string> paddedArticle = frame(article,"left",'*');

Test Result:

this is an
example
to
illustrate
framing
^Z
**************
* this is an *
* example    *
* to         *
* illustrate *
* framing    *
**************

Test 3 – Right Align

Update this line in main program:

vector<string> paddedArticle = frame(article,"right",'*');

Test Result:

this is an
example
to
illustrate
framing
^Z
**************
* this is an *
*    example *
*         to *
* illustrate *
*    framing *
**************

Reference

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

Accelerated C++ Solution to Exercise 5-4

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.

Acpp5p4MgntTree

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

Accelerated C++ Solution to Exercise 5-3

Exercise 5-3

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

Solution

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

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

The Project

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

Acpp5p3MgntTree

main.cpp

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

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

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

int main()
{

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

    Student_group students;
    Student_info record;

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

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

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

    cout << endl;

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

    cout << endl;

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

    return 0;
}

extract_fails_v3.h

#ifndef GUARD_EXTRACT_FAILS_V3_H
#define GUARD_EXTRACT_FAILS_V3_H

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

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

#endif // GUARD_EXTRACT_FAILS_V3_H

extract_fails_v3.cpp

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

using std::vector;

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

extract_fails_v4.h

#ifndef GUARD_EXTRACT_FAILS_V4_H
#define GUARD_EXTRACT_FAILS_V4_H

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

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

#endif // GUARD_EXTRACT_FAILS_V4_H

extract_fails_v4.cpp

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

using std::list;

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

grade.h

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

using std::list;

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

grade.cpp

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

using std::domain_error;
using std::vector;

// definitions for the grade functions from S4.1/52, S4.1.2/54, S4.2.2/63

// compute a student's overall grade from midterm and final exam
// grades and homework grade (S4.1/52)
double grade(double midterm, double final, double homework)
{
    return 0.2 * midterm + 0.4 * final + 0.4 * homework;
}

// compute a student's overall grade from midterm and final exam grades
// and vector of homework grades.
// this function does not copy its argument, because median (function) does it for us.
// (S4.1.2/54)
double grade(double midterm, double final, const vector<double>& hw)
{
    if (hw.size() == 0)
        throw domain_error("student has done no homework");
    return grade(midterm, final, median(hw));
}

// this function computes the final grade for a Student_info object
// (S4.2.2/63)
double grade(const Student_info& s)
{
    return grade(s.midterm, s.final, s.homework);
}

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

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

#endif // GUARD_MEDIAN_H

median.cpp

// source file for the median function
#include <algorithm>
#include <stdexcept>
#include <vector>

using std::domain_error;
using std::sort;
using std::vector;

// compute the median of a vector<double>
double median(vector<double> vec)
{
    typedef vector<double>::size_type vec_sz;

    vec_sz size = vec.size();
    if (size == 0)
        throw domain_error("median of an empty vector");

    sort(vec.begin(),vec.end());

    vec_sz mid = size/2;

    return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];
}

Student_info.h

#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

// Student_info.h
#include <iostream>
#include <string>
#include <vector>

struct Student_info
{
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};

bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);

#endif // GUARD_STUDENT_INFO_H

Student_info.cpp

#include "Student_info.h"

using std::istream;
using std::vector;

// we are interested in sorting the Student_info object by the student's name
bool compare(const Student_info& x, const Student_info& y)
{
    return x.name < y.name;
}

// read student's name, midterm exam grade, final exam grade, and homework grades
// and store into the Student_info object
// (as defined in S4.2.2/62)
istream& read(istream& is, Student_info& s)
{
    // read and store the student's name and midterm and final exam grades
    is >> s.name >> s.midterm >> s.final;

    // read and store all the student's homework grades
    read_hw(is, s.homework);
    return is;
}

// read homework grades from an input stream into a vector<double>
// (as defined in S4.1.3/57)
istream& read_hw(istream& in, vector<double>& hw)
{
    if (in)
    {
        // get rid of previous contents
        hw.clear();

        // read homework grades
        double x;
        while (in >> x)
            hw.push_back(x);

        // clear the stream so that input will work for the next student
        in.clear();
    }
    return in;
}

Test Program and Results

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

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

We shall see that both tests yield the same result.

Test 1 – vector based version

Amend the #include line and the typdef line accordingly.

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

Test 1 Result

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

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

Test 2 – list based version

Amend the #include line and the typdef line accordingly.

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

Test 2 Result

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

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

Reference

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

Accelerated C++ Solution to Exercise 5-2

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.

Acpp5p2MgntTree

  • 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