How to implement stack with various types of data?

[bejfake]

Hi,

I've got such class template:

template <class Type> class Stack{
private:
	struct Element{
		Type value;
		Element *prev;
	} 
	*end;
public:
	Stack(){
		end = NULL;
	}

	void push(Type value){
		struct Element *element = new Element;
		element->value = value;
		element->prev = end;
		end = element;
	}

	Type pop(){
		if(end != NULL){
			Type tempValue = end->value;
			struct Element *tempElement = end->prev;
			end = NULL;
			delete end;
			end = tempElement;
			return tempValue;
		}
	}

	~Stack(){
		while(end != NULL){
			pop();
		}
	}
};

It works good. But my primary assumption was to create stack which can store mixed types of data, f.e.

// now i have
Stack<int> stack; // i have to declare what kind of type will store the stack
stack.push(4);

// i would i have
Stack stack;
stack.push(4);
stack.push(3.14);
stack.push(string);
stack.push('c');
// etc

I didn't have idea how to do this so I've written simplified version of stack.

I was looking for some concept on web but unfortunately didn't find nothing especially.

[mike_2000_17]

This requires dynamic polymorphism (i.e. base class and some derived classes). A simple way to do it:

//a very simple base class with one virtual function (required for RTTI).
struct stack_element {
  virtual ~stack_element() { };
};

//a general class template for holding a primitive value
template <class T>
struct primitive : public stack_element {
  T value;
  primitive(const T& aValue) : value(aValue) { };
  ~primitive() { };
};

//a template specialization for pointer types.
template <class T>
struct primitive<T*> : public stack_element {
  T* value;
  primitive(T* aValue) : value(aValue) { };
  ~primitive() { if(value) delete value; };
};

//now, you can reuse your Stack class with stack_element pointer type:
Stack<stack_element*> myStack;
myStack.push(new primitive<int>(4));
myStack.push(new primitive<string>("hello world"));
myStack.push(new primitive<int*>(new int(4)));
//now, retrieving the elements is a bit ugly:
stack_element* elem = myStack.pop();
if(dynamic_cast<primitive<int>*>(elem))
  cout << dynamic_cast<primitive<int>*>(elem)->value << endl;
//..etc.

Of course, you see that this is far from ideal and basically there is no way to get around this. You can, of course, drop the "templatization" of class Stack and just implement it for "stack_element*" (which can be a nested class of Stack). You can also avoid the dynamic_cast if you can restrict the amount of different types needed and provide some sort of type identification virtual method for stack_element (such as "getTypeID" that could output a unique integer for each different type). If you only store types of similar sizes, you can also use a "union" (yes.. in good old C-style) that would replace dynamic polymorphism, if you don't like the overhead and don't mind the reduced capabilities. Keep in mind that the above code is ugly for a good reason: bad design leads to ugly code.

I have to say, however, that in all my years of programming, I have never found a use for heterogeneous arrays or stacks or whatever. Usually, you use a stack to contain some abstract data type (ADT) and with the use of polymorphism, you generally can find a base class that encompasses all the needed abstract functionality of the elements. For example, using a stack for a state-machine is very typical, and usually different states are implemented very differently and with very different data members, but you can easily find a base class that has all the methods you would ever need a state-object to perform (in the abstract sense).

[mike_2000_17]

Forgot to mention, there is also the Boost Any library to do this kind of stuff.

[bejfake]

Thx for exhaustive voice. I will look at this tomorrow.

I agree with you that stack which can hold every type of data is unpractical, but I have to write stack implementation to school (such as i've written or expanded version for better mark ;) ).

It's just amazing how people on non-polish boards can be nice and helpful. I think i will stop use them :)

Sorry for my bad English and see ya.

[bejfake]

Thx for exhaustive voice. I will look at this tomorrow.

I agree with you that stack which can hold every type of data is unpractical, but I have to write stack implementation to school (such as i've written or expanded version for better mark ;) ).

It's just amazing how people on non-polish boards can be nice and helpful. I think i will stop use them :)

Sorry for my bad English and see ya.

[alwaysLearning0]

I just want share my 2 cents,

you can implement typelist and variant, here is a library which has demonstrate and explained implementation of these design patterns, this is really powerfull.

http://www.codeproject.com/KB/cpp/TTLTyplist.aspx

Using this you can do following stuff:

struct my_type
{
   int x;
   my_type() : x(0) {}
   virtual ~my_type();
};

union my_union
{
   my_type a;
   double b;
};


typedef variant< my_type, double > mv;

main()
{
  my_type a;
  
  std::vector<mv> v;
  v.push_back(2.3); //add double 

  v.push_back(a); //add my_type

}

this library can use upto 5 types, but you can extend it more.

boost any is also a good one.