9 Replies - 514 Views - Last Post: 27 May 2012 - 05:17 AM Rate Topic: -----

#1 kojima100  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 66
  • Joined: 10-November 10

Custom Stack error

Posted 26 May 2012 - 10:04 AM

Hi, I'm trying to write an implementation of a stack in C++.
Everything appears to work fine when i try it normally, but when i run the program through valgrind to check for any memory leaks, everytime the function Resize is called from inside Push the data pops out as a 0. This doesn't happen when i run it straight off the command line.
Is it something stupid I'm doing, or is it just a problem with valgrind?

Here's the code:


#include <cstdlib>

#include <iostream>

template<typename T>
class Stack
{

    private:
    
        T* m_Array;
        T* m_TopBounds;
        T* m_Top;
        T* m_Bottom;
        
        size_t m_Size;
        size_t m_NumOfElements;
    
    public:
    
        explicit Stack(size_t StackSize = 10)  : m_Size(StackSize), m_NumOfElements(0)
        {

            m_Array = (T*)malloc(m_Size * sizeof(T));  
            
            if(m_Array == nullptr)
            {
    
                throw "Not enough memory";
    
            }
     
            m_Bottom = m_Top = m_Array - 1;
            m_TopBounds = m_Array + m_Size;
    
        }
        
        ~Stack()
        {
            
            while(m_Top != m_Bottom)
            {
            
                (m_Top--)->~T();
                
            }
            
            free((void*)m_Array);

        }
        
        size_t Size() const
        {
        
            return m_Size;
        }
        
        T Pop()
        {

            if(m_Top != m_Bottom)
            {
    
                --m_NumOfElements;
                
                T t = *m_Top;
               
                (m_Top--)->~T();
                
                return t;
            }
            else
            {
    
                throw "Can't pop off empty stack";
    
            }
        }

        
        void Push(const T& t)
        {

            if(m_Top == m_TopBounds)
            {
                
                size_t FirstRequest, BackUpRequest;
                
                if((m_Size << 1) > (m_Size + 20))
                {
                
                    FirstRequest = m_Size << 1;
                    BackUpRequest = m_Size + 20;
                
                }
                else
                {
                
                    FirstRequest = m_Size + 20;
                    BackUpRequest = m_Size << 1;
                
                }
                
              
    
                if (!Resize(FirstRequest))
                {
                
                    if((FirstRequest == BackUpRequest) || (!Resize(BackUpRequest)))
                    {
                    
                        if(!Resize(m_Size + 1))
                        {
                        
                            throw "Not enough memory";
                            
                        }
                    }
                } 
                
                
                
            }    
    
            ++m_NumOfElements;
    
            *(++m_Top) = t;
            
        }

        
        bool Resize(size_t NewStackSize)
        {
            
            //realloc will never return NULL if the it's resiszing down (I think)
            for( ; NewStackSize < m_NumOfElements; --m_NumOfElements)
            {
            
                (m_Top--)->~T();
    
            }
            
            T* NewArray = (T*)realloc((void*)m_Array, NewStackSize * sizeof(T));
            
            if(NewArray == nullptr)
            {
    
               return false;
    
            }
            
            m_Size = NewStackSize;
            m_Array = NewArray;
            m_Bottom = m_Array - 1;
            m_Top = m_Bottom + m_NumOfElements;
            m_TopBounds = m_Array + m_Size;

            return true;
       }

};

using namespace std;
int main()
{

    Stack<int> s;

    for(int i = 1; i <= 60000; ++i)
    {
    
        s.Push(i);
        cout << i << "\n";
    
    }

    for(int i = 1; i <= 60000; ++i)
    {
    
        cout << s.Pop() << "\n";
    
    }

    return 0;
}




Thanks in advance.

This post has been edited by kojima100: 26 May 2012 - 10:09 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Custom Stack error

#2 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1621
  • View blog
  • Posts: 3,079
  • Joined: 30-May 10

Re: Custom Stack error

Posted 26 May 2012 - 10:55 AM

Well first, you MUST use new/delete for memory allocation if you ever hope to use your template class for non POD data (ie, any class with constructors).

Second, look at your resize function.
You need to decide which end of the array is the "top" and which direction the stack grows in. What you do in resize seems to be completely at odds with what the initial stack constructor does.
Was This Post Helpful? 1
  • +
  • -

#3 kojima100  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 66
  • Joined: 10-November 10

Re: Custom Stack error

Posted 26 May 2012 - 11:13 AM

I'm not entirely sure I understan your second point.m_Bottom is one before the array, and m_Top is m_Bottom + the number of elements in the array (which would be 0 in the constructor) so the Top would be equal to the bottom untill something is added where it's incremented. so it grows ++ from the bottom.

As to your first point since it's a container wouldn't it be provided with already initialised data snce it's a container, so calling new and then overwriting it immediately would be pointless surely?

Sorry if i've missed the point completly i'm pretty new to C++.
Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5766
  • View blog
  • Posts: 12,580
  • Joined: 16-October 07

Re: Custom Stack error

Posted 26 May 2012 - 12:21 PM

First, as noted, malloc?!? No. Do NOT use malloc. Period.

I don't understand why you have so many variables. I don't understand why you define a size and then break it. Pick a paradigm; it grows or it doesn't. If it's array based, it would normally be a fixed size. If it needs to grow, then just use a simple linked list.

So, you essentially have this:
template<typename T>
class Stack {
public:
	Stack(size_t StackSize = 10);
	~Stack();
	size_t Size() const;
	T Pop();
	void Push(const T &);
private:
	// Why the hell would you do this?
	bool Resize(size_t);
};



Let's assume you really, really want to use an array and then go through the mess of reallocating it. You'd only need:
T *data;
size_t capacity, size;


Was This Post Helpful? 0
  • +
  • -

#5 kojima100  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 66
  • Joined: 10-November 10

Re: Custom Stack error

Posted 26 May 2012 - 12:27 PM

I have a size so that i know how much space is currently allocated. If i kneed more i just call Resize.
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5766
  • View blog
  • Posts: 12,580
  • Joined: 16-October 07

Re: Custom Stack error

Posted 27 May 2012 - 02:20 AM

In which case, using an array as the underlying structure is a questionable choice.

That doesn't really explain all the extra variables...

This post has been edited by baavgai: 27 May 2012 - 02:20 AM

Was This Post Helpful? 0
  • +
  • -

#7 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2087
  • Posts: 3,174
  • Joined: 21-June 11

Re: Custom Stack error

Posted 27 May 2012 - 02:36 AM

View Postbaavgai, on 27 May 2012 - 11:20 AM, said:

In which case, using an array as the underlying structure is a questionable choice.


Is it? std::vector is implemented using arrays that are resized when necessary as well, no?

So if the intent is to duplicate (some of) std::vector's functionality (for learning purposes, I'd assume), I don't see what's wrong with doing it this way.

Note that resizable arrays are a perfectly okay choice to use as stacks. They'll usually perform faster than linked lists for this use case.
Was This Post Helpful? 1
  • +
  • -

#8 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2087
  • Posts: 3,174
  • Joined: 21-June 11

Re: Custom Stack error

Posted 27 May 2012 - 04:12 AM

View Postkojima100, on 26 May 2012 - 08:13 PM, said:

As to your first point since it's a container wouldn't it be provided with already initialised data snce it's a container, so calling new and then overwriting it immediately would be pointless surely?


When you do *(++m_Top) = t; in your Push function, you're calling operator= on the object that m_Top points to. However that object has not been initialized yet, since you get the memory from malloc, not new. Calling operator= (or anything else) on an uninitialized object is undefined behavior.

If you want to avoid the overhead of calling the default constructor followed by operator= (or the requirement that a default constructor and operator= must exist), you can use placement new to call the copy constructor directly. This way you also don't require the existence of a default constructor or operator= (but you do require the existence of a copy constructor).

That'd definitely be advanced usage though and you probably should avoid that.
Was This Post Helpful? 1
  • +
  • -

#9 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5766
  • View blog
  • Posts: 12,580
  • Joined: 16-October 07

Re: Custom Stack error

Posted 27 May 2012 - 05:03 AM

It a "stack", not a vector. Random access of elements within the contents are not a requirement. The requirement is simply knowing where the top of the stack is. Performance of arrays versus linked list is a seek issue, which isn't in play here.

Could you make a dyamic stack by constantly reallocating an array? Sure. Is it easier to implement than a linked list? No, it's more work. Can you do it in C++ with realloc? No.
Was This Post Helpful? 0
  • +
  • -

#10 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2087
  • Posts: 3,174
  • Joined: 21-June 11

Re: Custom Stack error

Posted 27 May 2012 - 05:17 AM

View Postbaavgai, on 27 May 2012 - 02:03 PM, said:

It a "stack", not a vector. Random access of elements within the contents are not a requirement. The requirement is simply knowing where the top of the stack is.


I know.

Quote

Performance of arrays versus linked list is a seek issue, which isn't in play here.


No, it's not just a random access issue. It's also a locality and a memory allocation issue. With an array all elements are close to each other in memory, so you get much better caching behavior than with a linked list. A linked list also needs to allocate a new node on the heap each time you push an element.

A resizable array performs faster than a linked list when only using stack operations - no random access required. If you don't believe me, try comparing the performance of std::stack<T, std::list<T>> with that of std::stack<T, std::vector<T>>.
Was This Post Helpful? 2
  • +
  • -

Page 1 of 1