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 x and y.
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