Binary trees are complex but applicable to a wide range of problems, making their implementation with templates and inclusion in a library beneficial to application programmers. The same characteristics also apply to the template classes included in the C++ libraries introduced in the next section. In contrast, the Array class offers only modest benefits beyond fundamental or non-object arrays. However, the C++ libraries include an array class whose features elevate it far above fundamental arrays, and students should contrast it to the one described next.
Chapter 11 introduced the Array class primarily to demonstrate overloading the index operator: operator[]. Where C++'s fundamental, non-object arrays are always zero-indexed, instances of the Array class allow client programs to specify the array's upper and lower bounds: the lowest and highest legal index values. The class's constructor allocates an appropriately sized array on the heap, and the index operator translates the client's indexes into the underlying array indexes required to complete the operation. The initial Array class only stored one-byte characters, limiting its usefulness. Fortunately, the operations that translate Array indexes into fundamental C++ arrays are independent of the stored data, making the Array class amenable to a template implementation.
#include <stdexcept> // (a)
using namespace std;
template <class T>
class Array
{
private:
int lower; // (b)
int upper;
T* array; // (c)
public:
Array(int s, int e);
~Array() { delete[] array; }
T& operator[](int index); // (d)
T& at(int index); // (e)
int get_lower() { return lower; }
int get_upper() { return upper; }
int get_size() { return upper - lower + 1; }
};
|
template <class T>
Array<T>::Array(int l, int u) : lower(l), upper(u) // (f)
{
if (upper < lower)
throw invalid_argument("Upper must be >= lower");
array = new T[upper - lower + 1]{};
}
template <class T>
T& Array<T>::operator[](int index) // (g)
{
return array[index - lower];
}
template <class T>
T& Array<T>::at(int index) // (h)
{
if (index < lower || index > upper)
throw out_of_range("Index out of bounds");
return array[index - lower];
} |
Recall that we form an anagram by rearranging the letters in one phrase to form a second. So, given two phrases, the problem is to determine whether one is an anagram of the other. Anagrams typically consider only letters and perhaps digits, ignoring letter case, spaces, and punctuation. Chapter 8 introduced the anagram problem and demonstrated how to use strings, arrays, and functions. The following example takes a more direct, compact approach.
The programmed solution for the anagram problem discards non-letter characters and converts all letters to lowercase - the tolower function returns lowercase letters unmodified. The program benefits from the Array class's flexible boundaries by using the letters directly as indexes in the character-count arrays. The Chapter 8 version followed the same approach but burdened the application with the index mapping. This version reduces the application's complexity by shifting the mapping task to the Array class's operator[] or at functions, allowing the application to focus more on the problem.
#include <iostream>
#include <cstring>
#include <cctype>
#include <stdexcept>
#include "Array.h"
using namespace std;
int main()
{
const char* p1 = "To be or not to be: that is the question, whether " // (a)
"it's nobler in the mind to suffer the slings and arrows of "
"outrageous fortune.";
const char* p2 = "In one of the Bard's best-thought-of tragedies, "
"our insistent hero, Hamlet, queries on two fronts about how "
"life turns rotten.";
try
{
Array<int> a1('a', 'z'); // (b)
Array<int> a2('a', 'z');
for (size_t i = 0; i < strlen(p1); i++) // (c)
if (isalpha(p1[i]))
a1[tolower(p1[i])]++;
for (size_t i = 0; i < strlen(p2); i++)
if (isalpha(p2[i]))
a2[tolower(p2[i])]++;
for (int i = 'a'; i <= 'z'; i++)
cout << (char)i << '\t' << a1[i] << '\t' << a2[i] << endl; // (d)
for (int i = 'a'; i <= 'z'; i++)
if (a1[i] != a2[i])
{
cout << "NOT an anagram" << endl;
exit(0);
}
cout << a1.at(0) << endl; // (f) throws an exception
}
catch (invalid_argument ia) // (f)
{
cerr << ia.what() << endl;
}
catch (out_of_range oor)
{
cerr << oor.what() << endl;
}
cout << "Valid anagram" << endl;
return 0;
}