Input asked for better programming practices

Question

As I'm learning C++ I started implementing some common datastructures as a form of practice. The first one being a Stack (this was the first to spring in mind). I've done some programming and it's working, but now I need some input as to what I should do otherwise. Like deleting certain stuff or other pro tips. What should I do different and why?

template <class T>
class Stack
{
private:
    int* values;
    int capacity;
    int itemsOnStack;

public:

    /////////////////// 
    Stack()
    {
        Stack(32);
    }

    /////////////////// 
    Stack(const int sz)
    {
        values = new T[sz];
        capacity = sz;
        itemsOnStack = 0;
    }

    ~Stack()
    {
        values = 0;
               // delete?
    }

    ////////////////////
    void Push(const T& item)
    {   
        *(values + itemsOnStack) = item;

        itemsOnStack++;

        if(itemsOnStack > capacity)
        {
            capacity *= 2;

            T* temp = new T[capacity];
            temp = values;
            values = new T[capacity]; 
            values = temp;          
        }
    }

    /////////////////// 
    T Pop()
    {
        if(itemsOnStack > 0)
        {
            int current = --itemsOnStack;
            return *(values + current);
        }
        return NULL; // ? good?
    }

    /////////////////// 
    T Peek()
    {
        if(itemsOnStack > 0)
        {
            int current = itemsOnStack - 1;
            return *(values + current);
        }
        return NULL; // find something better here or shouldnt?
    }

    /////////////////// 
    int Count()
    {
        return itemsOnStack;
    }

    /////////////////// 
    int Capacity()
    {
        return capacity;
    }

    /////////////////// 
    bool IsEmpty()
    {
        return itemsOnStack == 0;
    }
};

Answer 1

You should probably delete values in the destructor instead of just setting it to 0;

in your push method, you cannot resize an array like that.

more info on resizing arrays: http://www.daniweb.com/forums/thread13709.html#

Answer 2

To name a few along with what John noted:

1.) Use initialization lists
2.) Use const member functions where applicable.
3.) Use function names more closely aligned with the standard. (empty() instead of IsEmpty())
4.) You have huge memory leaks. Destroy memory in your destructor

Answer 3

Push(): You should check the size of the array before writing to it

Answer 4

Did a first pass of fixes on your code:

template <class T>
class Stack
{
private:
    int* values;
    int capacity;
    int itemsOnStack;

public:

    //Stack() : 
    //{
    //   Stack(32); // doesn't do what you expect. This would create an unnamed temporary stack object
    //}

    Stack(const int sz = 32) // C++ doesn't yet have delegating constructors. You can't call one ctor from another. But in this case, a simple default parameter can be used instead
   : values(new T[sz]), capacity(sz), itemsOnStack() {} // use the initializer list for initializing members

    ~Stack()
    {
        delete[] values; // you allocated it, so you delete it as well
    }

    ////////////////////
    void Push(const T& item)
    {   
        values[itemsOnStack] = item; // cleaner syntactically than your version
     //   *(values + itemsOnStack) = item;

        ++itemsOnStack; // prefer pre-increment by default.

        if(itemsOnStack > capacity) // you need to check this before writing the element. Move this to the top of the function
        {
            int newCapacity = capacity * 2;

            // what's this supposed to do? You're just copying pointers around, not the contents of the array
            T* temp = new T[newCapacity ];
            std::copy(values, values+capacity, temp); // copy the contents from the old array to the new one
            delete[] values; // delete the old array
            values = temp; // store a pointer to the new array
            capacity = newCapacity;
        }
    }

    /////////////////// 
    T Pop()
    {
        T result = Peek(); // you've already got a peek function. Why not use that?
        --itemsOnStack;
        return result;
    }

    /////////////////// 
    T Peek()
    {
        if(itemsOnStack > 0)
        {
            int current = itemsOnStack - 1;
            return values[current]; // again, array syntax is clearer than pointer arithmetics in this case.
        }
//        return NULL; // Only pointers can be null. There is no universal "nil" value in C++. Throw an exception would be my suggestion
          throw StackEmptyException();
    }

    /////////////////// 
    int Count()
    {
        return itemsOnStack;
    }

    /////////////////// 
    int Capacity()
    {
        return capacity;
    }

    /////////////////// 
    bool IsEmpty()
    {
        return itemsOnStack == 0;
    }
};

Things left to fix:

Copy constructor and assignment operator. At the moment, if I try to do this, it'll break horribly:

Stack<int> s;
Stack<int> t = s; // no copy constructor defined, so it'll just copy the pointer. Then both stacks will share the same internal array, and both will try to delete it when they're destroyed.
Stack<int> u;
u = s; // no assignment operator, so much like above, it'll blow up

Const correctness:
Shouldn't I be able to call Peek() or Count() on a const Stack<T>?

Object lifetime:
Popping an element off the stack doesn't call the element's destructor. Pushing an element doesn't call the element's constructor. Simply expanding the array calls the default constructor immediately for all new elements. The constructor should be called when the user inserts an element and not befre, and the destructor immediately when an element is removed.

And, uh, proper testing:
I haven't compiled, run, tested or debugged this in any way. So I've most likely missed some bugs, and introduced a few new ones. ;)

Answer 5

You have lots of memory leaks, particularly if you copy, assign or push to your Stack object. Even as a learning exercise I would suggest steering clear of doing your own memory management (it is something that you do need to learn in C++, but take one step at a time). Instead, use std::vector or std::list rather than your raw C-style array of values. This will mean that the destructor, copy constructor, assignment operator and Push() method won't leak memory -- they'll also do the right thing by default (I call this the Principle of Least Surprise). I think one of the most important parts of C++ learning is knowing how to use the STL. Understand that first and worry about pointers and new[] and delete[] later.

I would suggest reading up on copy constructors, assignment operators and destructors so you know how values are actually copied around and deleted. Try writing a class:

class Noisy {
  public:
    Noisy() { std::cout << "Constructor" << std::endl; }
    ~Noisy() { std::cout << "Destructor" << std::endl; }
    Noisy& operator=(const Noisy& other) {std::cout << "Assign" << std::endl; }
    Noisy(const Noisy& other) {std::cout << "Copy constructor" << std::endl; }
};

and then do a few operations on Stack<Noisy>:

Stack<Noisy> stack(10);
stack.Push(Noisy());
Stack<Noisy> otherStack(stack);
Stack<Noisy> thirdStack;
thirdStack=stack;

and see if your expectations of what you think it should be doing match up with what you see in the console window.

Answer 6

you need to adopt a naming convention four you member variables. We use

 int *m_values;
 int m_capactity;

etc.

And why do you do

 *(values + itemsOnStack) = item;

I assume you mean

 values[itemsOnStack] = item;

they do exactly the same thing but the first is much more natural