我最近根据指令编写了一个基于节点的堆栈类(代码之前的注释中的规范,取自论坛帖子).我被告知要在这里发布它以供SO社区的一位更友好的成员审阅,所以在这里.为简单起见:我将定义与实现相结合.我知道何时使用头文件=)
主要是,我想知道我对删除的使用是否合理.在使用析构函数时,我仍然不确定自己; 规范使它听起来像我应该删除节点的唯一时间应该是在流行期间,其他任何东西是不安全的.我也不明白这里使用的是复制构造函数/赋值构造函数.
无论如何,关于代码的任何错误或评论都会很棒.
/*stack class
Background: the specs for this are, verbatim:
"Write a node-based stack class smile.gif
The stack is one of the most fundamental data structures used in computer science.
A stack has three basic operations:
push(value) - puts a value on the top of the stack
pop() - removes and returns the value that's on the top of the stack
peek() - return (but does not remove) the value off the top of the stack
Before creating the stack, you first have to create a Node class, which is a
very basic class with just two member variables: the value of the node, and a
pointer to the previous node in the stack.
Your stack should have only one member variable: the top node of the stack.
When you push, you add a node with the new value, with it's previous pointer
pointing towards the current stack top item. When you pop, you delete the top
node and then set the top of the stack to whatever that node's previous node
pointer was.
push, pop, and peek must all run in constant time.
You should write it so that it can only push (and pop/peek) ints."
*/
#include <string>
#include <iostream>
class Node
{
private:
int value;
Node* prev;
public:
int returnValue() { return value; }
Node* returnPtr() { return prev; }
/* constructors and destructors */
Node(int val, Node* ptrToLast)
{
value = val;
prev = ptrToLast;
}
};
class Stack
{
private:
Node* top;
int size;
public:
Stack() { size = 0; top = NULL; }
//added this after told the need for a destructor; not sure if it works
~Stack() {
while (top != NULL)
{
Node* tempPtr = top.returnPtr();
delete top;
top = tempPtr;
}
}
Node* returnTopPtr() { return top; }
void push(int);
int pop();
int peek();
//bonus; figured it might be worth knowing how many
//nodes are in a given stack
int returnSize();
};
int Stack::returnSize()
{
return size;
}
void Stack::push(int value)
{
++size;
Node* tempPtr = top;
top = new Node(value, tempPtr);
}
int Stack::peek()
{
return top->returnValue();
}
int Stack::pop()
{
const std::string throwStr = "You are trying to access/delete a node that doesn't exist. Seriously. ";
if (size == 0)
{
throw(throwStr);
}
--size;
Node* tempPtr = top->returnPtr();
int tempVal = top->returnValue();
delete top;
top = tempPtr;
return tempVal;
}
jal*_*alf 23
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 std::exception. 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)
Node(int val, Node* ptrToLast) : value(val), prev(ptrToLast) {}
Stack() : size(0), top(NULL) {}
Naming your functions return* us pretty pointless. Just call them size() and topPtr(), or perhaps getSize() and getTopPtr()
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:
void test() {
Stack s;
s.peek(); // crashes
}
This will leak memory, as the allocated node is never deleted (the Stack destructor should do that):
void test() {
Stack s;
s.push(1);
}
The destructor should look something like this:
~Stack() {
while (top != NULL){
Node* next = top.returnPtr();
delete top;
top = next;
}
}
This one should be fun too:
void test() {
Stack s;
s.push(1);
Stack t(s);
s.pop();
}
t.returnSize() will now return 1, but t.top points to the node in s 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:
Stack(const Stack& s);
如果你从另一个堆栈初始化一个堆栈,就会被调用,如上所述.赋值运算符如下所示:
Stack& operator= (const Stack& s);
并且在初始化两个堆栈后,如果我将一个堆栈分配给另一个堆栈,则调用它:
Stack s;
Stack t;
t = s; // now both are already initialized, so the assigment operator is used, not the copy constructor
这些功能的作用是确保T成为一个复制的s.因此s应该复制和分配每个节点t,以避免它们指向相同的节点.(这是你早期关于所有权的问题的一个很好的例子,顺便说一句.节点应该只属于一个Stack对象.如果它在多个之间共享,你就会遇到问题,而且它变成崩溃只是时间问题)
最后,如果我们想要有点唠叨:
void test() {
Stack s;
s.push(1);
s.push(2);
}
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 top 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.
"例外安全"的概念很重要,而且确实很难做到正确.基本上,如果抛出异常,哪个州是你的班级？它仍处于有效状态吗？(它应该永远是).它是否丢失了任何数据(对于某些可能不可避免的情况,对于其他情况可以小心避免),如果数据丢失,是否已正确删除？Destructors叫,内存释放？(再次,这应该是这种情况)
这里的最后一点是为什么我确信你至少有一个bug.每个人都有异常安全错误,包括我在内的大部分时间.在C++中编写一个像堆栈这样简单的正确实现是非常困难的.:)
奖金:
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 getSize function): (the live 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
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);
}
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, Stack now needs access to Node.tail_ in order for copying to work, so I made it a friend. So it works, but it's not elegant.
#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;
}
RAII is a lousy name for a vital technique. The basic idea is that every resource allocation (including, but not limited to, memory allocations with new.) should be wrapped in a class which takes care of copying or deleting the resource as necessary.
In our case, rather than having Stack keep track of all the nodes, we could simplify things a bit by making the Node class itself do most of that work. Now Node has been given copy constructor, assignment operator and destructor too. The stack now just has to keep track of the top node... almost. It is still a bit iffy because Stack.push allocates new nodes, but Node 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.
Stack still needs to access thetail_member ofNode`, 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.
#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;
}
To solve the problems mentioned above, I decided to change my strategy a bit. Node now does all the heavy lifting, including the push/pop/peek operations. Stack is simply a thin wrapper around these. This turned out to solve most of the problems. Stack no longer needs to mess around with private members of Node, 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 isLast function on the Node class because otherwise, Stack.pop had no way of knowing whether or not it was time to delete top. 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. ;))
#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;
};
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!
:)