Code Review 4: Removing Limitations

Dynamic arrays, overloading of the array access operator, separating string table

Don't you just hate it when you're trying to save a few hours' worth of editing and suddenly you get a message box saying "Cannot save: Too many windows open." or some such nonsense? What is it? Unfortunately, it's a common occurrence--somebody who considers himself or herself a programmer hardcoded a fixed size array to store some important program resources. Then somebody found a problem during testing. The limitation probably caused a fault when the bounds were first overwritten. A bug appeared in the database, "The program GP-faulted when user tried to save a big document." Then another genius fixed it by adding a boundary test and putting up the message box. At least that's how I imagine it happening. As you can see, I don't think highly of code that has unreasonable limitations built-in. And with templates it's so easy to remove the unnecessary limits!

Let's first look around to see where in our program we managed to impose unreasonable limitations due to our ignorance of templates. There's one we have just created in MultiNode by arbitrarily limiting the number of children to 8. The whole symbol table is infested with limitations: the buffer for string is limited, the array of offsets is finite. Finally, the storage of variable values has an arbitrary limit imposed on it.

You might ask, "What's the likelihood of user hitting one of the limitations? Is it worth going into all this trouble in order to deal with such unlikely cases?" The answer is:

It is less trouble to use dynamic arrays than it is to deal with limitations.

Just think of all the error messages you'll have to display, the propagation of these errors (by the way, we'll deal with this topic separately later), the localization of message strings. Believe me, you don't want to do it.

Dynamic Array

Almost all cases of artificial limits can be solved by just one template--the dynamic array. Let's go together through its design and implementation. In the process you'll not only learn more about templates and operator overloading, but you'll also prepare yourself for the general-purpose dynamic vector from the Standard Library.

Let's first try to come up with a set of requirements for this data structure. As much as possible we would like the dynamic array to look just like an array. That means we would like to access its elements by indexing, both to read and to write. Adding new elements is a bit more tricky. For performance reasons, we don't want the array to check for bounds on every access (except in the debugging version) to see if it's necessary to extend the array. Second, we never actually need to add new elements at an arbitrary offset. In all our applications we keep adding elements to the end of the array. It would be tempting to just keep track of the last added element and have method Push to add and extend the array. Instead I decided to be a little more general and have a method Add that can add a new element at an arbitrary offset. That's because I want to be able to use pairs of synchronized arrays that share the same insertion index--we'll see an example in a moment.

One more thing: in many cases it makes sense to pre-fill the array with some default values. For instance, an array of pointers could be pre-filled with null pointers, integers could be preset to zero or minus one, enumerated types to some default value, etc. We'll store this default value in the dynamic array, so that we could use it to pre-fill the new pieces of the array when we grow it.

template <class T> class DynArray { enum { initDynArray = 8 }; public: explicit DynArray (T const valDefault); ~DynArray (); void Add (int i, T const val); T operator [] (int i) const; T & operator [] (int i); int InRange (int i) const { return i < _capacity; } private: void Grow (int i); T * _arr; int _capacity; // size of the array T const _valDefault; };

The line

T operator [] (int i) const;

is another example of operator overloading. Here we are overloading the array access operator [] (square brackets) in order to be able to access dynamic arrays just like regular arrays.

Here's how we can define a dynamic array of integers, add a value to it using Add, and retrieve it using array access.

DynArray<int> a (0); // dynamic array with 0 default value a.Add (3, 10); // add entry with value 10 at offset 3 int i = a [3]; // access it like a regular array

The compiler will translate the last line into the call to operator [], just like this:

int i = a.operator [] (3);

which, by the way, is also correct alternative syntax.

Notice that we have another overloading of the same operator in the same class:

T & operator [] (int i);

How can this be done? It's the same operator, takes the same arguments, but it returns T by reference, not by value. Is it enough for the compiler to decide between these two when is sees, for instance, a[3]? The answer is, no--two overloads that only differ by return type are not allowed. What really makes a difference here is the word const. One method is constant and the other is not. When acting on a const object, the compiler will pick the const method, otherwise it will use the non-const one.

The non-const, reference-returning version of the operator allows us to use the result of array indexing as an lvalue. The following statement "does the right thing"

a [3] = 11;

Compare it with the more verbose version:

int & r = a.operator [] (3); // reference to the third element of 'a' r = 11; // change value through a reference

In the above example, if a were defined to be const, the compiler would flag it as an error. And rightly so! You are not supposed to change the value of a const object. That, by the way, shows you why I had to define two versions of this method.

If I only had the non-const version, I wouldn't be able to use it on const objects or in const methods of DynArray. In fact our program wouldn't compile for exactly that reason.

If I only had the const version, I wouldn't be able to modify the elements of the array using indexing--I couldn't use them as lvalues.

There is a third possibility: I could say that by returning a reference I am not really changing the state of the object. Let's try this

T & operator [] (int i) const // <-- const method?! { return _arr[i]; // <-- ERROR! }

Oops! It didn't work! It's really getting harder and harder to shoot yourself in the foot, doesn't it?

Let me try to explain why the compiler wouldn't let us compile the above code. It's because of the this pointer. The this pointer is the pointer to the object upon which a given method was invoked. You can use this explicitly; or implicitly, by accessing the members of the object. The above code, for instance, is equivalent to

T & operator [] (int i) const { return this->_arr[i]; // <- ERROR! }

The type of the this pointer depends on the class of the object. It also depends on whether the method is const or not. Inside a non-const method of, say, class Foo , this acts as if it were declared as

Foo * const this;

whereas, in a const method, this becomes

Foo const * const this;

Therefore, inside a const method, the expression this-->_arr[i] produces a const integer, because it dereferences a pointer to const. The compiler catches us red-handed trying to create a "reference to non-const" (the return type) from a const integer. It's as bad as

const double speedOfLight = 300000.0; // km/s double & mySpeed = speedOfLight; // <-- ERROR! Won't compile! // now let me slow down mySpeed = 0.0; // Oops! Changed the speed of light!

The bottom line is: If you want to have a method that can be used as an lvalue, because it returns a reference to the object's data, such method cannot be const. If you also want to overload the same method (that is have another method with the same name and argument types) to provide read-only access, you can do it by making the second method const. Its return type must be different, though. It could be a reference-to-const; or just the type of the value itself, if we want to return the data by value.

Although this technique is mostly used in the context of operator overloading, it can be used with any other kind of overloading. In principle, one could have

class Foo { public: Foo (double x) :_x(x) {} double & Get () { return _x; } double Get () const { return _x; } // Another possibility: // double const & Get () const { return _x; } private: double _x; };

and use Get both as an lvalue and an rvalue (right-hand-side value), as in

Foo varFoo (1.1); const Foo constFoo (3.14); varFoo.Get () = varFoo.Get () + 2.0 * constFoo.Get ();

I'm not saying that I recommend this kind of programming. A much better solution would be to provide a separate method Set and avoid overloading whatsoever.

In any case, it should be obvious that it is very important to be consistent--the two overloads should give access to the same piece of data.

The implementation of the dynamic array is pretty straightforward. Here's the constructor and the destructor.

template <class T> DynArray <T>::DynArray (T const valDefault) : _capacity (initDynArray), _valDefault (valDefault) { _arr = new T [initDynArray]; // allocate memory for (int i = 0; i < initDynArray; ++i) _arr[i] = _valDefault; } template <class T> DynArray <T>::~DynArray () { delete []_arr; }

Method Add has the potential of extending the array.

template <class T> void DynArray <T>::Add (int i, T const val) { if ( i >= _capacity ) Grow(i); _arr [i] = val; }

Here are the two versions of the array access operator. Notice that none of them can be used to extend the array--the assertions are there to make sure that nobody even tries.

template <class T> inline T DynArray<T>::operator [] (int i) const { assert (i < _capacity); return _arr[i]; } template <class T> inline T & DynArray<T>::operator [] (int i) { assert (i < _capacity); return _arr[i]; }

The Grow method works by doubling the size of the array. However, when asked to extend the array beyond doubling, it will oblige, too.

// private method template <class T> void DynArray <T>::Grow (int idxMax) { int newSize = 2 * _capacity; if (idxMax >= newSize) newSize = idxMax + 1; // allocate new array T * arrNew = new T [newSize]; // copy all entries int i; for (i = 0; i < _capacity; ++i) arrNew [i] = _arr [i]; for (; i < newSize; ++i) arrNew [i] = _valDefault; _capacity = newSize; // free old memory delete []_arr; // substitute new array for old array _arr = arrNew; }

Now it's time to make use of our dynamic array template to see how easy it really is. Let's start with the class MultiNode. In the old, limited, implementation it had two arrays: an array of pointers to Node and an array of Boolean flags. Our first step is to change the types of these arrays to, respectively, DynArray<Node*> and DynArray<bool>. We have to pass default values to the constructors of these arrays in the preamble to MultiNode constructor. These methods that just access the arrays will work with no changes (due to our overloading of operator []), except for the places where we used to check for array bounds. Those are the places where we might have to extend the arrays, so we should use the new Add method. It so happens that the only place we do it is inside the AddChild method and the conversion is straightforward.

class MultiNode: public Node { public: MultiNode (Node * pNode) : _aChild (0), _aIsPositive (false), _iCur (0) { AddChild (pNode, true); } ~MultiNode (); void AddChild (Node * pNode, bool isPositive) { _aChild.Add (_iCur, pNode); _aIsPositive.Add (_iCur, isPositive); ++_iCur; } protected: int _iCur; DynArray<Node*> _aChild; DynArray<bool> _aIsPositive; }; MultiNode::~MultiNode () { for (int i = 0; i < _iCur; ++i) delete _aChild [i]; }

Let's have one more look at the Calc method of SumNode. Other than for the removal of error checking (we have gotten rid of the unnecessary flag, _isError), it works as if nothing have changed.

double SumNode::Calc () const { double sum = 0.0; for (int i = 0; i < _iCur; ++i) { double val = _aChild [i]->Calc (); if (_aIsPositive[i]) sum += val; else sum --= val; } return sum; }

The only difference is that when we access our arrays _aChild [i] and _aIsPositive [i], we are really calling the overloaded operator [] of the respective dynamic arrays. And, by the way, since the method Calc is const, it is the const version of the overload we're calling. Isn't that beautiful?

Separating Functionality into New Classes

I'm not happy with the structuring of the symbol table. Just one look at the seven data members tells me that a new class is budding. (Seven is the magic number.) Here they are again:

HTable _htab; int * _offStr; int _capacity; int _curId; char * _strBuf; int _bufSize; int _curStrOff;

The rule of thumb is that if you have too many data members you should group some of them into new classes. This is actually one of the three rules of class formation. You need a new class when there are

• too many local variables in a function,
• too many data members in a class or
• too many arguments to a function.

It will become clearer why these rules make perfect sense (and why seven is the magic number) when we talk about ways of dealing with complexity in the third part of this book.

The last three data members of the symbol table are perfect candidates for a new string-buffer object. The string buffer is able to store strings and assign them numbers, called offsets, that uniquely identify them. As a bonus, we'll make the string buffer dynamic, so we won't have to worry about overflowing it with too many strings.

class StringBuffer { public: StringBuffer () : _strBuf (0), _bufSize (0), _curStrOff (0) {} ~StringBuffer () { delete _strBuf; } int AddString (char const * str); char const * GetString (int off) const { assert (off < _curStrOff); return &_strBuf [off]; } private: void Reallocate (int addLen); char * _strBuf; int _bufSize; int _curStrOff; };

When the buffer runs out of space, the AddString method reallocates the whole buffer.

int StringBuffer::AddString (char const * str) { int len = strlen (str); int offset = _curStrOff; // is there enough space? if (_curStrOff + len + 1 >= _bufSize) { Reallocate (len + 1); } // copy the string there strncpy (&_strBuf [_curStrOff], str, len); // calculate new offset _curStrOff += len; _strBuf [_curStrOff] = 0; // null terminate ++_curStrOff; return offset; }

The reallocation follows the standard doubling pattern--but making sure that the new string will fit no matter what.

void StringBuffer::Reallocate (int addLen) { int newSize = _bufSize * 2; if (newSize <= _curStrOff + addLen) newSize = _curStrOff + addLen; char * newBuf = new char [newSize]; for (int i = 0; i < _curStrOff; ++i) newBuf [i] = _strBuf [i]; delete []_strBuf; _strBuf = newBuf; _bufSize = newSize; }

Now the symbol table is much simpler. It only has four data members. I also used this opportunity to turn the array _aOffStr into a dynamic array.

class SymbolTable { // Private embedded anonymous enum enum { cSymInit = 64 }; public: // Public embedded anonymous enum enum { idNotFound = -1 }; SymbolTable (); int ForceAdd (char const * str); int Find (char const * str) const; char const * GetString (int id) const; private: int _curId; HTable _htab; DynArray<int> _aOffStr; // offsets of strings in buffer StringBuffer _bufStr; };

Here's the new improved implementation of ForceAdd. We don't have to worry any more about overflowing the offset table or the string buffer.

int SymbolTable::ForceAdd (char const * str) { int offset = _bufStr.AddString (str); _aOffStr.Add (_curId, offset); _htab.Add (str, _curId); ++_curId; return _curId - 1; }

It's always a pleasure to be able to simplify some code. This is the part of programming that I like best. ForceAdd now reads almost like a haiku.

This is how the constructor of the symbol table shrinks

SymbolTable::SymbolTable () : _curId (0), _htab (cSymInit + 1), _aOffStr (0) {}

And this is how simple the parsing of a symbolic variable becomes

// Factor := Ident if (id == SymbolTable::idNotFound) id = _symTab.ForceAdd (strSymbol); assert (id != SymbolTable::idNotFound); pNode = new VarNode (id, _store);

Class Store needs two dynamic arrays and a few little changes where the bounds used to be checked.

class Store { private: // private anonymous enum enum { stNotInit, stInit }; public: explicit Store (SymbolTable & symTab); bool IsInit (int id) const { assert (id >= 0); return _aStatus.InRange (id)) && _aStatus [id] != stNotInit; } double Value (int id) const { assert (id >= 0); assert (IsInit (id)); return _aCell [id]; } void SetValue (int id, double val) { assert (id >= 0); if (_aCell.InRange (id)) { _aCell [id] = val; _aStatus [id] = stInit; } else { AddValue (id, val); } } void AddValue (int id, double val) { assert (id >= 0); _aCell.Add (id, val); _aStatus.Add (id, stInit); } private: DynArray<double> _aCell; DynArray<unsigned char> _aStatus; };

In the preamble to the constructor of Store we construct the dynamic arrays. The memory cells are initialized to zero and the statuses to stNotInit.

Store::Store (SymbolTable & symTab) : _aCell (0.0), _aStatus (stNotInit) { // add predefined constants // Note: if more needed, do a more general job cerr << "e = " << exp (1) << endl; int id = symTab.ForceAdd ("e"); AddValue (id, exp (1)); cerr << "pi = " << 2 * acos (0.0) << endl; id = symTab.ForceAdd ("pi"); AddValue (id, 2 * acos (0.0)); }

Finally, our getting rid of built in limitations is reflected in some nice simplifications in main. We no longer need to pass size arguments to the constructors.

int main () { ... SymbolTable symTab; Function::Table funTab (symTab); Store store (symTab); ... }

Standard Vector

Now that you know how a dynamic array works, it's time to introduce the most useful member of the Standard Library, the vector. The vector is all that you might expect from a dynamic array and more. Without further ado, let's quickly substitute all the occurrences of DynArray with std::vector (yes, it's a member of the std namespace), making sure we include the appropriate header:

#include <vector>

Let's start with MultiNode and its two dynamic arrays.

std::vector<Node*> _aChild; std::vector<bool> _aIsPositive;

Before our code can compile, we have to make a few adjustments. For instance, std::vector doesn't have the Add method. We can, however, append new elements by calling push_back, which has the side effect of growing the array if necessary. (Notice, by the way, the particular naming convention of the stadard library. All names are lower case with underscores for word separators. You'll have no problems distinguishing them from our own names.)

Another thing, there seems to be no simple way of providing the default values for the elements of a vector. Fortunately, the standard library uses default constructors to fill empty spaces in vectors and other containers. It so happens that C++ provides default constructors for all built-in types. For instance, the default value for an int or a pointer is zero, for a bool, false, etc. Try it!

int i = int (); bool b = bool (); typedef void * voidptr; void * p = voidptr (); cout << "int " << i << ", bool " << b ", pointer " << p << endl;

It turns out that the introduction of std::vector further simplified our implementation of class MultiNode:

class MultiNode: public Node { public: MultiNode (Node * pNode) { AddChild (pNode, true); } ~MultiNode (); void AddChild (Node * pNode, bool isPositive) { _aChild.push_back (pNode); _aIsPositive.push_back (isPositive); } protected: std::vector<Node*> _aChild; std::vector<bool> _aIsPositive; };

I have eliminated the member variable _iCur as it's no longer needed. We can quickly find out how many children there are by calling the vector's size () method. However, if all we need is to iterate over the elements of a vector (like we do in the destructor of MultiNode) there is a better, more "standard," way: We can use an iterator.

If you think of a vector as an array, an iterator is like a pointer. Remember when I told you that it's better to use an index rather than a pointer to access elements of an array? With vectors it's sort of the opposite, at least as far as iteration goes.

You can get an iterator pointing to the beginning of a vector by calling te vector's begin () method. Similarly, you can get the iterator pointing one beyond the last element of a vector by calling its end () method. You can move the iterator to point to the next slot of the vector by applying the increment, ++, operator. You can test whether two iterators are equal (point to the same slot in the vector) using the (un-) equality operators. Finally, you can get the value of an element of the vector by dereferencing the iterator using the star (asterisk) operator.

This is what the new destructor of MultiNode looks like:

MultiNode::~MultiNode () { typedef std::vector<Node *>::iterator NodeIter; for (NodeIter it = _aChild.begin (); it != _aChild.end (); ++it) delete *it; }

The type "iterator" is internal to the template class vector. That makes for a very unwieldy type name, std::vector<Node *>::iterator. It is customary to declare local typedefs for such complex type names.

In case you're wondering, vector::iterator is in all likelihood implemented as a pointer in most versions of the Standard Library. And if, for some reason or another, it's not, you can still do with it virtually anything you can do with a pointer. What's even more important is that you get from it the same kind of performance as from a pointer. You can pass it around just like a poiner. You can return it from a function like a pointer. In fact, performance-wise, there is no difference between the code above and the following:

Node * aChild [size]; typedef Node ** NodeIter; for (NodeIter it = aChild; it != aChild + size; ++it) delete *it;

I want to stress this point, because some programmers might hesitate to use some of the features of the Standard Library for fear of performance degradation. No need to worry--the creators of the Standard Library made it their highest priority not to jeopardize the performance. That's why, for instance, they selected the pointer-like approach to iteration, rather than the, somehow safer, sequencer approach. Pointer-like iteration requires two separate pieces of data--the current position and the end position. A sequencer has access to both. With a sequencer, there is no danger that you might, by mistake, compare the current position in one vector against the end position that belongs to some other vector. In fact, if you are worried about this kind of errors, you might create a sequencer class out of two iterators.

class NodeSeq { public: NodeSeq (std::vector<Node *> & vec) : _cur (vec.begin ()), _end (vec.end ()) {} bool AtEnd () const { return _cur == _end; } void Advance () { ++_cur; } Node * Get () { return *_cur; } private: std::vector<Node *>::iterator _cur; std::vector<Node *>::iterator _end; };

The only drawback of the sequencer approach is that it's slightly more expensive to pass a sequencer by value than it is to pass an iterator--as you can see a sequencer is usually twice as large than the corresponding iterator. And, as you'll see later, iterators are passed around a lot, once you start using standard algorithms.

Next on our list of dynamic array substitutions is the symbol table with its _aOffStr array. We'll have to re-code the ForceAdd method; incidentally getting rid of the _curId member.

int SymbolTable::ForceAdd (char const * str) { int offset = _bufStr.AddString (str); int id = _aOffStr.size (); _aOffStr.push_back (offset); _htab.Add (str, id); return id; }

As you might remember, we use the current position in the array of offsets as our string id. Again, the size () method of the vector helps us locate the current end of the vector.

By the way, did you notice that the compiler didn't complain about our initializing the vector in the constructor of SymbolTable? Unlike DynArray, std::vector doesn't take a default element value. However, it has a one-argument constructor that accepts the initial size for the vector.

Finally, let's get rid of the two DynArrays in Store. Here the situation is a bit more tricky. One of the arrays stores enumerated values, for which the compiler doesn't know the default. Instead of coming up with a clever trick, why don't we simply replace this array with a vector of bool. All we ever ask this array is whether a given element has been initialized or not. That's a yes/no question. So here are the new data members of Store:

std::vector<double> _aCell; std::vector<bool> _aIsInit;

Next, we have to substitute all calls to DynArray::InRange with a test against vector::size (). For instance,

bool IsInit (int id) const { assert (id >= 0); return id < _aIsInit.size () && _aIsInit [id]; }

The AddValue method has to be able to insert an item beyond the current end of the vector. The way to do it is to first resize them. The resize method increases the size of the vector and fills the new slots with default values.

void AddValue (int id, double val) { assert (id >= 0); _aCell.resize (id + 1); _aIsInit.resize (id + 1); _aCell [id] = val; _aIsInit [id] = true; }

To summarize: There is no reason for any program to have unreasonable limitations due to the use of fixed-size arrays. Standard Library vector should be used whenever a resizable array is needed.