Stack implementation using arrays

Question

Please comment on the same. How can it be improved?

Specific improvements I am looking for:

1. Memory leaks
2. C++ style
3. Making code run faster
4. RAII

#include<iostream>
#include<algorithm>

template <typename T>
class Stack {
private:
    T* array_;
    int length_;
    T* last_;
    void expandArray();

public:
    Stack(int length = 8) :
        array_(new T[length]),
        length_(length),
        last_(array_)
    {}

    Stack<T>& push(const T&);
    Stack<T>& pop();
};

template<typename T>
void Stack<T>::expandArray() {
    T* array_temp = new T[length_ << 1];
    std::copy(array_, array_ + length_, array_temp);
    std::swap(array_, array_temp);
    delete[] array_temp;
    last_ = array_ + length_ - 1;
    length_ <<= 1;
}

template<typename T>
Stack<T>& Stack<T>::push(const T& data) {
    if (last_ == (array_ + length_ - 1)) {
        expandArray();
    }
    last_[0] = data;
    last_++;
    std::cout << "[" << data << "] pushed." << std::endl;
    return *this;
}

template<typename T>
Stack<T>& Stack<T>::pop() {
    if(array_ != last_) {
        last_--;
        std::cout << "[" << last_[0] << "] popped." << std::endl;
    } else {
        std::cout << "Nothing to pop." << std::endl;
    }
    return *this;
}

int main() {
    Stack<std::string> s;
    s.push(std::string("a"))
     .push(std::string("b"))
     .push(std::string("c"))
     .push(std::string("d"));
    s.pop().pop().pop().pop().pop();
}

Answer 1

First of all, I would specify that your stack is using a "dynamically allocated array", as opposed to just an array, as I at first expected a C array when looking at the title. That varies from person to person, though.

On to more important things:

• I would not print anything in the stack functions. If someone wants information on what they're pushing and popping, let them do it themselves.
• You seem to be missing a peek function.
• Either throw an exception or add an assert to pop for the array_ == last_ case.
• length_ should actually be called capacity_.
• expandArray may leak memory if the copy throws. I would use an std::vector<T*> internally for this stuff.
• You don't check that length > 0 in the constructor.
• I would not allocate so anything by default.
• You lack all three of a copy constructor, assignment operator, and destructor, so you'll definitely leak memory. You should also have a move constructor and a move assignment operator, but those aren't as critical.
• You provide no way to check whether the stack is empty.

Answer 2

Memory leaks

Yes. No destructor

C++ style

Where? This is C code. Just uses a few things from C++. But basically this is C in style and usage.

Making code run faster

It will run infinitely faster when correct. Currently it is broken.

{
    Stack<int>  x;
    Stack<int>  y(x);
} // breaks here with a double delete.

RAII

Would be nice. But no destructor. Also you are not implementing the rule of three(five). To help you should probably look up the copy/swap idiom (assuming it is assignable in the first place).

Code Review:

When you create this array:

T* array_temp = new T[length_ << 1];

You are creating (length * 2) members (that will be fully constructed). I suppose this is OK. But if T is expensive to construct then this may not be something you want to pay for. As an example std::vector<> does not initialize the elements between size() and capacity().

The rest is good you create it in a temporary and then swap with the current. But you start deleting the old stuff before finishing the update on this object. If the destructor of T throws an exception your object is now in an intermediate state.

The order is:

1. Create an new stuff that can throw (int temps)
2. Change the state of the current object (using no-throw actions).
3. Destroy the old stuff.

This way if destroying the old stuff causes problems you don't leave your object in an intermediate state. You should probably look up copy and swap idiom. It will help with this.

Answer 3

I would use std::aligned_storage for the backing store and then use placement new and placement delete to manage elements. Currently you are default constructing elements above the capacity and are also not destroying objects when they are popped. You may also want to consider changing the interface to use move semantics to push and pop items (if using my first suggestion this just means offering an emplace_push(T&&) inteface and using placement new with move constructor, conversely offer a T pop() function that move constructs the head to the result (using NRVO) and then placement deletes the head). Also when you reallocate the backing store you should use move semantics. The advantage of doing it this way (apart from performance) is that T does not need to be default constructible, copy constructible or assignable.