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

Question

我正在努力做到每次超过大小时我的 Stack 的大小都会加倍。我需要创建一个新堆栈来容纳旧堆栈，但大小要翻倍。需要删除旧堆栈。下面的代码一直给我错误

"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. 记得做所有必要的簿记工作。

祝你好运!