6
\$\begingroup\$

Please review my simple Stack:

template<class T>
class Stack {
public:
    Stack() = default;
    Stack(std::initializer_list<T> i) :n{} {
        for (auto& x : i) {
            elem.push_back(x);
            ++n;
        }
    }
    Stack(const Stack<T>&) = default;
    Stack(Stack<T>&&) = default;
    Stack& operator=(const Stack&) = default;
    Stack& operator=(Stack&&) = default;
    ~Stack() = default;
    int size() const {
        return n;
    }
    bool isEmpty() const {
        return (n == 0);
    }
    void push(T);
    T pop();
    T& peek();

private:
    std::vector<T> elem;
    int n;
};

template<class T>
void Stack<T>::push(T t) {
    elem.push_back(t);
    ++n;
}

template<class T>
T Stack<T>::pop() {
    if (isEmpty()) {
        throw std::out_of_range("underflow");
    }
    T t = *elem.erase(elem.end()-1);
    --n;
    return t;
}

template<class T>
T& Stack<T>::peek() {
    if (isEmpty()) {
        throw std::out_of_range("underflow");
    }
    return elem[n-1];
}

How can I make this code better and build more complicated data structures based on stacks?

\$\endgroup\$
  • \$\begingroup\$ My first question is why do you need this at all? Why not just use std::stack? \$\endgroup\$ – John Dibling Nov 10 '14 at 17:43
  • \$\begingroup\$ @John Dibling because I want to practice creating my own stack. I believe I can understand data structures more if I write one. \$\endgroup\$ – morbidCode Nov 10 '14 at 17:56
4
\$\begingroup\$

Remove int n;from member variable. Underlying container std::vector holds the size information of the stack class. It increases the size of stack class object by sizeof(int).

Remove various default definition methods from your class. Compiler would generate it for such classes. Due to these definition your class looks more verbose.

Implement all your member functions using the underlying container classes.

Prefer the standard name of your method instead of other. This way any program would easily use your custom class instead of std::stack. Change the isEmpty() to empty()

Your implementation can be simplified as below.

template<class T>
class Stack {
public:
    Stack(const std::initializer_list<T>& i):elem(i) {}
    int size() const { return elem.size(); }
    bool empty() const { return elem.empty();}
    void push(const T&);
    T pop();
    T peek();
private:
    std::vector<T> elem;
};


template<class T>
void Stack<T>::push(const T& t) {
    elem.push_back(t);
}

template<class T>
T Stack<T>::pop() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    auto x = elem.back();  
    elem.pop_back();
    return x;
}

template<class T>
T Stack<T>::peek() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    return elem.back();
}
\$\endgroup\$
  • 2
    \$\begingroup\$ How about Stack(const std::initializer_list<T> &i) : elem(i){}? \$\endgroup\$ – nwp Nov 8 '14 at 11:17
  • \$\begingroup\$ @nwp: Yes you are right. I have added this suggestion. \$\endgroup\$ – Mantosh Kumar Nov 8 '14 at 11:24
  • 1
    \$\begingroup\$ Your pop looks bad to me, the order of last two statements is wrong (use auto tmp = elems.back(); elems.pop_back(); return tmp;) \$\endgroup\$ – firda Nov 8 '14 at 11:28
  • \$\begingroup\$ Just now I realized that, author wants to return the value which is going to erased. Hence we need to save it before calling the pop_back. \$\endgroup\$ – Mantosh Kumar Nov 8 '14 at 11:30
3
\$\begingroup\$

There's a reason std::stack doesn't provide a pop() that returns the popped element: exception safety. Returning the popped element by value from pop() may require calling the copy constructor (although the compiler may be able to elide the copy) which in general may throw. If it throws you will lose the popped element and therefore your stack's pop() doesn't meet the Strong Exception Safety Guarantee.

This may not matter for your use case but I think it's worth understanding why the standard library version of a stack doesn't provide a pop that returns the popped element but has a separate top() and void-returning pop().

\$\endgroup\$

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.