我用 C++ 编写了一个堆栈类(如下所示),但它是静态的并且肯定会占用大量内存。我怎样才能使它动态化,以便在需要时为对象添加一些内存,而当我弹出一些东西时内存会自动删除?
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);
}
};
最佳答案
您必须在需要时动态分配它。可能是这样的:
#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;
}
}
};
还有一个小的免责声明,这段代码是直接写入浏览器的。它没有经过测试,但原则上应该可以工作......:)
关于c++ - 如何使我的堆栈类动态化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8475032/