Wie ordne ich mehr Speicher in dieser benutzerdefinierten Stapelimplementierung korrekt zu?

Question

Ich versuche es so zu machen, dass sich mein Stack jedes Mal verdoppelt, wenn die Größe überschritten wird. Ich muss einen neuen Stapel erstellen, um den alten Stapel zu halten, aber doppelt so groß. Der alte Stapel muss gelöscht werden. Der folgende Code hält mich eine Fehlermeldung

"Stack (17854,0x7fff77cd0300) malloc: * Fehler für Objekt 0x1001054b0: pointer befreit wurde, einen Haltepunkt in malloc_error_break nicht zugeordnet * gesetzt zu debuggen"

Auch Die Zufallszahlen werden jedes Mal erzeugt, wenn ich mein Programm starte. HILFE!

#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

Dieser Code ist eindeutig falsch:

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

Sie einen neuen Zeiger zuweisen, dann ist es sofort verwerfen, dann löschen. So ist der neu zugewiesene Speicher durchgesickert und stackPtr ist bereits freigegeben und ungültig. Sie aktualisieren auch nicht size, wenn es sich ändert (gut, wenn es geändert worden wäre, wenn Sie Speicher wie ein Sieb nicht undicht waren), und Sie verwenden manchmal size, als Sie wahrscheinlich top meinten.

Answer 2

an diesem Code Werfen Sie einen Blick, die von Ihrem push Implementierung ist (es ist der Teil, wo Sie mehr Speicher zuzuteilen):

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

Optisch, hier ist was passiert. Vor der Linie 1, sieht es wie folgt aus:

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

Nach Linie 1 ausgeführt, sieht es wie folgt aus:

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

Nach Linie Ausführung 2, sieht es wie folgt aus:

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

Hoppla. Sie haben nur eine Menge Speicher verwaist.

Nach Linie Ausführung 3, sieht es wie folgt aus:

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

Beachten Sie, dass, wenn Sie fertig sind, haben Sie mit verwaisten Speicher (alle 's?) Beendet und Ihre stackPtr Variable jetzt Punkte zur toten Erinnerung. Hoppla.

Um dies zu beheben, müssen Sie einige Änderungen vornehmen. Erstens, wenn Sie schrieb

newPtr = stackPtr; 

mein Gefühl ist, dass Sie über alle Elemente aus dem alten Array auf die neue kopieren soll. Leider, wie oben dargestellt, tut das, was Sie geschrieben haben, nicht das, was Sie denken. Um dies zu beheben, müssen Sie die Elemente einzeln nacheinander verschieben. Ziehen Sie eine for-Schleife in Betracht, um dies zu tun - lesen Sie von stackPtr ein Element nach dem anderen und schreiben Sie in den entsprechenden Eintrag in newPtr.

Zweitens, müssen Sie stackPtr ändern, so dass Sie, nachdem Sie den Speicher, der zuvor zugewiesen wurde, aufgebläht haben, zeigen Sie auf den neu zugewiesenen Speicher.Eine Möglichkeit, dies zu tun, wäre

stackPtr = newPtr; 

zu schreiben, nachdem Sie den Speicher für stackPtr befreit haben.

Es gibt ein anderes Problem hier. Beachten Sie, dass Sie size nach der Zuweisung des neuen Arrays nie aktualisiert haben. Dies bedeutet, dass Sie zwar ein brandneues Array zur Verfügung haben, mit dem Sie arbeiten können, aber Sie werden sich nicht wirklich daran erinnern, wie groß es ist. Nachdem Sie alles andere erledigt haben, stellen Sie daher sicher, dass Sie size so aktualisieren, dass es doppelt so groß ist wie zuvor.

Möglicherweise gibt es andere Probleme im Code, aber ich vermute, dass dies Ihnen den Einstieg erleichtern wird. Einige Dinge zu erinnern:

1. Es tut nie weh, Bilder zu zeichnen, wenn Sie mit Zeigern arbeiten.
2. Achten Sie darauf, dass Sie "Zeiger zuweisen" nicht mit "Elemente eines Arrays kopieren" verwechseln.
3. Denken Sie daran, alle notwendigen Buchhaltung zu tun.

Viel Glück!

Answer 3

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

Dieser endet mit stackPtr auf sie zeigen den ursprünglichen Speicher nun gelöscht. Sie verschieben den Inhalt des alten Speichers auch nicht wirklich in den neuen Speicher. Es sollte so etwas wie:

T* newPtr = new T[size*2]; 
std::move(stackPtr, stackPtr + size, newPtr); 
delete[] stackPtr; 
stackPtr = newPtr; 

---

In Bezug auf rand jedes Mal die gleiche Sache zurückkehrt; Sie säen niemals den Zufallsgenerator. Sie müssen srand am Anfang des Programms anrufen, bevor Sie jemals rand anrufen.