StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
1085272
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
13
CommunityOwnedDate
CreationDate
2009-07-06T03:19:42.693
FavoriteCount
0
LastActivityDate
2009-07-06T16:04:14.850
LastEditDate
2009-07-06T16:04:14.850
LastEditorUserId
33213
OwnerUserId
33213
ParentId
1085238
PostTypeId
2
Score
23
ViewCount
0
LastEditorDisplayName
text
Body
First, a few general comments which don't cause problems in this case, but some may do so in other situations: You should only throw exceptions derived from the class <code>std::exception</code>. C++ does allow you to throw any type (like a string, in your case), but it's a really bad idea. Class members should be initialized with initializer lists, as shown below: (this can cause errors in other cases. If you don't use the initializer list, the members are first default-constructed, and then the assignment operator is used in the body of the constructor to overwrite them. Not all types have an assigment operator, or the assignment operator may have undesirable side effects, so not using initializer lists can be problematic) <pre><code>Node(int val, Node* ptrToLast) : value(val), prev(ptrToLast) {} Stack() : size(0), top(NULL) {} </code></pre> Naming your functions <code>return*</code> us pretty pointless. Just call them <code>size()</code> and <code>topPtr()</code>, or perhaps <code>getSize()</code> and <code>getTopPtr()</code> Second, you didn't follow the rules. ;) Your stack class has two member variables, it was only allowed to have one. :) Finally, things that break the stack: This will crash, as you try to dereference a null pointer: <pre><code>void test() { Stack s; s.peek(); // crashes } </code></pre> This will leak memory, as the allocated node is never deleted (the Stack destructor should do that): <pre><code>void test() { Stack s; s.push(1); } </code></pre> The destructor should look something like this: <pre><code>~Stack() { while (top != NULL){ Node* next = top.returnPtr(); delete top; top = next; } } </code></pre> This one should be fun too: <pre><code>void test() { Stack s; s.push(1); Stack t(s); s.pop(); } </code></pre> <code>t.returnSize()</code> will now return 1, but <code>t.top</code> points to the node in <code>s</code> that was just deleted. This should be fixed by defining a copy constructor and an assigment operator for the stack (and perhaps for the node class as well) The copy constructor would look like this: <pre><code>Stack(const Stack& s); </code></pre> and is called if you initialize one stack from another, like in the above. The assignment operator looks like this: <pre><code>Stack& operator= (const Stack& s); </code></pre> and is called if I assign one stack to another, after both are initialized: <pre><code>Stack s; Stack t; t = s; // now both are already initialized, so the assigment operator is used, not the copy constructor </code></pre> The role of these functions is to ensure that t becomes a copy of <code>s</code>. So each node in <code>s</code> should be copied, and assigned to <code>t</code>, to avoid them pointing to the same nodes. (Which is a wonderful example of your question about ownership earlier, btw. The nodes should belong to exactly one Stack object. If it becomes shared between multiple, you have a problem, and it's just a matter of time before it turns into a crash) And finally, if we want to get a bit nastier: <pre><code>void test() { Stack s; s.push(1); s.push(2); } </code></pre> What happens if the memory allocation for the second node fails (perhaps we ran out of memory. Unlikely, but it can happen). An exception is thrown after you incrmented size. The size of s will now be 2, even though <code>top</code> still points to the first node If you think this is too unlikely a problem to be taken seriously, imagine a small extension to your class. Let's say it was a template, so that it could store other types than an int. That means that every time we create a node, we have to call the value type's copy constructor. That could throw an exception too. We don't know, because we have no clue which type the user might try to store in the stack. The notion of "Exception safety" is important and really really difficult to get right. Basically, which state is your class in if an exception is thrown? Is it still in a valid state? (it should always be). Has it lost any data (for some cases that might be unavoidable, for others it can be avoided with care), and if it has lost data, has it been deleted correctly? Destructors called, memory released? (again, this should always be the case) The last point here is why I was so sure you'd have at least one bug. Everyone gets exception safety wrong, including me most of the time. Writing a correct implementation of sometihng as simple as a stack is surprisingly difficult in C++. :) Bonus: In response to comments asking about copy constructors, destructors and RAII, let's just do the whole thing: First, let me say that there is probably one or two bugs left I haven't spotted. Second, here's the code I tested against, and all the following passes it. Feel free to run your own code through it as well. (it should work as is, except you'll have to rename the <code>getSize</code> function): (the <code>live</code> variable is one I added for debugging. I've modified my Stack implementations so that constructors increment it, and destructors decrement it, just to verify that the number of constructions and destructions are equal. This should obviously be removed from the Stack class once you're sure it works <h2>Test code</h2> <pre><code>static int live; // debugging - keeps track of how many nodes have been allocated. Constructors add 1, destructors subtract. It should end in 0 #include "stack.h" #include <iostream> #include <cassert> int main(){ { // test stack creation + push Stack s; s.push(1); s.push(2); s.push(3); assert(s.getSize() == 3); Stack t; t.push(4); t.push(5); t.push(6); assert(t.getSize() == 3); // test assigment operator when both stacks contain data s = t; assert(s.getSize() == 3); assert(s.peek() == 6); assert(t.peek() == 6); Stack u(s); // test self assigment when stack contains data u = u; assert(u.getSize() == 3); assert(u.peek() == 6); Stack v; // test copy construction from stack with data Stack w(t); assert(w.getSize() == 3); assert(w.peek() == 6); assert(t.getSize() == 3); assert(t.peek() == 6); // test assignment operator when source is empty, destination contains data w = v; assert(w.getSize() == 0); assert(v.getSize() == 0); // test copy construction from empty stack Stack x(v); assert(x.getSize() == 0); assert(v.getSize() == 0); // test pop assert(t.pop() == 6); assert(t.pop() == 5); assert(t.pop() == 4); assert(s.pop() == 6); assert(s.pop() == 5); assert(s.pop() == 4); } // at this point, all allocated stacks go out of scope, so their destructors are called, so now is a good time to check for memory leaks: assert(live == 0); } </code></pre> <hr> <h2>Fixed implementation</h2> Now, first the straightforward fix. Copy constructor, assignment operator and destructor have been added on the Stack class. The Node class is still problematic if used in isolation, but as long as it is only used through the Stack, we can make sure nodes get copied and deleted properly. Unfortunately, <code>Stack</code> now needs access to <code>Node.tail_</code> in order for copying to work, so I made it a friend. So it works, but it's not elegant. <pre><code>#include <stdexcept> // for std::exception class Stack; class Node { private: // changed naming to head/tail, which are commonly used in implementations of linked lists like this. The head is the current element, tail is a pointer to the remainder int head_; Node* tail_; public: friend class Stack; // this is necessary for the Stack copy constructor in order to modify the tail pointer after the node is created. // the elegant solution had been to define a copy constructor on the Node class as well, but we'll get to that int head() const { return head_; } Node* tail() const { return tail_; } Node(int val, Node* prev) : head_(val), tail_(prev) { ++live; } // use initializer list ~Node() { --live; } Node(const Node& other) : head_(other.head_), tail_(other.tail_){ ++live; }; // this could be omitted, but I use it to update 'live' for debugging purposes }; class Stack { private: Node* top; // int size; // we don't actually need the size at all, according to spec, so I removed it to keep things simple bool empty() const { return top == NULL;} void freeNodes() { // helper function to avoid duplicate code while (!empty()){ pop(); } } public: Stack() : top() {} // use initializer list ~Stack() { // destructor - the stack is being deleted, make sure to clean up all nodes freeNodes(); } Stack(const Stack& other) : top() { // copy constuctor - we're being initialized as a copy of another stack, so make a copy of its contents if (other.empty()){ return; } top = new Node(*other.top); // copy the first node, to get us started Node* otherNext = other.top->tail(); Node* current = top; while (otherNext != NULL){ current->tail_ = new Node(*otherNext); // copy the current node current = current->tail(); // move to the next node otherNext = otherNext->tail(); } } Stack& operator= (const Stack& other) { if (this == &other){ // If we assign this stack to itself (s = s), bail out early before we screw anything up return *this; } //now create the copy try { if (other.empty()){ freeNodes(); top = NULL; return *this; } // naively, we'd first free our own stack's data before constructing the copy // but what happens then if an exception is thrown while creating the copy? We've lost all the current data, so we can't even roll back to a previous state // so instead, let's simply construct the copy elsewhere // this is almost straight copy/paste from the copy constructor. Should be factored out into a helper function to avoid duplicate code Node* newTop = new Node(*other.top); // copy the first node, to get us started Node* otherNext = other.top->tail(); Node* current = newTop; while (otherNext != NULL){ current->tail_ = new Node(*otherNext); // copy the current node current = current->tail(); // move to the next node otherNext = otherNext->tail(); } // once we're sure that we're able to create the copy of the other stack, we're ready to free the current one // this is a bit of duplicate code freeNodes(); top = newTop; return *this; } catch (...){ // if an exception was thrown throw; // and rethrow the exception so the application can deal with it } } // Node* returnTopPtr() { return top; } // not necessary. It's not a required part of the public interface, and class members can just access the top variable directly void push(int); int pop(); int peek() const; int getSize() const{ if (empty()){ return 0; } int i = 0; for (Node* cur = top; cur != NULL; cur = cur->tail_, ++i){} return i; } }; void Stack::push(int value) { Node* currentTop = top; top = new Node(value, currentTop); // this could throw an exception, but if it does, our stack will simply be left unchanged, so that's ok } int Stack::peek() const { if (empty()){ throw std::exception("Stack is empty"); } return top->head(); } int Stack::pop() { if (empty()){ throw std::exception("Stack is empty"); } Node* tail = top->tail(); int result = top->head(); delete top; top = tail; return result; } </code></pre> <hr> <h2>RAII v. 1</h2> <a href="http://en.wikipedia.org/wiki/RAII" rel="noreferrer">RAII</a> is a lousy name for a vital technique. The basic idea is that every resource allocation (including, but not limited to, memory allocations with <code>new</code>.) should be wrapped in a class which takes care of copying or deleting the resource as necessary. In our case, rather than having <code>Stack</code> keep track of all the nodes, we could simplify things a bit by making the <code>Node</code> class itself do most of that work. Now <code>Node</code> has been given copy constructor, assignment operator and destructor too. The stack now just has to keep track of the <code>top</code> node... almost. It is still a bit iffy because <code>Stack.push</code> allocates new nodes, but <code>Node</code> is now responsible for most of the deletions. . However, it does allow us to get rid of the loops we needed before to delete or copy the node list. <code>Stack still needs to access the</code>tail_<code>member of</code>Node`, but this time, I made an accessor function instead of making the class a member. Overall, better, but I'm still not happy with it. <pre><code>#include <stdexcept> class Node { private: int head_; Node* tail_; public: int head() const { return head_; } Node* tail() const { return tail_; } Node*& tail() { return tail_; } // Another way to allow Stack to modify the tail. Needed for pop() Node(int val, Node* prev = NULL) : head_(val), tail_(prev) { ++live; } ~Node(){ --live; delete tail_; } // it is safe to call delete on a NULL pointer Node(const Node& other) : head_(other.head()), tail_(NULL) { ++live; if (other.tail() == NULL){ return; } tail_ = new Node(*other.tail()); } Node& operator= (const Node& other){ if (this == &other){ return *this; } head_ = other.head(); if (other.tail() != NULL){ return *this; } Node* oldTail = tail_; try { tail_ = new Node(*other.tail()); } catch(...){ tail_ = oldTail; throw; } } }; class Stack { private: Node* top; bool empty() const { return top == NULL;} public: Stack() : top() {} ~Stack() { delete top; } Stack(const Stack& other) : top(){ if (other.empty()){ return; } top = new Node(*other.top); } Stack& operator= (const Stack& other) { if (this == &other){ return *this; } Node* oldTop = top; try { top = NULL; if (other.top != NULL){ top = new Node(*other.top); } delete oldTop; return *this; } catch (...){ delete top; top = oldTop; throw; } } void push(int); int pop(); int peek() const; int getSize() const{ if (empty()){ return 0; } int i = 0; for (Node* cur = top; cur != NULL; cur = cur->tail(), ++i){} return i; } }; void Stack::push(int value) { Node* currentTop = top; top = new Node(value, currentTop); } int Stack::peek() const { if (empty()){ throw std::exception("Stack is empty"); } return top->head(); } int Stack::pop() { if (empty()){ throw std::exception("Stack is empty"); } Node* tail = top->tail(); int result = top->head(); if (top != NULL){ top->tail() = NULL; // detach top from the rest of the list delete top; } top = tail; return result; } </code></pre> <hr> <h2>RAII v.2</h2> To solve the problems mentioned above, I decided to change my strategy a bit. <code>Node</code> now does all the heavy lifting, including the push/pop/peek operations. <code>Stack</code> is simply a thin wrapper around these. This turned out to solve most of the problems. <code>Stack</code> no longer needs to mess around with private members of <code>Node</code>, and we have some clearer rules for ownership. The stack owns the top node, and every non-top node is owned by its parent -- and this time, the owner both creates, copies and destroys the node. Much more consistent. To implement this, I had to add an <code>isLast</code> function on the Node class because otherwise, <code>Stack.pop</code> had no way of knowing whether or not it was time to delete <code>top</code>. I'm not 100% happy with this solution either (and if I hadn't removed the size member from the stack, I could have used that to solve the problem) But overall, this one is both cleaner and simpler than the above attempts. (It's the only one I spent less than an hour debugging, for one thing. ;)) <pre><code>#include <stdexcept> class Node { public: Node(int value, Node* prev = 0) : head(value), tail(prev) { ++live;} ~Node() { --live; delete tail; } Node(const Node& other) : head(other.head), tail(0) { ++live; if (other.tail != 0){ tail = new Node(*other.tail); } } Node& operator= (const Node& other){ if (this == &other){ return *this; } Node* oldTail = tail; tail = new Node(*other.tail); delete oldTail; head = other.head; return *this; } void push(int val){ tail = new Node(head, tail); head = val; } int peek(){ return head; } void pop(){ Node* oldTail = tail; head = tail->head; tail = tail->tail; // lol oldTail->tail = 0; delete oldTail; } bool isLast() { return tail == NULL; } int getSize() const{ int i = 0; for (const Node* cur = this; cur != NULL; cur = cur->tail, ++i){} return i; } private: Node* tail; int head; }; class Stack { public: Stack() : top(){} ~Stack() { delete top; } Stack(const Stack& other) : top() { if (other.empty()){ return; } top = new Node(*other.top); } Stack& operator= (const Stack& other){ if (this == &other){ return *this; } Node* newTop = NULL; if (!other.empty()){ newTop = new Node(*other.top); } delete top; top = newTop; return *this; } void push(int val){ if (empty()) { top = new Node(val); } else { top->push(val); } } int peek(){ if (empty()){ throw std::exception("Empty stack"); } return top->peek(); } int pop(){ int result = peek(); if (top->isLast()){ delete top; top = NULL; } else { top->pop(); } return result; } int getSize() const{ if (empty()){ return 0; } return top->getSize(); } private: bool empty() const { return top == NULL; } Node* top; }; </code></pre> Since all this started as an attempt to show you why C++ isn't a very nice beginners language, I think I can safely say mission accomplished! :)
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. PONode-based stack class (need peer review)
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USjalf
UserOwnerUserId
1. USjalf
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. PONode-based stack class (need peer review)
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.