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

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.

The Project

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

Source File List

• main.cpp
• vcout.cpp

Header File List

• vcout.h

Source Files

main.cpp

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

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

int main()
{
  string word;               // a word

  vector<string> wordCollectionA;    // a collection of words
  cout << "Define vector<string> wordCollectionA below..." << endl;
  // Populate wordCollectionA.
  while (cin >> word)
    wordCollectionA.push_back(word);
  cin.clear();

  vector<string> wordCollectionB;    // another collection of words
  cout << "Define vector<string> wordCollectionB below..." << endl;
  // Populate wordCollectionB.
  while (cin >> word)
    wordCollectionB.push_back(word);
  cin.clear();

  // Test appending using the push_back method
  vector<string> baseForPushBack = wordCollectionA;
  for (vector<string>::const_iterator i = wordCollectionB.begin();
       i != wordCollectionB.end(); ++i)
    baseForPushBack.push_back(*i);

  // Test appending using the insert method
  vector<string> baseForInsert = wordCollectionA;
  baseForInsert.insert(baseForInsert.end(), wordCollectionB.begin(), wordCollectionB.end());

  // Test appending using the copy method
  vector<string> baseForCopy = wordCollectionA;
  copy(wordCollectionB.begin(), wordCollectionB.end(),
       back_inserter(baseForCopy) );

  // Display results
  cout << "Append wordCollectionB to wordCollectionA with push_back method..."
      << endl;
  vcout(baseForPushBack);
  cout << "Append wordCollectionB to wordCollectionA with insert method..."
      << endl;
  vcout(baseForInsert);
  cout << "Append wordCollectionB to wordCollectionA with copy method..."
      << endl;
  vcout(baseForCopy);

  return 0;
}

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

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

Result

The test demonstrates that all 3 methods are equivalent – they produce the same result and serve the same purpose. i.e. appending elements to the base container.

Imagine:

• We have a vector<string> wordCollectionA container that contains the string elements “Item0” and “Item1”.
• We have a vector<string> wordCollectionB container that contains the string elements “Item2”, “Item3” and “Item4”.
• Appending the elements in wordCollectionB to the (base) wordCollectionA should result in A containing “Item0”, “Item1”, “Item2”, “Item3” and “Item4”.

Define vector<string> wordCollectionA below...
Item0
Item1
^Z
Define vector<string> wordCollectionB below...
Item2
Item3
Item4
^Z
Append wordCollectionB to wordCollectionA with push_back method...
Item0
Item1
Item2
Item3
Item4
Append wordCollectionB to wordCollectionA with insert method...
Item0
Item1
Item2
Item3
Item4
Append wordCollectionB to wordCollectionA with copy method...
Item0
Item1
Item2
Item3
Item4

Reference

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

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.

Source File List

• main.cpp
• findLongest.cpp
• hasAscender.cpp
• hasDescender.cpp
• vcout.cpp

Header File List

• findLongest.h
• hasAscender.h
• hasDescender.h
• vcout.h

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

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.

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.

Source File List

• main.cpp
• findLongest.cpp
• isPalindrome.cpp
• lowcase.cpp
• vcout.cpp

Header File List

• findLongest.h
• isPalindrome.h
• lowcase.h
• vcout.h

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

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.

 

Source File List

• main.cpp
• hasUpcaseLetters.cpp
• vcout.cpp

Header File List

• hasUpcaseLetters.h
• vcout.h

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

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.

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

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

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.

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.

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

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

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

The Project

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

C++ Source File List

• main.cpp
• frame.cpp
• hcat.cpp
• vcout.cpp

C++ Header File List

• frame.h
• hcat.h
• vcout.h

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

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

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.

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

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

And these are the final output!

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

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

Header File List

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

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

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.

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

• 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

Exercise 5-4

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

Solution

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

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

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

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

The Project

For completeness I shall include all the files here.

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

main.cpp

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

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

int main()
{

    Student_group students;
    Student_info record;

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

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

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

    cout << endl;

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

    cout << endl;

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

    return 0;
}

extract_fails.h

#ifndef GUARD_EXTRACT_FAILS_H
#define GUARD_EXTRACT_FAILS_H

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

Student_group extract_fails(Student_group&);

#endif // GUARD_EXTRACT_FAILS_H

extract_fails.cpp

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

// separate passing and failing student records
// derived from S5.5/85
Student_group extract_fails(Student_group& students)
{
    Student_group fail;
    Student_group::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

grade.h

#ifndef GUARD_GRADE_H
#define GUARD_GRADE_H

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

double grade(double, double, double);
double grade(double, double, const std::vector<double>&);
double grade(const Student_info&);
bool fgrade(const Student_info&);

#endif // GUARD_GRADE_H

grade.cpp

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

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

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

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

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

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

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

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

#endif // GUARD_MEDIAN_H

median.cpp

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

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

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

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

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

    vec_sz mid = size/2;

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

Student_info.h

#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

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

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

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

#endif // GUARD_STUDENT_INFO_H

Student_info.cpp

#include "Student_info.h"

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

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

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

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

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

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

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

Student_group.h

#ifndef GUARD_STUDENT_GROUP_H
#define GUARD_STUDENT_GROUP_H

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

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

#endif // GUARD_STUDENT_GROUP_H

Test Program and Results

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

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

We shall see that both tests yield the same result.

Test 1 – vector based version

Amend the Student_group.h accordingly (one-liner change).

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

Test 1 Result

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

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

Test 2 – list based version

Amend the Student_group.h accordingly (one-liner change).

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

Test 2 Result

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

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

Conclusion

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

Reference

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