как сделать мой класс стека динамическим

Question

я пишу класс стека в 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);
    }

};

Answer 1

Вы должны распределять его динамически, когда возникает необходимость. Может быть, что-то вроде этого:

#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;
            }
        }
};

Также небольшой отказ от ответственности, этот код был написан прямо в браузере. Это не проверено, но должно работать в принципе ...:)

Answer 2

Вы также можете использовать 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();};
};

Answer 3

Любой массив, подобный структуре, будет дорого увеличивать и уменьшать (T должен быть копируемым), а все существующие T должны быть перемещены. Если вы обнаружите, что вы делаете много нажатий / всплывающих окон и вам необходимо поддерживать низкое потребление памяти, попробуйте использовать связанный список для внутреннего использования. Это должно быть только по одной ссылке.

Вот эскиз:

template <class T>
class stack
{
  struct Node
  {
    T data;
    Node* next;
  };
public:

  // methods

private:
  Node *head;
};

Теперь, чтобы поместить что-то в стек, создайте Node с помощью T, установите следующий указатель на текущий head, а head на указатель Node. Поппинг включает в себя next из head и установку в head.

Конечно, вам нужно правильно управлять памятью при уничтожении и т. Д.

РЕДАКТИРОВАТЬ: ах, похоже, мое предположение, что вы, возможно, знаете основы C ++, неверно, я предположил, что вы сделали, как вы используете шаблон. В этом случае - игнорируйте этот ответ, пока не изучите основы!