**Problem 1.** The following are code fragments for a table of strings,
which can hold up to 100 entries. Strings (we will call them
*values*) can be added, looked up and printed. Notice that
with such member functions, once a value is added, we cannot
tell from ``outside the table'' which position in the table it
occupies.

const int MAX_TABLE_SIZE = 100; // max capacity class StringTable { int size; // the number of actual entries string values [MAX_TABLE_SIZE]; public: //.... //.... void add( const string& new_val ); // add a value bool includes( const string& val ); // true if val occurs in the // table, false otherwise. void print(); // print all values }; void StringTable::add(const string& s){ if( size == MAX_TABLE_SIZE ){ // capacity exhausted -- signal error and abort } else values[ size++ ] = s; // add the value, } // increment the size

For the following problems, write the code of the required member functions using correct syntax for out-of-class definitions.

**(a)** The above code defines no constructors. Write one.

StringTable::StringTable( ) : size(0) { }

**(b)** Write the functions `includes(..)` and `print()` (make sure
you separate the strings you print).

bool StringTable::includes( const string& val ) { for( int i=0; i < size; i++ ) if( values[i] == val ) return true; return false; } void StringTable::print() { for( int i=0; i < size; i++ ) cout << values[i] << endl; }

**(c)** The following code reads words (words are separated
by whitespace, i.e. spaces, newlines and tabs) one by one, and
adds them to s StringTable.

ifstream f( "sometext.txt" ); string s; StringTable words; while( f >> s ) // f >> s fills s with a new word and returns true, // or fails (when at eof) and returns false words.add( s ); // now words contains all words from the file ... if( words.includes( "computer" ) ) cout << "Must read!"; else cout << "Don't bother."; ... words.print();

Modify the `add(..)` function so that a word is added if and only if
it doesn't occur in the StringTable already. Assuming this modification,
`words.print();` will print each word that occurs in `sometext.txt`
exactly once.

void StringTable::add(const string& s) { if( ! includes( s ) ){ // do only if s isn't there already if( size == MAX_TABLE_SIZE ){ // capacity exhausted -- signal error and abort } else values[ size++ ] = s; // add the value, increment the size } }

**(d)** Modify the class StringTable so that it keeps only one copy
of each added value (as in (c)), and also counts how many times it was
added. Modify `print()` so that it prints these counts. As a result,
`words.print();` in the above code will print each word that occurs
in `sometext.txt` and the number of times it occurs.

// Add to the private data members of class StringTable: int counters [ MAX_TABLE_SIZE ]; void StringTable::add(const string& s) { int index = 0; while( index < size && values[index] != s ) // look for s in values index++; // now either index == size or values[index] == s . if( index == size ){ if( size == MAX_TABLE_SIZE ){ // capacity exhausted -- signal error and abort } else{ values[ size ] = s; // add the value, increment the size counters[ size ] = 1; // first occurrence size++; } else { // s is already in the table, at index "index" counters[ index ] += 1; } } void StringTable::print() { for( int i=0; i < size; i++ ) cout << values[i] << " --> " << counters[i] << endl; }

**(e)** The original class StringTable will work for files of no more
than 100 words (in modifications (c) and (d), only *different* words count).
Suppose that the programmer who is going to use your code knows
approximately how many words will be in his file. Therefore, he would like to
be able to declare StringTables of various capacities (say, 20 or 3000 values).
If the capacity he specifies turns out to be too small, it is OK to let
`add(..)` fail with an error message, as before. With as few changes to the
code as possible, provide the programmer with this feature. Make sure that your
code doesn't leak memory.

**Hint:** You need to specify the desired initial capacity as a parameter
to the constructor. As per conditions of the problem, you need not change
that capacity after the table gets created.

const int DEFAULT_TABLE_SIZE = 100; class StringTable { int capacity; int size; // the number of actual entries string * values; // now a pointer to dyn. alloc. memory public: StringTable( int init_capacity = DEFAULT_TABLE_SIZE ); void add( const string& new_val ); // add a value bool includes( const string& val ); // true if val occurs in the // table, false otherwise. void print(); // print all values }; StringTable::StringTable( int init_cap ) : capacity( init_cap ), size( 0 ), values( new string[init_cap] ){ } StringTable::~StringTable() { delete[] values; } void StringTable::add(const string& s){ // ... if( size == capacity ){ // capacity exhausted -- signal error and abort } else{ values[ size ] = s; // ... } } // the rest is the same

**(f, extra credit)** Make the table expand itself, i.e. increase its capacity,
each time the current capacity is exhausted. Make the capacity grow by a pre-determined
number of value slots each time this happens (this extra growth can also be given
as a parameter to the constructor.

Left as an exercise. Implement it and test it.

**Problem 2.** Look at the following excerpts from an implementation
of `Fraction` and answer the questions below.

class Fraction { int num; int denom; public: Fraction( int n, int d ) : num(n), denom(d) { } // .... friend Fraction operator * ( const Fraction& , const Fraction & ); // .... }; Fraction operator * ( const Fraction & X, const Fraction & Y ){ return Fraction( X.num * Y.num, X.denom * Y.denom ); }

**(a)** Assuming this declaration, is the following legal?
If it is, describe its effect, if not, provide the fix needed
to make it legal.

Fraction arr_frac[ 100 ]; Illegal. This declaration needs to call the default Fraction constructor 100 times (for each element of the array), but the default constructor is not provided. In the presence of a non-default constructor, the default one is not generated. Fix: define a default constructor Fraction::Fraction( )

**(b)** List all member functions that are called as a result of
the following statements. Be sure to list **all** member functions,
including those that may be automatically generated by the compiler.
Also, make sure you consider the long-term effects as well as short-term
ones.

Fraction a( 1, 2 ), b( 1, 3 ); Fraction::Fraction(int,int) -- the constructor is called twice Fraction c = a * b; // makes c == 1/6 operator* calls Fraction::Fraction(int,int) to create a temporary to hold the product. Then the copy constructor, Fraction::Fraction( const Fraction& ), is called to construct c as a copy of that temporary. Some time afterwards the temporary will get destroyed by Fraction::~Fraction() . Notice: The overloaded assignment, Fraction::operator= (..) is NOT called. For that both LHS and RHS must be already existing objects, while here c is only being constructed.

**(c)** I want to write a function for adding Fractions that
avoids the overhead of creating temporary objects. Imagine code like this,
continuing the segment above:

Fraction a( 1, 2 ), b( 1, 3 ), d; fraction_sum( d, a, b ); // makes d == 5/6

I want my function `fraction_sum(..)` to fill in its first argument
with the sum of the other two arguments (naturally, I need to make this function
a `friend` of `Fraction`). Which of the following prototypes
is right for `fraction_sum(..)`? Specify what is wrong with the each
of the other prototypes.

void fraction_sum( const Fraction & res, const Fraction & x , const Fraction & y ); The first argument is const. So it cannot be changed by the function! Any assignment to res will cause a compilation error. void fraction_sum( Fraction res, Fraction x , Fraction y ); This function receives all three parameters by value, i.e. it will receive COPIES of d, a, b. Copying the last two arguments simply slows things down; but any changes made to res will be lost once the function returns, and will not affect d. void fraction_sum( Fraction & res, const Fraction & x, const Fraction & y ); This is correct, and avoids unnecessary copying of a, b. The first parameter is a reference, so d will be changed when res is assigned to. void fraction_sum( Fraction res, const Fraction & x, const Fraction & y ); The first parameter is passed by value, i.e. any changes to res will affect only the copy of d that res will refer to, not d itself. void fraction_sum( Fraction res, Fraction & x, Fraction & y ); Same problem, and the last two arguments are not protected from accidental assignment. Suppose you mistype and assign a new value to x instead of res. The compiler will not catch that error, unlike in the previous two examples.

**(d)** List all that is wrong (if anything) with the following two
implementations of the *unary minus*. The unary minus is what makes

x = -y;work for some Fractions

Fraction Fraction::operator - ( const Fraction X ) { return Fraction( - X ); } 1. The function calls itself -- infinite recursion. This crashes Macs, even in Debug mode. 2. This is a member function, so it already known one Fraction, the "this" instance on which it is called. Being a unary operator, it needs only one Fraction. Why X ? 3. Fraction X is passed by value -- copy constr. will be called. 4. and so on... Fraction& Fraction::operator - ( ) { return Fraction( -num, -denom ); } 1. This is mathematically wrong: -(1/2) is either (-1)/2 or 1/(-2), but NOT (-1)/(-2) 2. This function returns a reference to a local temporary Fraction. That object may be destroyed sooner than the reference is used, in which case the reference will be dangling. The only way to ensure the necessary lifespan of a local object when returning it from a function is to specify Fraction (not a reference to it!) as the return type. A good compiler will warn you about "returning a reference to a local".

**(e, extra)** Write all code required to make the following line legal
for some Fractions `c` and `b` :

c = 2 * b; You need to write a friend function (this cannot be done with a member -- why? Hence, add to the class definition: friend Fraction operator * ( int x, const Fraction& y ); Fraction operator * ( int x, const Fraction& y ) { return Fraction( x * y.num, y.denom ); }

(**extra**) List as many ways of making this work as you can think of.

Add a constructor that makes a Fraction out of int, so 2 becomes 2/1 : Fraction::Fraction( int x ) : num( x ), denom( 1 ) {} This constructor will be applied to 2 above, as a kind of an implicit conversion. Or make the Fraction::Fraction(int,int) take a second default argument: Fraction( int n, int d = 1 ); // the body is the same