7
\$\begingroup\$

I am trying to mimic std::stack in my implementation (just the basic interface - no iterators / allocators). Since I was having trouble handling all the memory allocation/deallocation, I read this.

Although my implementation seems to work flawlessly, I'm still not confident about these things:

  1. There is no memory-leak
  2. All the routines are fully performance and space-optimized
  3. My usage of Copy-and-Swap idiom is correct
  4. There isn't any better way of displaying the contents of a stack (see the overloaded operator<<).

Could you please review it to see if it could be improved?

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;
}  

EDIT:

  1. Made size(), empty() and top() as const functions.
  2. Changed the type of stack_size from unsigned int to size_t.
  3. Defined struct mystack_nodein the private section of class mystack so that it is inaccessible to any other part of the code.

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;
}
\$\endgroup\$
6
\$\begingroup\$

Based on Edit 2:

Don't do this:

using  namespace std;

The mystack_node may be a structure. But it can still have members and construcors. If you add a constructor you will make your life simpler in the add or push below.

    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)
        {}
    };

As noted elsewhere. Defined a standard swap function: https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom

    void mystack_swap(mystack &a,mystack &b)

The copy constructor is broken.
You copy the data into a local vector then don't do anything with it.

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

You are on the correct line when you try an make it exception safe with a vector. But you don't need to go so far. You just need to make sure if there is an exception during the copy that you free any allocated memory. Note if an exception is thrown from the constructor then the destructor will not be called.

As you only have a singly linked list I would use recursion to track the copy.

    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);
    }

In the destructor I would have used a for(;;) loop. That way you can put all the control in one place. Since the constructor now can potentially relase also use the same function as the constructor.

    ~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;
        }
    }

By adding the constructor to mystack_node the push becomes much more readable.

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

Since you do not have control of the type T. You must assume that all calls to its methods are not exception safe. This includes the destructor. This means you need to write your code so that your object is fully mutated before calling an exception unsafe method.

    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.
        }
    }

Why not return a reference to the top node?

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

If you do this you probably need two versions. A const and a non cost version.

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

Rather than dereference the object then use the . operator. It may be best to just use the -> operator for readability.

        return (*stack_top).data;

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

One minor thing.

     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
\$\endgroup\$
  • \$\begingroup\$ Great answer!! I tried to compile my code after making the mentioned changes, but got a compiler warning regarding your release_stack() throw() function - warning: for increment expression has no effect [-Wunused-value] my attempt \$\endgroup\$ – Anmol Singh Jaggi Jul 26 '13 at 19:06
  • \$\begingroup\$ @AnmolSinghJaggi: Fixed a bug. Change loop != next to loop = next \$\endgroup\$ – Martin York Jul 26 '13 at 19:09
  • \$\begingroup\$ Also, in the pop() function, you have mentioned // Thus if the destructor throws it will not harm your object . I do not understand under what circumstances would a destructor throw an exception?? ( I don't have a good understanding of exception-handling ) \$\endgroup\$ – Anmol Singh Jaggi Jul 26 '13 at 19:18
  • \$\begingroup\$ You are not supposed to throw from a destructor but you can. You do not know how T is implemented or even who is implementing T. So you must assume that they are idiots. If the destructor of T throws an exception (when you call delete oldTop;) then it should not affect your class. \$\endgroup\$ – Martin York Jul 26 '13 at 20:56
7
\$\begingroup\$

The recommended swap function implementation is as a friend named 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);
}

And the assignment operator is:

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

    swap(*this, other);
    return *this;
}
\$\endgroup\$
  • \$\begingroup\$ I'd like to emphasize that ::swap(mystack&, mystack&) is still an external function and not a member function, even though it is defined within the class definition. \$\endgroup\$ – Lstor Jul 26 '13 at 3:15
  • \$\begingroup\$ @William Thanks for reviewing my code. But could you please explain what difference does it make whether i make swap() a friend or a private function?? \$\endgroup\$ – Anmol Singh Jaggi Jul 26 '13 at 3:44
  • \$\begingroup\$ @Lstor I am unable to fathom why swap isn't a member function. Would you care to explain in a little more depth?? \$\endgroup\$ – Anmol Singh Jaggi Jul 26 '13 at 3:58
  • \$\begingroup\$ Section 11.3.6 of the C++11 standard states: A function can be defined in a friend declaration of a class [iff] the class is a non-local class, the function name is unqualified, and the function has namespace scope. The easiest way to tell is because it has friend in front. See this demonstration (remove line #14 to get it to compile). \$\endgroup\$ – Lstor Jul 26 '13 at 4:26
  • 1
    \$\begingroup\$ See stackoverflow.com/questions/5695548/… \$\endgroup\$ – William Morris Jul 26 '13 at 11:51
5
\$\begingroup\$
  1. You may run a high risk of memory leaks when using raw structures, especially with pointers. Memory-management is not one of my strong points, so I won't say too much about that. For learning purposes, you should be okay as long you maintain good habits (accompany each new with delete, etc).

  2. Memory-management still plays a big role here, considering your stack is dynamic (as it lacks a full() and uses nodes). Again, watch your memory and pointer usage.

  3. Based on this, I think you're using it correctly.

  4. With a linked list type structure, that may be as good as you can get it. For a dynamically-allocated array, on the other hand, you would just loop through it. Overall, you won't attain superb data output unless you use iterators. This is okay for a basic implementation, though.


  • Do not use using namespace std.

  • The class declarations and implementations should be noticeably separate, even if they're in one file. I had to scrounge for that }; to see where your declarations ended. Generally, you may still keep your accessors and mutators within the declarations as they'll automatically become inline.

  • The node struct should be kept private within your class since it's a data member and shouldn't be exposed.

  • If you're using C++11, use nullptr instead of NULL.

  • You're not technically putting anything into your output stream. Yours is called out, but you're still using std::cout.

  • Your accessors (size(), empty(), and top()) should be declared with const since they just return data members:

    unsigned int size() const
    
  • size() should return a std::size_t. This is located in <cstddef>.

  • If you're keeping careful track of stack_size, pop() could just check if the stack size is zero (using empty()).

Follow-up on comments:

  1. full() was just my name for a common bool function for determining if a static structure has reached its maximum size. With a dynamic structure like yours, this is not needed.

  2. Consider this piece of code:

    for (auto iter = container.cbegin(); iter != container.cend(); ++iter)
    {
        std::cout << *iter;
    }
    

    This is one of a few C++11 ways of iterating through an STL storage container (such as std::vector). Here, let structure be a name of such container and iter an iterator of this container (defined within the implementation). These containers are designed in such a way that, if utilized correctly, you will avoid runtime errors with them. In this case, using iterators instead of indices ensures that you'll not go out-of-bounds when accessing the container.

  3. You simply need to move it to the private section of the class. In order for operator<< to recognize your data members, declare it a friend and put it inside the class. This particular operator doesn't belong to any one class, so you also cannot declare it as part of your own class with the :: operator (in case you were curious). There's plenty of info on all these operators, so read up!

  4. In and of itself, I don't think so. The reason I've mentioned dynamically-allocated arrays is because stack elements aren't accessed the same way as linked lists. The former deals with popping data from the top, whereas the former can have any node removed anywhere within the structure. However, you're not wrong about using a linked list; it's still another way to implement a stack.

  5. Not a huge difference, but I think it's a bit more readable with empty(). With linked lists, NULL is necessary for determining if the list head is pointing to a node (not empty) or the NULL address (empty). Overall, I'd say it's up to you. Again, you should make sure that your element count is maintained, otherwise you'll have problems.

\$\endgroup\$
  • \$\begingroup\$ op= taking a parameter by value and then swapping it is the copy-and-swap idiom he is talking about. It should be like he wrote. \$\endgroup\$ – Lstor Jul 26 '13 at 1:45
  • \$\begingroup\$ @Lstor: Oh, right. Forgot about that. I'm still working on my answer. \$\endgroup\$ – Jamal Jul 26 '13 at 1:46
  • \$\begingroup\$ @Jamal Thanks for taking the time to review my code!!.. Your answer was very helpful.However,I am not able to understand few things in it -: 1). What is this full you are talking about?? 2). How can iterators be used to improve the output process?? 3). Could you please show me a demo on how to make mystack_node as a private struct of mystack?? [ I tried to shift the structure inside the class (as a normal struct and not as a template ), but then the output operator wasn't able to see mystack_node *temp!! ( and i don't know how to fix it )] \$\endgroup\$ – Anmol Singh Jaggi Jul 26 '13 at 3:32
  • \$\begingroup\$ @AnmolSinghJaggi: I'll follow-up on this right now. \$\endgroup\$ – Jamal Jul 26 '13 at 3:39
  • 3
    \$\begingroup\$ @AnmolSinghJaggi std::stack is by default implemented on top of a std::deque, which uses an array. (C++11 standard section 23.3.3.1.1: A deque is a sequence container that, like a vector , supports random access iterators.) Using an array gives locality of reference, random access (accessing index n is O(1) instead of O(n)), and so on. \$\endgroup\$ – Lstor Jul 26 '13 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.