i write a stack class in c++ (shown below) but it is static and sure it uses lots of memory's. how can i make it dynamic so when ever it need it add some memory to the object and when ever i pop something the memory automatically delete?
template <class T>
class stack
{
private:
T value[512];
uint16_t length;
public:
stack()
{
length=0;
}
stack(T _input)
{
value[0]=_input;
length=1;
}
bool push(T _input)
{
if(length+1<512)
{
value[++length]=_input;
return true;
}
else
return false;
}
T pop()
{
return value[length--];
}
T peak()
{
return value[length];
}
bool has_data()
{
return (length>0?true:false);
}
};
You have to allocate it dynamically when the need arises. Something like this maybe:
#define STACK_INITIAL_ALLOC 32
#define STACK_CHUNK_ALLOC 32
template<typename T>
class Stack
{
public:
Stack()
: data(0), entries(0), allocated(0)
{ }
Stack(const T &value)
: data(0), entries(0), allocated(0)
{
push(input);
}
~Stack()
{
if (data)
delete [] data;
}
void push(const T &value)
{
if (entries == allocated)
allocate(); // Allocate more memory
data[entries++] = value;
}
T pop()
{
if (entries > 0)
{
shrink();
return data[--entries];
}
else
throw runtime_error("stack empty");
}
T &top()
{
if (entries > 0)
return data[entries - 1];
else
throw runtime_error("stack empty");
}
// Return the number of entries in the stack
size_t count() const
{
return entries;
}
private:
T *data; // The actual stack
size_t entries; // Number of entries in stack
size_t allocated; // Allocated entries in stack
void copy(T *from, T *to)
{
for (size_t i = 0; i < entries; i++)
*to++ = *from++
}
void allocate()
{
if (data == 0)
{
allocated = STACK_INITIAL_ALLOC;
data = new T[allocated];
}
else
{
// We need to allocate more memory
size_t new_allocated = allocated + STACK_CHUNK_ALLOC;
T *new_data = new T[new_allocated];
// Copy from old stack to new stack
copy(data, new_data);
// Delete the old data
delete [] data;
allocated = new_allocated;
data = new_data;
}
}
// Shrink the stack, if lots of it is unused
void shrink()
{
// The limit which the number of entries must be lower than
size_t shrink_limit = allocated - STACK_CHUNK_ALLOC * 2;
// Do not shrink if we will get lower than the initial allocation (shrink_limit > STACK_INITIAL_ALLOC)
if (shrink_limit > STACK_INITIAL_ALLOC && entries < shrink_limit)
{
// We can shrink the allocated memory a little
size_t new_allocated = allocated - STACK_CHUNK_ALLOC;
T *new_data = new T[new_size];
copy(data, new_data);
delete [] data;
data = new_data;
allocated = new_allocated;
}
}
};
Also a small disclaimer, this code was written straight into the browser. It's not tested, but should work in principle... :)
You could also use std::vector :
template <class T>
class stack{
private:
std::vector<T> vec;
public:
inline void push(T arg){vec.push_back(arg);};
inline T pop(){return vec.pop_back();};
};
Any array like structure will be expensive to grow and shrink (T has to be copy constructible) and all the existing Ts have to be moved. If you find that you are doing lots of pushing/popping and you need to keep memory usage low, try using a linked list internally. It only has to be singly linked.
Here is a sketch:
template <class T>
class stack
{
struct Node
{
T data;
Node* next;
};
public:
// methods
private:
Node *head;
};
Now, to push something on the stack, construct a Node with the T, set it's next pointer to current head, and the head to the Node pointer. Popping involves taking next from the head and setting that to the head.
Of course you need to manage the memory correctly on destruction etc.
EDIT: ah it appears that my assumption that you may know the basics of C++ is incorrect, I assumed you did as you are using a template. In this case - ignore this answer till you've learned the basics!
