如何在此自定义堆栈实现中正确分配更多内存？

Question

我试图让它每次超过大小时我的Stack大小加倍.我需要创建一个新的堆栈来保存旧堆栈,但是需要加倍.需要删除旧堆栈.下面的代码一直给我错误

"堆栈(17854,0x7fff77cd0300)malloc:*对象0x1001054b0的错误:未释放指针被释放*在malloc_error_break中设置断点以进行调试"

此外,每次运行程序时生成的随机数都是相同的.救命!

#include <iostream>
using namespace std;

const int DEFAULT_SIZE = 100;

template< class T >
class Stack {
public:
    Stack( int = 10 );  // default constructor (stack size 10)
    // destructor
    ~Stack() {
            delete [] stackPtr;
    }

    bool push( const T& );
    bool pop( T& );
    int pop();

    // determine whether Stack is empty
    bool isEmpty() const {
            return top == -1;
    }

    // determine whether Stack is full
    bool isFull() const  {
            return top == size - 1;
    }

private:
    int size;     // # of elements in the stack
    int top;      // location of the top element
    T *stackPtr;  // pointer to the stack
};

// constructor
template< class T >
Stack< T >::Stack( int s ) {
    size = s > 0 ? s : 10;
    top = -1;  // Stack initially empty
    stackPtr = new T[ size ]; // allocate memory for elements
}

template< class T >
bool Stack< T >::push( const T &pushValue ) {
    if ( !isFull() ) {
        stackPtr[ ++top ] = pushValue;
        return true;
    }

    T *newPtr = new T[size*2];
    newPtr = stackPtr;
    delete [] stackPtr;
    return true;
}

template< class T >
bool Stack< T >::pop( T &popValue ) {
    if ( !isEmpty() ) {
        popValue = stackPtr[ top-- ];  // remove item from Stack
        return true;
    }

    return false;
}

template <class T>
int Stack< T >::pop() {
    return stackPtr[--size];
}

int main() {
    Stack<int> s;
    int i = 0;
    for (i=0; i < DEFAULT_SIZE; i++) {
        s.push( rand() % 100 +1 );
    }

    for (i=0; i < DEFAULT_SIZE; i++) {
        cout << s.pop() << " , ";
        if (i % 20 == 0) {
            cout << endl;
        }
    }
}

Answer 1

看一下这段代码,它来自你的push实现(它是你分配更多内存的部分):

1: T *newPtr = new T[size*2];
2: newPtr = stackPtr;
3: delete [] stackPtr;
4: return true;

在视觉上,这是正在发生的事情.在第1行之前,事情看起来像这样:

 +----------+       +-----+-----+-----+-----+
 | stackPtr | ----> | 137 | 271 | 281 | 284 |
 +----------+       +-----+-----+-----+-----+

执行第1行后,事情看起来像这样:

 +----------+       +-----+-----+-----+-----+
 | stackPtr | ----> | 137 | 271 | 281 | 284 |
 +----------+       +-----+-----+-----+-----+
 +----------+       +-----+-----+-----+-----+-----+-----+-----+-----+
 |  newPtr  | ----> |  ?  |  ?  |  ?  |  ?  |  ?  |  ?  |  ?  |  ?  |
 +----------+       +-----+-----+-----+-----+-----+-----+-----+-----+

执行第2行后,事情看起来像这样:

 +----------+       +-----+-----+-----+-----+
 | stackPtr | --+-> | 137 | 271 | 281 | 284 |
 +----------+   |   +-----+-----+-----+-----+
 +----------+   |   +-----+-----+-----+-----+-----+-----+-----+-----+
 |  newPtr  | --+   |  s  |  o  |     |  a  |  l  |  o  |  n  |  e  |
 +----------+       +-----+-----+-----+-----+-----+-----+-----+-----+

哎呀.你刚刚孤立了一堆记忆.

执行第3行后,事情看起来像这样:

 +----------+        
 | stackPtr | --+->    kablooie! deleted memory.
 +----------+   |
 +----------+   |
 |  newPtr  | --+
 +----------+     

请注意,当你完成后,你最终得到了孤立的内存(所有的？),你的stackPtr变量现在指向死记忆.哎呀.

要解决此问题,您需要进行一些更改.首先,当你写作

newPtr = stackPtr;

我的感觉是你打算将旧数组中的所有元素复制到新数组中.不幸的是,如上所述,你所写的并不符合你的想法.要解决此问题,您需要一次一个地明确移动元素.考虑使用for循环来执行此操作 - 一次从stackPtr一个元素读取并写入相应的条目newPtr.

其次,您需要进行更改,stackPtr以便在炸毁之前分配的内存后,将其指向新分配的内存.一种方法是写

stackPtr = newPtr;

在你释放了记忆之后stackPtr.

这里还有另外一个问题.请注意,size在分配新阵列后,您从未实际更新过.这意味着虽然您将获得一个全新的阵列,但您实际上并不记得它有多大.因此,在完成其他所有操作后,请确保更新,size以便它比以前大两倍.

代码中可能还有其他问题,但我怀疑这有助于您入门.要记住的一些事情:

1. 使用指针时绘制图片绝对不会受到伤害.
2. 注意不要将"指定指针"与"数组的复制元素"混淆.
3. 记得做所有必要的簿记.

祝好运!