// hSTACK.h
#ifndef hSTACK__H
#define hSTACK__H
template <class T>
class Stack {
int size;
T* storage[3];
int counter;
public:
/*
* The Constructor
*/
Stack(int theSize) : size(theSize), counter(0) {
T* storage = new T[theSize];
};
/*
* The destructor
*/
~Stack() {
cout << "Ende";
}
/*
* Push something on the stack
*/
void push(T& data) {
storage[counter] = &data;
counter++;
};
/*
* Pop something from the stack
*/
T* pop() {
if(counter > 0) {
T* data = storage[counter-1];
counter--;
return data;
} else {
return 0;
}
};
/*
* Peek the last object from the stack
*/
T& peek() {
return storage[counter];
};
};
#endif hSTACK__H
// main.cpp, for testing purposes
#include <iostream>
#include "hStack.h"
using namespace std;
int main() {
Stack<int> Test(10);
int x1 = 15;
int x2 = 13;
int x3 = 10;
Test.push(x1);
Test.push(x2);
Test.push(x3);
cout << *(Test.pop()) << endl;
cout << *(Test.pop()) << endl;
cout << *(Test.pop()) << endl;
cout << *(Test.pop()) << endl;
// Required to keep the program from exiting
char x;
cin >> x;
return 1;
}
Problem with my first Stack-Class
Author
Hi,
I'm new to C++ programming. I'm coming from a PHP and Java background, so while OOP is no problem for me, some of the other concepts in C++ are really bugging me (especially pointers, I guess).
I've finally done reading intensively through "Thinking in C++ Vol. 1" and wanted to start getting used to the languange by writing a little Hangman game. But first I wanted to write something very basic, like my own little Stack-class, so here is what I got already:
Well, as you can see, I haven't implemented checking for array out-of-bounds exceptions, that comes later.
I have two questions now:
1.) A problem which you might have noticed is, that I always initialize the stack-storage to '3', since I had to give the T-array an initial value at start, or else the compiler prints out an error. I tried:
T* storage[];
Which didn't worked. I hoped to make clear to the compiler, that this is an array of undetermined size, but it doesn't work.
If I do
T* storage[1]
and in the constructor I initialize the variable like this:
T* storage = new T[theSize];
It's not possible to push more objects than one on the stack, or else I get an array-out-of-bounds exception. What am I doing wrong?
2.) If you take a closer look at the "pop()"-method, you see that in case I pop more objects than there are on the stack, it will simply return '0', which is also done in the examples of "Thinking in C++". But in both, my code and in the examples, MS Visual C++ always shows a dialog-box:
"Unhandled exception at 0xblablabla in StackClass.exe..."
Why is this? Is it because I try to dereference a constant value and not a variable-pointer? Any way around this? What should I do in case I have popped everything from the stack.
Btw, I just notice, that I haven't included the fact, that popping something from the stack, removes it. Well, will do that later, though.
So, any help is greatly appreciated. :)
1. The code T* array[] does not create an array of unknown size, but rather of a size you do not want to specify (but can be inferred from what you place into the array during initialization). Thus, any such array must be initialized as part of its declaration (and as such, cannot be a member of a class).
The code T* array[3] creates an array of three pointers as part of the class memory. This memory cannot be deleted when you need to resize the array. A better approach would be to store a pointer-to-pointer and initialize it in the constructor.
T* storage = new T[theSize]; does not initialize this->storage: it creates a local variable and has it point to memory, which is leaked when the variable goes out of scope. Also note that you are using the incorrect type. What you want is an array of T*.
2. Manipulating a pointer set to 0 is acceptable, as long as you don't dereference it. *0 (which occurs on your fourth pop line) is undefined behavior.
3. Use std::vector instead of C arrays first. Once you understand how vectors work, move through the code and replace them with C arrays. Don't try to understand two things at once, it just won't work.
Even then, you have to learn early on the Separation of Responsibility principle. The Stack class is responsible for managing a FILO queue, not for managing a resizable array. Whether you use std::vector or your own ResizableArray class based on C arrays, this responsibility belongs outside the Stack class.
The code T* array[3] creates an array of three pointers as part of the class memory. This memory cannot be deleted when you need to resize the array. A better approach would be to store a pointer-to-pointer and initialize it in the constructor.
T* storage = new T[theSize]; does not initialize this->storage: it creates a local variable and has it point to memory, which is leaked when the variable goes out of scope. Also note that you are using the incorrect type. What you want is an array of T*.
2. Manipulating a pointer set to 0 is acceptable, as long as you don't dereference it. *0 (which occurs on your fourth pop line) is undefined behavior.
3. Use std::vector instead of C arrays first. Once you understand how vectors work, move through the code and replace them with C arrays. Don't try to understand two things at once, it just won't work.
Even then, you have to learn early on the Separation of Responsibility principle. The Stack class is responsible for managing a FILO queue, not for managing a resizable array. Whether you use std::vector or your own ResizableArray class based on C arrays, this responsibility belongs outside the Stack class.
template<typename T> class Stack { std::deque<T> contents;public: void push(const T& pushed) { contents.push_back(pushed); } T top() const { return contents.last(); } void pop() { contents.pop_back(); } std::size_t size() const { return contents.size(); }};
Okay, let's begin:
I'm sure you have more questions on memory allocation and pointers, so ask away. It's getting kind of late over here, so if there's something slightly amiss, it's my fault. I KNOW for a fact that there's a TRILLION memory leaks, and the behaviour of the class is unusual, but I was just correcting what you had written down - I'm not about to redesign (and complete!) your class for you.
- 1 - You're right - pointers aren't your strong suit (and why would they be with a background in Java and PHP?). You want a a dynamic array - that is, one whose size will change at run-time. To do this, you declare a pointer to random memory (Just: T * storage;), and then on initialisation, you ask for however much memory you need (storage = new T[new_size];). Then you can access the first new_size elements, which are zero through to new_size - 1 (you know this). If you run out of space, you have to store all that data temporarily, ask for a new "chunk" of memory that's even larger, and copy all your old stored elements over, leaving room at the back for new ones to be created. As you have it, you're creating an array of pointers.
- 2. - That pop thing is happening because of the above reason. You think you're asking for different memory than you actually asked.
- 3. - Don't use those sort of comments unless you need to comment out a big piece of code for testing purposes. Otherwise you'll run into trouble when you do want to comment out a big block of code.
- 4. - Redone:
// hSTACK.h#ifndef hSTACK__H#define hSTACK__Htemplate <class T>class Stack{ unsigned int size; T * storage; unsigned int counter; public: Stack(unsigned int theSize = 0) : size(theSize), counter(0), storage(NULL) { storage = new T[theSize]; }; ~Stack() { cout << "Ende"; } // we use -const- here, because we should (we don't change it, and we want to // communicate that to the user). void push(const T& data) { // You originally had this as &data, which was taking a pointer to // the T, which was necessary to work with your T * storage[3];. But // it wasn't doing what you were thinking. storage[counter] already // dereferences it to type T, so it's just basic assignment. // // Also, the post-increment (++) operator is around for this very purpose, // it POST increments, ie - it increments AFTER it's used. storage[counter++] = data; }; // Pop's return type has changed to T, because we've dereferenced a pointer to a bunch // of Ts. T pop() { if(counter > 0) return storage[counter--]; else return NULL; }; T& peek() { return storage[counter]; };};#endif hSTACK__H
I'm sure you have more questions on memory allocation and pointers, so ask away. It's getting kind of late over here, so if there's something slightly amiss, it's my fault. I KNOW for a fact that there's a TRILLION memory leaks, and the behaviour of the class is unusual, but I was just correcting what you had written down - I'm not about to redesign (and complete!) your class for you.
Quote:Original post by _goatT pop() { if(counter > 0) return storage[counter--]; else return NULL; };
Huh?
Author
First off: I'm blown away by the level of replies I got here, this is much better and more helpful than any other programming board I've experienced! Much thanks to you!
@ToohrVyk:
Ah, that thing with the constructor was really stupid, should have seen that myself.
You have written "template<typname T>" instead of "<class T>". I did a quick search on google and haven't really found a difference, but I want to make sure that there really isn't one, right?
What do you mean with "C Arrays"?
int myInteger[10];
This?
Well, I know that an std::vector (or deque in your example; I didn't even know what that was, had to look it up) would fit here better maybe and I wouldn't write my own container-classes in an application if it is not absolutely needed, because they are tested and optimized over the time, but I just want to learn how things work and get used to C++, so this isn't a bad excercise.
Hmmm, even though I'm an advocate of good software-design(which doesn't make me a good software-designer ;) ), I don't really know if I agree with this seperation.
While I understand the argument, that one might see the Stack as a simple LIFO-class, I think that always having an array in the appropriate size is essential to a stack and thus tightly bind to it.
If the stack moves the responsibility to another class or does it itself is not really very important, since I can't think of a case right now, where this would really benefit my stack-class.
It would benefit from this seperation, if I would later want to change how my array-class works. This would make life a little easier, than modifying the stack class for this purpose, but when do I really need to change this behaviour? (ok, not really a good question, because there may always be something wrong)
Whatever, maybe there is a much better point to it I cannot see right now. Seperation of responsibility is always a nice topic. ;)
@_goat:
Thanks for your input and no, I don't expect you to redesign my whole class for me, even though you did it already. This is much more than I expected.
To 1: Yes, I'm working on this right now, nice explanation.
To 3: Wow, I'm using these type of comments for function-explanations for so long now and never noticed this. Yes, you're right, I will stick to the other way.
To 4: Thanks for this, I really understand things much better now. Well, you made a little mistake, I guess:
Counter had to be pre-decremented, because after a push, counter is always one number bigger than there are actual elements on the stack.
Hmmm, a TRILLION memory leaks sound, uhm, very much. Here is my class:
I tried to eliminate one memory-leak by deleting "storage" in the destructor. There shouldn't be much more, right?
As you can see in my pop()-method, I tried to free the memory of a popped element on the stack, but the compiler gave me an error:
"error C2541: 'delete' : cannot delete objects that are not pointers"
Hmmm, what I thought the class did was to get variables passed to push and then take the address and just store the address of the objects.
So I made a quick test:
This looks strange to me. Shouldn't a variable declared like:
"T* storage;" store a pointer / an array of pointers to a type T?
In the push()-function the argument is passed by reference, so that means, when I change the variable inside the push()-function, it would be changed on the outside too, right?
But now the variable is assigned as
"storage[counter++] = data;"
which means, that the value of data is stored, basically just a copy.
When I change the assignment to "...= &data" it doesn't work. And why does it work now? I thought storage should store pointers? I'm confused. How would I achive to store pointers?
Well, when I think about it now, I don't even know if this would be a good idea. Imagine that I have a stack class which stores pointers instead of values and I have this code.
This function gets called from somewhere. Now, when fillStack() is called, it pushes 4 pointers to the integer on the stack. Actually, this isn't the greatest example ever, but it should show the behaviour.
Whatever, when the function goes out of scope now, the stack should now be filled with pointers to "empty" locations in the memory, since the variables do not exist anymore, right?
And now I'm confused. I thought that by passing just the addresses it would be faster than copying everything by value. Imagine a very large and complex object, getting these kind of objects onto the stack could definately be a bottle-neck. But what can I do against this?
Hmmm, maybe something like this?
This would prevent the variables to go out of scope and get destroyed, right? I couldn't think of any other way.
I know these are alot a of questions, but I really want to learn this the right way. Thanks for helping me up to this point already, I'm now trying to make the stack dynamically-sized.
@ToohrVyk:
Ah, that thing with the constructor was really stupid, should have seen that myself.
You have written "template<typname T>" instead of "<class T>". I did a quick search on google and haven't really found a difference, but I want to make sure that there really isn't one, right?
What do you mean with "C Arrays"?
int myInteger[10];
This?
Well, I know that an std::vector (or deque in your example; I didn't even know what that was, had to look it up) would fit here better maybe and I wouldn't write my own container-classes in an application if it is not absolutely needed, because they are tested and optimized over the time, but I just want to learn how things work and get used to C++, so this isn't a bad excercise.
Hmmm, even though I'm an advocate of good software-design(which doesn't make me a good software-designer ;) ), I don't really know if I agree with this seperation.
While I understand the argument, that one might see the Stack as a simple LIFO-class, I think that always having an array in the appropriate size is essential to a stack and thus tightly bind to it.
If the stack moves the responsibility to another class or does it itself is not really very important, since I can't think of a case right now, where this would really benefit my stack-class.
It would benefit from this seperation, if I would later want to change how my array-class works. This would make life a little easier, than modifying the stack class for this purpose, but when do I really need to change this behaviour? (ok, not really a good question, because there may always be something wrong)
Whatever, maybe there is a much better point to it I cannot see right now. Seperation of responsibility is always a nice topic. ;)
@_goat:
Thanks for your input and no, I don't expect you to redesign my whole class for me, even though you did it already. This is much more than I expected.
To 1: Yes, I'm working on this right now, nice explanation.
To 3: Wow, I'm using these type of comments for function-explanations for so long now and never noticed this. Yes, you're right, I will stick to the other way.
To 4: Thanks for this, I really understand things much better now. Well, you made a little mistake, I guess:
T pop() { if(counter > 0) return storage[--counter]; else return NULL; };Counter had to be pre-decremented, because after a push, counter is always one number bigger than there are actual elements on the stack.
Hmmm, a TRILLION memory leaks sound, uhm, very much. Here is my class:
template <class T>class Stack { unsigned int size; T* storage; unsigned int counter; public: // // The Constructor // Stack(unsigned int theSize) : size(theSize), counter(0), storage(NULL) { storage = new T[theSize]; }; // // The destructor // Release the occupied memory // ~Stack() { delete storage; } // // Push something on the stack // void push(const T& data) { storage[counter++] = data; }; // // Pop something from the stack // T pop() { if(counter >= 0) { T data = storage[--counter]; //delete storage[counter+1]; <-- Error return data; } else { return NULL; } }; // // Peek the last object from the stack // T& peek() { return storage[counter]; };};I tried to eliminate one memory-leak by deleting "storage" in the destructor. There shouldn't be much more, right?
As you can see in my pop()-method, I tried to free the memory of a popped element on the stack, but the compiler gave me an error:
"error C2541: 'delete' : cannot delete objects that are not pointers"
Hmmm, what I thought the class did was to get variables passed to push and then take the address and just store the address of the objects.
So I made a quick test:
Stack<int> Test(10); int x1 = 15; int x2 = 13; int x3 = 10; Test.push(x1); Test.push(x2); Test.push(x3); // Reassignment here, to check if a pointer or a value has been passed x1 = 25; cout << (Test.pop()) << endl; cout << (Test.pop()) << endl; // Outputs '15', so nothing has changed cout << (Test.pop()) << endl;This looks strange to me. Shouldn't a variable declared like:
"T* storage;" store a pointer / an array of pointers to a type T?
In the push()-function the argument is passed by reference, so that means, when I change the variable inside the push()-function, it would be changed on the outside too, right?
But now the variable is assigned as
"storage[counter++] = data;"
which means, that the value of data is stored, basically just a copy.
When I change the assignment to "...= &data" it doesn't work. And why does it work now? I thought storage should store pointers? I'm confused. How would I achive to store pointers?
Well, when I think about it now, I don't even know if this would be a good idea. Imagine that I have a stack class which stores pointers instead of values and I have this code.
void fillStack(Stack<int> &theStack) { int x1 = 10; int x2 = 20; int x3 = 30; int x4 = 40; theStack.push(&x1); theStack.push(&x2); theStack.push(&x3); theStack.push(&x3);}This function gets called from somewhere. Now, when fillStack() is called, it pushes 4 pointers to the integer on the stack. Actually, this isn't the greatest example ever, but it should show the behaviour.
Whatever, when the function goes out of scope now, the stack should now be filled with pointers to "empty" locations in the memory, since the variables do not exist anymore, right?
And now I'm confused. I thought that by passing just the addresses it would be faster than copying everything by value. Imagine a very large and complex object, getting these kind of objects onto the stack could definately be a bottle-neck. But what can I do against this?
Hmmm, maybe something like this?
void fillStack(Stack<int> &theStack) { int x1 = new int(10); int x2 = new int(20); int x3 = new int(30); int x4 = new int(40); theStack.push(&x1); theStack.push(&x2); theStack.push(&x3); theStack.push(&x3);}This would prevent the variables to go out of scope and get destroyed, right? I couldn't think of any other way.
I know these are alot a of questions, but I really want to learn this the right way. Thanks for helping me up to this point already, I'm now trying to make the stack dynamically-sized.
Just a little bug in your final version.
storage = new T[theSize];
should be deleted with []
delete [] storage;
storage = new T[theSize];
should be deleted with []
delete [] storage;
- When dealing with templates, typename is identical to class. Some people (myself included) prefer the use of typename just for clarity.
- Yes, int foo[10]; is a C-style array. There is, generally speaking, very little safety or reliability for such arrays. They are quite error prone and a royal pain to manage. It's up to you whether learning how to manage them is worth your time (I'd say so, if only so you can appreciate how much better std::vector is) but I'd agree that you should probably learn that separately from trying to build a Stack class. Trying to learn too much at once is risky, especially in a language like C++, which is enough of a minefield as it is.
- Separating array management out of the Stack class is a good idea. Yes, in a very simple vacuum environment it doesn't make any difference, but it's always best to think in the long term - especially when designing classes like a Stack. In this case, managing a dynamic array is something that is going to be used all over the place, and having it in a central location (rather than implementing it in Stack, and again in Queue, and again in Vector, etc.) is a very good idea. It doesn't directly benefit Stack by itself, but it'll be a tremendous benefit to your project overall in the long run.
If you'd like to learn to do manual array management, I'd recommend implementing a class for that first. Then, use that class to build your Stack class. That'll cover C-style arrays without overloading you with too many new things at once, and also give you some good experience in designing multiple classes that work together. - In C++, it is sort of a de-facto standard that containers (such as a Stack) are not responsible for freeing pointers. If your Stack contains a lot of pointers to other objects, it shouldn't be the Stack's job to delete those pointers. The std library works on this principle, as does Boost. Your Stack should just store "stuff" - it shouldn't care about whether the "stuff" is integers, pointers, or entire objects; that's the idea of using templates, after all.
Safe storage of dynamically-allocated objects in a container is usually done by combining a smart pointer class (such as std::auto_ptr or, better, one from Boost) with the container; your container holds smart pointer objects which ensure the memory is freed at the right time. In any case, it's still the job of the client to worry about it; your Stack class can safely stick its fingers in its ears, close its eyes, and sing loudly [wink]
I think that covers most of your questions.
Im not sure if someone has mentioned it already but shouldnt
be like this?
T& peek() { return storage[counter];};be like this?
T& peek() { return storage[counter-1];};Quote:Original post by ApochPiQ
- When dealing with templates, typename is identical to class. Some people (myself included) prefer the use of typename just for clarity.
That's not entirely accurate. You cannot use the typename keyword when using a template as a template parameter. So for instance:
template< template< typename A > typename B, typename A >The nested template cannot be a typename, but a class, so it has to be:
template< template< typename A > class B, typename A ></offtopic>
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
