C++Talk.NET

Stefan Chrobot · Guest

Hi!

I'm reading "Effective C++" 2nd Edition, by Scott Meyers - fantastic
book BTW - and I'd like to propose my improvement of Stack class.

The idea is to create a template class that avoids code bloat. It is
achieved by using a generic stack that operates on pointers and doeas
all the job, and also templatized classes that ensure type safety of all
the operations. But there was one restriction: the stack has to hold
pointers to objects. My solution tries to get around this problem. Much
of the comments refer to the version presented in the book, but I think
that they are useful nonetheless.

Maybe it's not the most beautiful code in the world, but I think it
works. I've tested this code: all ctors/c-ctors/dtors were called
correctly and there were no memory leaks.

Comments are welcome!

Stefan Chrobot

/*

Stack

Implementation of a stack which tries to avoid code bloat.
This time Stack can hold any type and it does it in STL fashion, i.e.
holding copies of objects. Every StackNode holds a pointer to a memory,
where resides it's corresponding object. GenericStack and it's
specializations take care of allocation and deallocation of this memory.

*/

// Generic stack declaration
//
// There are three new member functions in GenericStack. objectSize()
// is to return the number of bytes, that each object of held type
// T needs. destroyObject()'s role is to explicitly call the destructor
// for type T. The functionality of both depends on the derived class'
// type, which is unknown to GenericStack, so both were made pure
// virtual. The last function - purge() - takes role of the destructor
// and frees all the memory reserved by the stack. The reasoning behind
// this is that the destructor must call destuctors for each held
// object, but it doesn't know it's type. We can't use destroyObject()
// in destructor, because all calls in constructors and destructors are
// early bound, because in constructor the derived part is not yet
// constructed and in the destructor it's already destroyed. One could
// move the code to destructor of specialized stacks, but then we would
// cause code bloat, which we are trying to avoid. We call purge() from
// destructors of specialized stacks. Apart from that and argument and
// return type of push (explained later), everything stays the same.
class GenericStack
{
protected:
GenericStack();
~GenericStack();
void* push();
void* pop();
bool empty() const;
virtual size_t objectSize() const = 0;
virtual void destroyObject(void*) const = 0;
void purge();
private:
GenericStack(const GenericStack&); // disallowed
GenericStack& operator=(const GenericStack&); // disallowed
struct StackNode
{
void* data;
StackNode* next;
StackNode(void* newData, StackNode* nextNode)
: data(newData), next(nextNode) { }
};
StackNode* top;
};

// Generic stack implementation

// Same as before
GenericStack::GenericStack() : top(0) { }

// All that push() knows and can do is to create a new element
// in the list, connect it to the list, and allocate amount of
// memory, which is specified by derived class. push() returns pointer
// to memory, where new object should be constructed. This pointer is
// then used when calling placement new.
void* GenericStack::push()
{
// create sufficient space
void* newObjectPlace = new char[objectSize()];
// create new list node
top = new StackNode(newObjectPlace, top);
// return pointer to memory
return newObjectPlace;
}

// The role of the pop() is to return a copy of object that sits on the
// top of the stack. Because pop() doesn't know how to construct object
// of unknown type, it just disconnects the top node of the list and
// lets specialized pop() do the rest of the job.
void* GenericStack::pop()
{
StackNode* topOfStack = top; // retrieve top of the stack
top = top->next; // "move" the top of the stack
void* data = topOfStack->data; // remember object held on top
delete topOfStack; // remove top list node
return data; // return address of top element
}

// Same as before
bool GenericStack::empty() const
{
return top == 0;
}

// Do nothing, all handled by purge()
GenericStack::~GenericStack()
{
}

// When removing elements of generic stack, destructor for every object
// has to be called explicitly, because all of them were created using
// placement new, so simply deleting them causes errors.
void GenericStack::purge()
{
while(top)
{
// get last list node
StackNode* toDie = top;
// "move" top of the list
top = top->next;
// call destructor for object, virtual call works OK
destroyObject(toDie->data);
// free object's memory
delete[] static_cast<char*>(toDie->data);
// free list's node memory
delete toDie;
}
}

// Template stack
template<typename T>
class Stack : private GenericStack
{
public:
~Stack()
{
GenericStack::purge(); // Remove all objects
}
// New version of push, accepts argument by const reference,
// like STL containers do.
void push(const T& object)
{
// create new list node, reserve required memory for object,
// retrieve the pointer to where the object should reside
void* newObjectSpace = GenericStack::push();
// create object in specified location of memory using copy
// constructor, making a copy of push()'s argument
new (newObjectSpace) T(object);
}
// pop() has to return a copy of the object
// we're holding on stack
T pop()
{
// remove top list node without removing object's memory
// and therefore the object itself, get pointer to it
T* toDie = static_cast<T*>(GenericStack::pop());
// construct return value from object in memory
T popped = *toDie;
// destroy object
destroyObject(toDie);
// free object's memory, need reinterpret_cast unfortunately
delete[] reinterpret_cast<char*>(toDie);
// return popped object
return popped;
}
// same as before
bool empty() const { return GenericStack::empty(); }
private:
// easy to implement using sizeof()
size_t objectSize() const { return sizeof(T); }
// destroyObject calls destructor explicitly
void destroyObject(void* object) const
{
static_cast<T*>(object)->~T();
}
};

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Andreas Magnusson · Guest

Hi, I've also read Meyer's "Effective C++" (don't remember which
edition though) and it's very good.

Joel Eidsath · Guest

Although Meyer's Stack implmentation was appropriate for making his
points: "Differentiate between inheritance and templates" and "Use
private inheritance judiciously," you would probably want to use the
STL stack in real code.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Andreas Magnusson · Guest

Oops, I forgot to say (a bit tired when I wrote my previous post) as I
recall it Meyer also explains why having pop() return the top element a
bad idea if you want to play it exception-safe. Anyway, here's why:
Eventhough you may be able to extract the element and free the data in
the stack in an exception-safe manner, you may still not be fully
exception-safe. Consider this:

CtorCanThrow v = s.pop();

or even

AssignmentCanThrow v;
v = s.pop();

What may happen is that the element just popped from the stack may get
lost as the ctor/assignment operator of v throws an exception. So you
popped an element but it's gone.

This is why the STL stack implementation (as all stack implementations
that are exception-safe) has three functions that covers the stack
"concept" (push/pop): push(), pop() and top(). Both push() and pop()
return void and top() returns the top-element without popping it.

A great book to read to become more exception-aware is Herb Sutter's
"Exceptional C++". For me it was definately an eye-opener as I believe
it will be for you.

Sorry if I come out a bit harsh, my aim is to educate not to discourage
you!

Cheers,
Andreas

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Stefan Chrobot · Guest

Andreas Magnusson napisa³(a):

Stefan Chrobot · Guest

Andreas Magnusson napisa=B3(a):

Andreas Magnusson · Guest

Maciej Sobczak · Guest

Stefan Chrobot wrote:

Ulrich Eckhardt · Guest

Stefan Chrobot wrote:

Stefan Chrobot · Guest

Ulrich Eckhardt napisa=B3(a):

Ulrich Eckhardt · Guest

Stefan Chrobot wrote: