Wednesday, May 5, 2010

Building a stack

OK, now we have enough small pieces of C++ as a better C, to do something real. Let's build a stack of integers, using constructors and dynamic memory allocation.
#include
// declare our stack element with constructor.
struct StackElement {
StackElement(int aValue, StackElement* pTail);
// aValue and pTail can have any value!
int value;
StackElement* pNext;
// StackElement is not yet completed, but
// we can have pointers to incomplete types.
};
StackElement::StackElement(int aValue,
StackElement* pTail)
: value(aValue),
pNext(pTail)
{
// nothing to do in here as it's all taken care of in
// the initialiser list.
}
// Struct thrown if preconditions are violated.
struct Precond
{
Precond(char* p);
char* msg;
};
Precond::Precond(char* p) : msg(p) {}
// Use function overloading to print
// stack elements, strings and integers.
void print(StackElement* pElem) throw (Precond)
{
if (pElem == 0) // **1**
throw "0 pointer sent to print(StackElement*)";
cout <<>value << endl;
}
void print(const char* string = "") throw (Precond)
{ // just a new line if default parameter value used.
if string == 0)
throw "0 pointer sent to print(const char*)";
cout << string << endl;
}
void print(int i)
{
cout << i << endl;
}
int main(void)
{
try {
print("Simple stack example");
print(); // just a new line
StackElement* pStackTop = 0;
print("Phase one, pushing objects on the stack");
print();
{
for (unsigned count = 0; count < 20; ++count)
{
// Create new element first on the stack by
// setting the "next" pointer of the created
// element to the current top of the stack.
pStackTop = new StackElement(count, pStackTop);
if (pStackTop == 0) //**2**
{
cout << "Memory exhausted. Won't add more"
<< endl;
break;
}
print(count);
}
}
print("Phase two, popping objects from the stack");
print();
while (pStackTop != 0)
{
print(pStackTop);
StackElement* pOldTop = pStackTop;
pStackTop = pStackTop->pNext;
delete pOldTop;
}
return 0;
}
catch (Precond& p) {
cout << "Precondition violation: " << p.msg << endl;
return 1;
}
catch (...) {
cout << "Unknown error: Probably out of memory"
<< endl;
return 2;
}
}
At //**1** you see something unexpected. The pointer is initialised to 0, and not "NULL". There is no such thing as "NULL" in C++, so the number 0 is what we have, and use. The reason is, oddly as it may seem, that C++ is much pickier than C about type correctness. Typically in C, "NULL" is defined as "(void*)0." C++ never allows implicit conversion of a "void*" to any other pointer type, so this definition is not good enough. The integer 0, however, is implicitly convertible to any pointer type.
//**2** is an unpleasant little thing. Depending on how new your compiler is, the "new" operator will either return 0 (for old compilers) or throw an instance of "bad_alloc" (for new compilers) if the memory is exhausted.
So, what do you think of this small stack example? Is it good? Better than the C alternative with several different function names to remember, being careful to allocate objects of the correct size and initialise the struct members correctly? I think it is better. We don't have to overload our memory with many names, we don't have to worry about the size of the object to allocate, and we don't need to cast an incompatible type either (compare with "malloc") and initialisation of the member variables is localised to something that belongs to the struct; its constructor. We check our preconditions (no post conditions are used here) with C++ exceptions.

No comments:

Post a Comment