Stack implementation with shared_ptr C++11

Question

stack.hpp

#ifndef _TOP_HPP
#define _TOP_HPP

#include<memory>
#include<iostream>
#include<cstring>


    template <typename T>
    class Stack{
        private:
            struct Node{
                std::shared_ptr<Node> prev;
                T value;
            };

            int size;
            std::shared_ptr<Node> top;
            const char* name;

        public:
            Stack();
            Stack(const char* name);
            bool isEmpty()const;
            void push(T);
            const int pop();
            const int getSize()const{return size;}
            const char& getName()const{return name;}
            void clear();

            Stack<T>& operator=(const Stack<T>&);
            //don't know why but when implement this friend fun beyond 
            //class then main.cpp don't compile 
            friend std::ostream&  operator<<(std::ostream& os,const Stack<T>& s){
                if(strcmp(s.name,"null")) os<<"Name: "<<s.name<<"  Size "<<s.size<<std::endl;
                auto temp=s.top.get();
                while(temp){
                    os<<temp->value<<std::endl;
                    temp=temp->prev.get();
                }
                return os<<std::endl;
            }


    };


    template <typename T>
    inline Stack<T>::Stack():size(0),top(std::make_shared<Node>()),name("null"){ 
        top->prev=nullptr; 
        top->value=0; 
    }

    template <typename T>
    inline Stack<T>::Stack(const char* name):size(0),top(std::make_shared<Node>()),name(name){
        top->prev=nullptr; 
        top->value=0; 
    }

    template <typename T>
    inline bool Stack<T>::isEmpty()const{
        if(size==0) return true;
        return false;
    }

    template <typename T>
    void Stack<T>::push(T x){
        std::shared_ptr<Node> add =std::make_shared<Node>();
        add->value=x;
        add->prev=nullptr;
        if(isEmpty()) top=std::move(add);
        else{
            add->prev=std::move(top);
            top=std::move(add);
        }
        ++size;
    }

    template <typename T>
    const int Stack<T>::pop(){
        int p=top->value;
        if(isEmpty()){ std::cerr<<"stack is empty"<<std::endl; }
        else{
            top=top->prev; //this is good idea ?
            --size;
        }
            return p;
    }


     template <typename T>
     Stack<T>& Stack<T>::operator=(const Stack<T>& s){
         if(this!=&s){
             size=s.size;
             top=s.top;
         }
         return *this;
     }

    template <typename T>
    inline void Stack<T>::clear(){
        while(top){
            top=std::move(top->prev);i//how can i improve this ? 
            --size;
        }
    }


#endif

main.cpp

#include<iostream>
#include<memory>
#include "stack.hpp"


using namespace std;


int main(){

    Stack<int> s("asd");
    Stack<int> q;
    s.push(12);
    s.push(13);
    s.push(14);
    s.push(15);

    q=s;

    cout<<s; //cout's normal display a stacks 
    cout<<q; 
    s.clear(); // after this fun on s

    cout<<s; // this stack is delete
    cout<<q; // this stack have only 15 (top of stack s) ;/


}

Any particular reason for using shared_ptr instead of unique_ptr? — KIIV
– KIIV, Commented Jul 26, 2016 at 8:44
Not really. I use ptr first time and i am lerning about how they are work. I had unique but it has't default copy construcotr so i changed it to shared because i had huge desire to know how works a default copy construcor on shared but now i know it don't works good enough. ;) — Klemens
– Klemens, Commented Jul 26, 2016 at 9:08

buld0zzr · Accepted Answer · 2016-07-26 09:38:12Z

Use containers

Instead of char* name use std::string name, it's safer with the cost of very little overhead, and prevents basic errors like assigning a char string to a pointer, like you do in your constructors, for example:

template <typename T>
inline Stack<T>::Stack(const char* name) :size(0), top(std::make_shared<Node>()), name(name)

You assign a pointer to a pointer, without any control over the lifetime of memory for name, and you'd get undefined behavior when you try to use it.

Always use brackets

Instead of

if (isEmpty()) top = std::move(add);
else {
    add->prev = std::move(top);
    top = std::move(add);
}

You should write

if (isEmpty()) {
    top = std::move(add);
}
else {
    add->prev = std::move(top);
    top = std::move(add);
}

It makes the code more readable and would prevent mistakes that are too easy to miss. There're several places like this in the code.

Your copy constructor is bad

You're not doing a deep copy, but a shallow copy. q gets shared ownership of s stack, you should make a deep copy of it. For example, when you call clear on s, the internal stack gets destroyed, however, q is now in inconsistent state. Here's an example of your stack deep copy

template <typename T>
Stack<T>& Stack<T>::operator=(const Stack<T>& s) {
    if (this != &s) {
        //Creating a new stack
        top = std::make_shared<Node>();

        //Copying the top value
        top->value = s.top->value;
        std::shared_ptr<Node> s_stack = s.top;
        top->prev = std::make_shared<Node>();
        std::shared_ptr<Node> this_prev = top;

        //Copying next values
        while (s_stack->prev) {
            this_prev = this_prev->prev;
            s_stack = s_stack->prev;
            this_prev->value = s_stack->value;
            this_prev->prev = std::make_shared<Node>();
        }

        this_prev->prev = nullptr;
        size = s.size;
    }
    return *this;
}

Note that further improvements can be made if your Node class would be more intelligent and provide a constructor that would initialize the value, but set the prev pointer to nullptr.

Clear function is bad

After clear the expected behavior is that s is reset to the initial state, that is, top is a shared_ptr to Node object with value = 0, however, after clear method top is a shared_ptr to nullptr. This should be a better implementation that wouldn't mess with other shared owners of internal stack.

template <typename T>
inline void Stack<T>::clear() {
    top = std::make_shared<Node>();
    top->prev = nullptr;
    top->value = 0;
    size = 0;
}

However, it requires a correct implementation of copy constructor, since now q memory wouldn't be destroyed, that's what shared_ptr expresses.

PS. You could also gain more insight if you would add a destructor to Node which would output something when a corresponding Node object is destroyed, something like this, but for learning purposes only, it's not a production code in any way.

~Node() {
    std::cout << "destroyed\n";
}

Thanks a lot ! But i have a problem with deep copy on shared_ptr . How to do that ? — Klemens
– Klemens, Commented Jul 26, 2016 at 8:57
About clear() , stack q wouldn't be destroyed and s after s.clear() wouldn't print it content but pointers of s will be still in memory, right ? — Klemens
– Klemens, Commented Jul 26, 2016 at 9:20
Right, since the ownership is shared, these pointers belong to q too. I'm currently writing a deep copy example, which would solve this shared ownership problem, if you would wait a bit. — buld0zzr
– buld0zzr, Commented Jul 26, 2016 at 9:22

Stack Exchange Network

Stack implementation with shared_ptr C++11

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Stack implementation with shared_ptr C++11

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions