Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
Solutions
to selected exercises can be found in the electronic document The Thinking
in C++ Volume 2 Annotated Solution Guide, available for a small fee from www.MindView.net.
1. Write a test program using the TestSuite Framework for the
standard vector class that thoroughly tests the following member
functions with a vector of integers: push_back( ) (appends
an element to the end of the vector), front( ) (returns the
first element in the vector), back( ) (returns the last
element in the vector), pop_back( ) (removes the last
element without returning it), at( ) (returns the element in a
specified index position), and size( ) (returns the number of
elements). Be sure to verify that vector::at( ) throws a std::out_of_range
exception if the supplied index is out of range.
2. Suppose you are asked to develop a class named Rational
that supports rational numbers (fractions). The fraction in a Rational
object should always be stored in lowest terms, and a denominator of zero is an
error. Here is a sample interface for such a Rational class:
//: C02:Rational.h {-xo}
#ifndef RATIONAL_H
#define RATIONAL_H
#include <iosfwd>
class Rational {
public:
Rational(int numerator = 0, int denominator = 1);
Rational operator-() const;
friend Rational operator+(const Rational&,
const Rational&);
friend Rational operator-(const Rational&,
const Rational&);
friend Rational operator*(const Rational&,
const Rational&);
friend Rational operator/(const Rational&,
const Rational&);
friend std::ostream&
operator<<(std::ostream&, const
Rational&);
friend std::istream&
operator>>(std::istream&, Rational&);
Rational& operator+=(const Rational&);
Rational& operator-=(const Rational&);
Rational& operator*=(const Rational&);
Rational& operator/=(const Rational&);
friend bool operator<(const Rational&,
const Rational&);
friend bool operator>(const Rational&,
const Rational&);
friend bool operator<=(const Rational&,
const Rational&);
friend bool operator>=(const Rational&,
const Rational&);
friend bool operator==(const Rational&,
const Rational&);
friend bool operator!=(const Rational&,
const Rational&);
};
#endif // RATIONAL_H ///:~
Write a complete
specification for this class, including preconditions, postconditions, and
exception specifications.
3. Write a test using the TestSuite framework that thoroughly
tests all the specifications from the previous exercise, including testing
exceptions.
4. Implement the Rational class so that all the tests from
the previous exercise pass. Use assertions only for invariants.
5. The file BuggedSearch.cpp below contains a binary search
function that searches the range [beg, end) for what. There are
some bugs in the algorithm. Use the trace techniques from this chapter to debug
the search function.
//: C02:BuggedSearch.cpp {-xo}
//{L} ../TestSuite/Test
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <fstream>
#include "../TestSuite/Test.h"
using namespace std;
// This function is only one with bugs
int* binarySearch(int* beg, int* end, int what) {
while(end - beg != 1) {
if(*beg == what) return beg;
int mid = (end - beg) / 2;
if(what <= beg[mid]) end = beg + mid;
else beg = beg + mid;
}
return 0;
}
class BinarySearchTest : public TestSuite::Test {
enum { SZ = 10 };
int* data;
int max; // Track largest number
int current; // Current non-contained number
// Used in notContained()
// Find the next number not contained in the array
int notContained() {
while(data[current] + 1 == data[current + 1])
++current;
if(current >= SZ) return max + 1;
int retValue = data[current++] + 1;
return retValue;
}
void setData() {
data = new int[SZ];
assert(!max);
// Input values with increments of one. Leave
// out some values on both odd and even indexes.
for(int i = 0; i < SZ;
rand() % 2 == 0 ? max += 1 : max += 2)
data[i++] = max;
}
void testInBound() {
// Test locations both odd and even
// not contained and contained
for(int i = SZ; --i >=0;)
test_(binarySearch(data, data + SZ, data[i]));
for(int i = notContained(); i < max;
i = notContained())
test_(!binarySearch(data, data + SZ, i));
}
void testOutBounds() {
// Test lower values
for(int i = data[0]; --i > data[0] - 100;)
test_(!binarySearch(data, data + SZ, i));
// Test higher values
for(int i = data[SZ - 1];
++i < data[SZ -1] + 100;)
test_(!binarySearch(data, data + SZ, i));
}
public:
BinarySearchTest() { max = current = 0; }
void run() {
setData();
testInBound();
testOutBounds();
delete [] data;
}
};
int main() {
srand(time(0));
BinarySearchTest t;
t.run();
return t.report();
} ///:~