[PlasticineGuy]

I've been figuring out how to implement a stack and it's working well... except I can only push one value.

//stack.cpp
#include <cstdlib>
#include <iostream>
#include "saqdef.h"
namespace saq {
	TMPL
	class Stack {
		public:
			Stack(int size = 31000): sp(0), stack(new T[size]), sz(size) {}
			~Stack(void) { if(sp != 0) throw std::exception("Pushed values not popped."); }
			T push(T value);
			T pop(T& dest);
			T pop(void);
			int getsize(void);
			void addmem(const int mem);
			T* getstack(void);
		private:
			int sp, sz;
			T *stack;	
	};
	TMPL
	T saq::Stack<T>::push(T value) {
		stack[sp] = value;
		++sp;
		return value;
	}
	TMPL
	T saq::Stack<T>::pop(T& dest) {
		if(!sp || sp > MAX(sizeof(stack), 1) / sizeof(T)) {
			throw std::exception("Attempting to pop a value not pushed.");
		}
		dest = stack[sp - 1];
		--sp;
		return dest;
	}
	TMPL
	T saq::Stack<T>::pop(void) {
		if(!sp || sp > MAX(sizeof(stack), 1) / sizeof(T)) {
			throw std::exception("Attempting to pop a value not pushed.");
		}
		T ret;
		ret = stack[sp - 1];
		--sp;
		return ret;
	}
	TMPL
	void saq::Stack<T>::addmem(const int mem) {
		T *temp;
		temp = new T[sz + mem];
		memcpy(&temp, &stack, sizeof(stack));
		delete[] stack;
		stack = new T[sz + mem];
		memcpy(&stack, &temp, sizeof(temp));
		sz += mem;
		delete[] temp;
	}
	TMPL
	int saq::Stack<T>::getsize(void) {
		return sz;
	}
	TMPL
	T* saq::Stack<T>::getstack(void) {
		return stack;
	}
}
int main() {
	saq::Stack<int> myStack(2);
	myStack.push(20);
	myStack.push(30);
	std::cout << myStack.pop() << std::endl;
	std::cin.get();
	myStack.pop();
}

//saqdef.h
#pragma once
#define TMPL template <class T>
#ifndef MAX
#define MAX(a, b) ((a>b)?a:b)
#endif

I've checked with the debugger, and at a breakpoint on myStack.push(30)'s ++sp, stack[sp] = 30, but stack[sp] does not actually have an entry "30". It only has 20. What's going on?

I do end up with an unhandled exception:

Unhandled exception at 0x75629617 in stack_and_queue.exe: Microsoft C++ exception: std::exception at memory location 0x001bf598..

It points to:

00A917C4  call        @ILT+385(__RTC_CheckEsp) (0A91186h) 
00A917C9  push        offset [email protected]@@ (0A97D90h) 
00A917CE  lea         ecx,[ebp-100h] 
00A917D4  push        ecx  
00A917D5  call        @ILT+290([email protected]) (0A91127h) 
		}
		T ret;
		ret = stack[sp - 1];
00A917DA  mov         eax,dword ptr [this] <--this is the next statement

EDIT: I know about the memory leak in pop().

This post has been edited by PlasticineGuy: 11 February 2010 - 02:58 AM

[Bench]

What is this supposed to be doing?

sp > MAX(sizeof(stack), 1) / sizeof(T) 

sizeof T* and sizeof T are both compile-time constants

did you mean to use

(sp > sz) 

instead?



Also, i suspect that this will cause you problems too - again, sizeof T* is a compile time constant

memcpy(&temp, &stack, sizeof(stack)); 

I'd strongly suggest using the STL copy algorithm instead of memcpy. memcpy can introduce subtle bugs into your program when you try to build a stack of objects whose copy constructors are nontrivial (or whose copy constructors are deliberately hidden to prevent copying). Its generally a very bad idea to use memcpy for anything except POD types, so for a template class you should avoid it like the plague.

#include <algorithm>

// etc.
   std::copy( stack, stack + sz, temp ); 

This post has been edited by Bench: 11 February 2010 - 04:45 AM

[PlasticineGuy]

I didn't know about std::copy. Thank you.

MAX(sizeof(stack), 1) / sizeof(T) 

Is supposed to be finding the number of elements in the array... so I did mean sz.

EDIT: I really have no bloody idea why it isn't setting the value stack[sz] for sz > 0. Or, it is, but it isn't accessible outside of saq::Stack<T>::push(const T value).

This post has been edited by PlasticineGuy: 11 February 2010 - 10:05 PM

[Martyn.Rae]

I may be late in coming in on this one, but the two elements are set correctly on the stack.

[PlasticineGuy]

I'm sorry?
According to the debugger, this is no such thing as stack[1].
EDIT: Nope, sorry, I'm wrong; there is. ret gets set correctly in int pop(void).

The address &stack[sp] is equal to stack+4; is this correct? It points to 300, which is correct.
I get an assert failure at delete &stack[sp]:
_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
What's going on? Is it even possible to delete a certain element of a dynamically allocated array? If not, will setting that element to 0 leak the memory? Here is my code so far:

#include <algorithm>
#include <iostream>
#include "saqdef.h"
namespace saq {
	TMPL
	class Stack {
		public:
			Stack(int size = 100): sp(0), stack(new T[size]), sz(size) {}
			~Stack(void) { if(sp != 0) throw std::exception("Pushed values not popped."); }
			T push(T value);
			T pop(T& dest);
			T pop(void);
			int getsize(void) const;
			//void addmem(const int mem);
			T* getstack(void) const;
		private:
			int sp, sz;
			T *stack;	
	};
	TMPL
	T saq::Stack<T>::push(T value) {
		stack[sp] = value;
		++sp;
		return value;
	}
	TMPL
	T saq::Stack<T>::pop(T& dest) {
		if(!sp || sp > sz) {
			throw std::exception("Attempting to pop a value not pushed.");
		}
		--sp;
		dest = stack[sp];
		return dest;
	}
	TMPL
	T saq::Stack<T>::pop(void) {
		if(!sp || sp > sz) {
			throw std::exception("Attempting to pop a value not pushed.");
		}
		T ret;
		--sp;
		ret = stack[sp];
		delete &stack[sp];
		return ret;
	}
	/*TMPL
	void saq::Stack<T>::addmem(const int mem) {
		T *temp;
		temp = new T[sz + mem];
		std::copy(stack, stack + sz, temp);
		delete[] stack;
		stack = new T[sz + mem];
		std::copy(temp, temp + sz + mem, stack);
		sz += mem;
		delete[] temp;
	}*/
	TMPL
	int saq::Stack<T>::getsize(void) const {
		return sz;
	}
	TMPL
	T* saq::Stack<T>::getstack(void) const {
		return stack;
	}
}
int main() {
	saq::Stack<int> myStack(2);
	myStack.push(20);
	myStack.push(300);
	std::cout << myStack.pop() << std::endl;
	std::cin.get();
	myStack.pop();
}

As a note, while the addmem() function works, I commented it out because VC++ throws a couple of warnings about std::copy:

1>c:\users\helen\documents\visual studio 2008\projects\stack_and_queue\stack_and_queue\stack.cpp(50) : warning C4996: 'std::copy':
Function call with parameters that may be unsafe - this call relies on the caller to check that the passed values are correct. To disable this warning, use -D_SCL_SECURE_NO_WARNINGS.
See documentation on how to use Visual C++ 'Checked Iterators'

What's that about?

EDIT 2: The program works fine in Release mode, which leads me to suspect I am doing something dodgy with dynamic memory handling. I am not experienced in it.

EDIT 3: Instead of using delete &stack[sp], I used stack[sp] = 0. Does that sound fishy? Have I leaked memory? It seems I have; after calling the destructor my memory use does not go down.

I used delete[] stack in the destructor. It frees the memory but gives an access violation.

This post has been edited by PlasticineGuy: 11 February 2010 - 11:58 PM

[Bench]

Visual Studio is being a bit over-zealous by warning you that a pointer is not a checked iterator. other types of iterators are 'exception safe' - meaning that they throw an exception when you try to do something wrong with them. Otherwise, there's nothing technically wrong with using un-checked iterators in copy, except that its safer to use an STL container (e.g vector/list/etc).


Unless you want to delete the entire array block, you cannot release its memory back to the OS, otherwise you'll end up corrupting the heap. It would be easier to leave the element in memory - you can leave it alone and reuse or clean it up later - doing this won't cause any leaks.

[PlasticineGuy]

How can you delete the whole array block? Why, specifically, does delete[] not work?

[Martyn.Rae]

I might have got the wrong end of things here, but if you have templated a stack of integer values, then you cannot of course delete it. Unless the template code has allocated it, it cannot delete it.

[baavgai]

Other than the whacky "sp > MAX(sizeof(stack), 1) / sizeof(T)" business, it worked fine for me. There was a non standard call of std::exception. And that you didn't bother returning a value in main.

There were some messy bits. And addmem was redundant. The use of exceptions make little sense, except on the pop, IMHO. Your destructor shouldn't bitch if still has values, it should fix it. It's also a memory leak.

I did, of course, compulsively fix it, if you're interested.

#include <iostream>
#include <exception>
#include <stdexcept>

// using namespace std;

#define TMPL template <class T>
#define MAX(a, B)/> ((a>B)/>?a:B)/>

namespace saq {
	TMPL
	class Stack {
		public:
			Stack(int size = 31000): sp(0), stack(new T[size]), sz(size) {}
			~Stack(void) { 
				//if(sp != 0) throw std::runtime_error("Pushed values not popped."); 
				delete[] stack;
			}
			T push(T value);
			T pop(T& dest);
			T pop(void);
			int getsize(void) const;
			void addmem(const int mem);
			T* getstack(void);
		private:
			int sp, sz;
			T *stack;	
	};
	TMPL
	T saq::Stack<T>::push(T value) {
		stack[sp++] = value;
		return value;
	}
	TMPL
	T saq::Stack<T>::pop(T& dest) {
		if(sp==0) {
			throw std::runtime_error("Attempting to pop a value not pushed.");
		}
		dest = stack[--sp];
		return dest;
	}
	TMPL
	T saq::Stack<T>::pop() {
		T ret;
		pop(ret);
		return ret;
	}
	TMPL
	void saq::Stack<T>::addmem(const int mem) {
		T *temp;
		temp = new T[sz + mem];
		memcpy(&temp, &stack, sizeof(stack));
		delete[] stack;
		// wtf?
		// stack = new T[sz + mem];
		// memcpy(&stack, &temp, sizeof(temp));
		// sz += mem;
		// delete[] temp;
		stack = temp;
	}
	
	TMPL int saq::Stack<T>::getsize(void) const { return sz; }
	
	TMPL T* saq::Stack<T>::getstack(void) { return stack; }
}
int main() {
	saq::Stack<int> myStack(2);
	myStack.push(20);
	myStack.push(30);
	std::cout << myStack.pop() << std::endl;
	// std::cin.get();
	myStack.pop();
	
	return 0;
}

[Bench]

PlasticineGuy, on 12 February 2010 - 09:36 AM, said:

How can you delete the whole array block? Why, specifically, does delete[] not work?

What happens when you call delete is a little bit more complicated than just cleaning up memory - that's the reason there are two different versions of delete (one which is 'delete' and the other is 'delete[]')

To understand what 'delete' is doing, you need to understand what 'new' is doing

struct foo
{
    int a,b;
};

int main()
{
    foo* bar = new foo;
    delete bar;
} 

This version of new allocates a small chunk of memory on the heap whose size is sizeof foo. After this, it calls the foo constructor.

the matching call to delete calls the foo destructor and then releases that memory back to the OS; it assumes that 'bar' is not part of an array (correctly)

struct foo
{
    int a,b;
};

int main()
{
    foo* bar = new foo[5];
    delete [] bar;
} 

The second version of new[] allocates sizeof(foo) * 5 bytes on the heap, but also secretly records the fact that 5 objects have been allocated (usually as a "preamble" in the bytes which precede the array - although exactly how that works is up to your compiler). This extra bit of information is important, because its the only information which 'delete []' has access to in order ensure that it correctly destroys every element.
this version of 'new' also calls the foo constructor 5 times, once for each object.

The matching version of delete[] first looks at the extra information regarding how many objects it needs to destroy - it will then loop through each element and call their destructor; this is the reason why you cannot release sections of an array, because when you call delete[], that memory will be accessed by the foo destructor - if you had previously released that memory prematurely using 'free' or the wrong version of delete, then the heap will be corrupted.

Safe to say that mixing the subscript and non-subscript versions of new/delete with each other is undefined, so you shouldn't try it - as a rule of thumb, only ever use 'delete[]' on the first element of the array to destroy the entire block, and never use the ordinary 'delete' on any part of an array.

I hope this clarifies things a little; its also worth noting that usually there's no point in shrinking an array - memory allocated to your program which isn't currently being used can still be re-used later as long as you don't leak it. (The STL vector does not shrink in size when you remove elements, because its likely that you'll reuse that memory again later - constantly resizing is rather expensive, whereas reserving a bit of extra memory is cheap)

This post has been edited by Bench: 12 February 2010 - 04:39 AM

[baavgai]

I just looked at that addmem again, still wrong. A call to sizeof(stack) will only get you the size of a pointer.

Here:

TMPL
void saq::Stack<T>::addmem(int mem) {
	T *temp = new T[sz + mem];
	memcpy(&temp, &stack, sz*sizeof(T));
	delete[] stack;
	sz += mem;
	stack = temp;
}

[PlasticineGuy]

Here's my current implementation (this is solved, by the way):

void saq::Stack<T>::addmem(const int mem) {
	T *temp;
	temp = new T[sz + mem];
	std::copy(stack, stack + sz, temp);
	delete[] stack;
	stack = new T[sz + mem];
	std::copy(temp, temp + sz + mem, stack);
	sz += mem;
	delete[] temp;
}

It works.

EDIT:

Quote

And that you didn't bother returning a value in main.

No need to . The C++ specification defines that main returns 0 by default if you don't bother (lazy I know).

This post has been edited by PlasticineGuy: 12 February 2010 - 05:42 AM

[Bench]

PlasticineGuy, on 12 February 2010 - 12:39 PM, said:

Here's my current implementation (this is solved, by the way):

void saq::Stack<T>::addmem(const int mem) {
	T *temp;
	temp = new T[sz + mem];
	std::copy(stack, stack + sz, temp);
	delete[] stack;
	stack = new T[sz + mem];
	std::copy(temp, temp + sz + mem, stack);
	sz += mem;
	delete[] temp;
}

It works.

The second block is redundant - both of those blocks you've allocated are the same size

void saq::Stack<T>::addmem(const int mem) {
	T *temp = new T[sz + mem];
	std::copy(stack, stack + sz, temp);
	delete[] stack;
	stack = temp;
	sz += mem;
}

[baavgai]

PlasticineGuy, on 12 February 2010 - 06:39 AM, said:

It works.

Badly. Simply "working" should never be an excuse.

Last attempt to explain:

void saq::Stack<T>::addmem(const int mem) {
	T *temp;
	temp = new T[sz + mem];
	std::copy(stack, stack + sz, temp); // good, more C++y, sort of
	delete[] stack; // good, you've copied it, free it now
	// bad, you are creating a new empty space
	// stack = new T[sz + mem]; 
	// bad, you now copying again
	// std::copy(temp, temp + sz + mem, stack);
	sz += mem;
	// bad, you're killing a perfectly good pointer
	// delete[] temp;
	// better, avoidng allocation and duplicate effort
	stack = temp;
}

Good luck.