模拟std：：堆栈的基本接口

Question

我试图在我的实现中模仿std::stack (只是基本的接口--没有迭代器/分配程序)。由于处理所有内存分配/取消分配都有问题，所以我阅读了这。

虽然我的实现似乎完美无缺，但我仍然对以下几点缺乏信心：

1. 没有内存泄漏。
2. 所有的例程都是完全性能和空间优化的。
3. 我对复制和交换成语的使用是正确的。
4. 没有任何更好的方法来显示堆栈的内容(请参阅重载的operator<<)。

你能检查一下，看看是否可以改进吗？

using  namespace std;
template<typename T> struct mystack_node  // The data structure for representing the "nodes" of the stack
{
    T data;
    mystack_node *next;
};

template<typename T> class mystack;
template<typename T>ostream& operator <<(ostream& out,const mystack<T> &a);

template<typename T> class  mystack
{
    unsigned int stack_size;  // A variable keeping the record of number of nodes present in the stack
    mystack_node<T> *stack_top;  //  A pointer pointing to the top of the stack
    void mystack_swap(mystack &a,mystack &b)  //  Swap function used in the assignment  operator ( Copy-and-Swap Idiom )
    {
        swap(a.stack_size,b.stack_size);
        swap(a.stack_top,b.stack_top);
    }
public:
    mystack():stack_size(0),stack_top(NULL) {}  //  Default Constructor
    mystack(const mystack& other):stack_size(0),stack_top(NULL)  //  Copy constructor
    {
        int i=0;
        vector<T> vec(other.stack_size);  //  A vector for storing a backup of all the nodes in the "other" stack
        mystack_node<T> *temp=other.stack_top;
        while(temp!=NULL)
        {
            vec[i++]=temp->data;
            temp=temp->next;
        }
        for(i=(int)vec.size()-1; i>=0; i--)
        {
            push(vec[i]);
        }
    }
    ~mystack()  //  Destructor
    {
        mystack_node<T> *temp=stack_top;
        while(temp!=NULL)
        {
            temp=temp->next;
            delete stack_top;
            stack_top=temp;
        }
    }
    mystack& operator = (mystack other)  // Assignment operator
    {
        mystack_swap(*this,other);
        return *this;
    }
    void push(const T &val)  // Add a new node to the stack
    {
        mystack_node<T> *temp=new mystack_node<T>;
        temp->data=val;
        temp->next=stack_top;
        stack_top=temp;
        stack_size++;
    }
    void pop()    //  Remove the "top" node from the stack
    {
        if(stack_top!=NULL)   //  Don't do anything if the stack is already empty
        {
            mystack_node<T> *temp=stack_top->next;
            delete stack_top;
            stack_top=temp;
            stack_size--;
        }
    }
    unsigned int size() // Returns the number of nodes in the stack
    {
        return stack_size;
    }
    bool empty() // Returns whether if the stack is empty or not
    {
        return stack_size==0;
    }
    T top()  // Returns the "top" node from the stack
    {
        return (*stack_top).data;  // Deliberately left Out-of-Bound exception checking...
    }
    friend ostream& operator << <T> (ostream&,const mystack&);
};
template<typename T>ostream& operator <<(ostream& out,const mystack<T> &a) // Output operator to show the contents of the stack
{
    mystack_node<T> *temp=a.stack_top;
    while(temp!=NULL)
    {
        out<<temp->data<<" ";
        temp=temp->next;
    }
    return out;
}  

编辑：

1. 将size()、empty()和top()作为const函数。
2. 将stack_size的类型从unsigned int更改为size_t。
3. 在struct mystack_node的私有部分中定义了class mystack，这样代码的任何其他部分都无法访问它。

using  namespace std;

template<typename T> class mystack;
template<typename T>ostream& operator <<(ostream& out,const mystack<T> &a);

template<typename T> class  mystack
{
    struct mystack_node  // The data structure for representing the "nodes" of the stack
    {
        T data;
        mystack_node *next;
    };
    size_t stack_size;  // A variable keeping the record of number of nodes present in the stack
    mystack_node *stack_top;  //  A pointer pointing to the top of the stack
    void mystack_swap(mystack &a,mystack &b)  //  Swap function used in the assignment  operator ( Copy-and-Swap Idiom )
    {
        swap(a.stack_size,b.stack_size);
        swap(a.stack_top,b.stack_top);
    }
public:
    mystack():stack_size(0),stack_top(NULL) {}  //  Default Constructor
    mystack(const mystack& other):stack_size(0),stack_top(NULL)  //  Copy constructor
    {
        int i=0;
        vector<T> vec(other.stack_size);  //  A vector for storing a backup of all the nodes in the "other" stack
        mystack_node *temp=other.stack_top;
        while(temp!=NULL)
        {
            vec[i++]=temp->data;
            temp=temp->next;
        }
        for(i=(int)vec.size()-1; i>=0; i--)
        {
            push(vec[i]);
        }
    }
    ~mystack()  //  Destructor
    {
        mystack_node *temp=stack_top;
        while(temp!=NULL)
        {
            temp=temp->next;
            delete stack_top;
            stack_top=temp;
        }
    }
    mystack& operator = (mystack other)  // Assignment operator
    {
        mystack_swap(*this,other);
        return *this;
    }
    void push(const T &val)  // Add a new node to the stack
    {
        mystack_node *temp=new mystack_node;
        temp->data=val;
        temp->next=stack_top;
        stack_top=temp;
        stack_size++;
    }
    void pop()    //  Remove the "top" node from the stack
    {
        if(stack_top!=NULL)   //  Don't do anything if the stack is already empty
        {
            mystack_node *temp=stack_top->next;
            delete stack_top;
            stack_top=temp;
            stack_size--;
        }
    }
    size_t size() const // Returns the number of nodes in the stack
    {
        return stack_size;
    }
    bool empty() const // Returns whether if the stack is empty or not
    {
        return stack_size==0;
    }
    T top() const  // Returns the "top" node from the stack
    {
        return (*stack_top).data;  // Deliberately left Out-of-Bound exception checking...
    }
    friend ostream& operator << <T> (ostream&,const mystack&);
};
template<typename T>ostream& operator <<(ostream& out,const mystack<T> &a) // Output operator to show the contents of the stack
{
    typename mystack<T>::mystack_node *temp=a.stack_top;
    while(temp!=NULL)
    {
        out<<temp->data<<" ";
        temp=temp->next;
    }
    return out;
}

Answer 1

基于Edit 2：

别这么做：

using  namespace std;

mystack_node可能是一个结构。但是它仍然可以有成员和构造者。如果您添加了一个构造函数，您将在下面添加或推送中使您的生活变得更简单。

    struct mystack_node  // The data structure for representing the "nodes" of the stack
    {
        T data;
        mystack_node *next;

        // Add
        mystack_node(T const& d, mystack_node* n)
             : data(d)
             , next(n)
        {}
    };

如其他地方所述。定义标准交换函数：https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom

    void mystack_swap(mystack &a,mystack &b)

复制构造函数被破坏。

将数据复制到一个局部向量中，然后不要对它做任何事情。

    mystack(const mystack& other):stack_size(0),stack_top(NULL)

当您尝试使用向量使其异常安全时，您在正确的行上。但你不需要走这么远。您只需要确保在复制过程中是否存在异常，从而释放任何分配的内存。注如果从构造函数引发异常，则不会调用析构函数。

由于您只有一个单独链接的列表，所以我将使用递归来跟踪副本。

    mystack(const mystack& other)
        : stack_size(0)
        , stack_top(NULL)
    {
        try
        {
             recursive_copy(other.stack_top);
             stack_size = other.stack_size;
        }
        catch(...)
        {
             // If there is an exception
             // Release all resources then
             // let the exception continue to propagate.
             release_stack();
             throw;
        }            
    }

    void recursive_copy(mystack_node* head)
    {
         if (head == NULL)
         {    return;
         }
         // Recursively go to the end of the list
         recursive_copy(head->next);

         // On your way back up.
         // Build each node onto the stack.
         stack_top = new mystack_node(head.data, stack_top);
    }

在析构函数中，我会使用for(;;)循环。这样你就可以把所有的控制放在一个地方。因为构造函数现在可能可以与构造函数使用相同的函数。

    ~mystack()  //  Destructor
    {
        release_stack();
    }

    release_stack() noexcept  /* or C++03 throws() */
    {
        mystack_node* next;
        for(mystack_node* loop=stack_top; loop; loop = next)
        {
            next =loop->next;
            delete loop;
        }
    }

通过将构造函数添加到mystack_node中，push变得更加可读性。

    void push(const T &val)  // Add a new node to the stack
    {
        stack_top = new mystack_node(val, stack_top);
        stack_size++;
    }

由于您无法控制T类型，所以必须假定对其方法的所有调用都是不例外安全的。这包括析构函数。这意味着您需要编写代码，以便在调用异常不安全方法之前对对象进行完全更改。

    void pop()    //  Remove the "top" node from the stack
    {
        if(stack_top!=NULL)   //  Don't do anything if the stack is already empty
        {
            mystack_node* oldTop = stack_top;
            stack_top=stack_top->next;
            stack_size--;

            // Put the delete at the end.
            // Your object has now been fully mutated
            // Thus if the destructor throws it will not harm your object
            // by leaving it in an undefined state.
            delete oldTop;

            // In your old version where you called delete before modifying
            // stack_top. An exception would have left your object pointing
            // at an object that had been deleted.
        }
    }

为什么不返回对顶部节点的引用？

    T top() const  // Returns the "top" node from the stack

如果您这样做，您可能需要两个版本。一个const和一个非成本版本。

    T& top();  // See below.
    T const& top() const   {return const_cast<mystack>(*this).top();}

而不是取消引用对象，然后使用.运算符。为了提高可读性，最好只使用->操作符。

        return (*stack_top).data;

        // Easier to read as:
        return stack_top->data;

一件小事。

     mystack_node   *oldTop;    // Looks very C like

     // In C++ it is more common to put the * on the left with the type.
     // The argument being the `*` is part of the type, and C++ is
     // all about type correctness.
     //
     // Its not a big thing and there is a lot of code your way around
     // but it is in the minority (and it helps C++ developers spot
     // C developers pretending to code in C++  :-) )

     mystack_node*   oldTop;    // More C++ like

Answer 2

推荐的交换函数实现是一个名为friend swap (https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom)的

public:
...
friend void swap(mystack &a, mystack &b)
{
    using std::swap;

    swap(a.stack_size, b.stack_size);
    swap(a.stack_top, b.stack_top);
}

而赋值操作符是：

mystack& operator= (mystack other)
{
    using std::swap;

    swap(*this, other);
    return *this;
}