Wie zerstört der Vektor std :: seine Objekte?

Question

Ich versuche, meinen eigenen std :: Vektor aus Gründen der Praxis zu implementieren. Aktuelle Quellcode: http://pastebin.com/bE4kjzcb

---

Hier eine Übersicht meiner Klasse:

1. Array() etwas Speicher zuteilen mit malloc()
2. push_back(const T &t) ein Element hinzuzufügen, rufen Sie realloc(), falls erforderlich.
3. ~Array() Anruf free(), um Speicher freizugeben.

Das Hauptproblem mit diesem Modell ist, rezykliert free() die Erinnerung, aber es nennt destructor nicht T ‚s (wenn T eine Klasse ist eher als Standard-Datentyp).

Dies kann zu schwerwiegenden Ressourcenverlusten führen, wenn Elemente in Vektoren Objekte sind. Meine Lösung für dieses Problem ist, rufen Sie ~T()EXPLICITLY vor ich free() der Speicher.

Der Grund, warum ich malloc() verwende, ist, versuche ich realloc() zu verwenden. Wenn ich new und delete verwende, wird die Speicherbelegung bei der Neuzuweisung ihren Höchstwert erreichen. (Der Moment, wenn sowohl der neue Puffer als auch der alte Puffer vorhanden sind.)

Q: Ist das ein schlechtes Design? Wie funktioniert std::vector dieses Problem zu lösen? Gibt es andere Fehler in meiner Vektorklasse?

PS: Sprechen wir jetzt nicht über Multithread-Leistungen von malloc().

Answer 1

Aufruf ~T() ist genau wie std::vector behandelt das Problem.

Sie jedoch ein paar Probleme haben:

Erstens muss push_back Platzierung nutzen, um neue, den Wert in den Vektor kopieren-konstruieren. Sie können nicht einfach die Zuweisung verwenden.

Zweitens können Sie nicht anrufen realloc - wenn das Objekt interne Zeiger haben, werden sie am Ende außerhalb von ihnen selbst zeigen. Sie müssen erneut malloc aufrufen, dann mit placement new die Werte kopieren, dann explizit alle alten Werte löschen und dann free aufrufen, um den alten Wert freizugeben.

(Eigentlich std::vector stellt nicht ~T() selbst. Stattdessen ruft er die Allocator, die für verantwortlich ist ... Aufteilung und Speicher ausplanen. Innerlich aber das ist, wie Mehrzweckverteilern es tun.)

Answer 2

Anstatt zu malloc und free zu rufen, lieber new und delete verwenden. Der Aufruf von delete stellt sicher, dass die Instanz dtor aufgerufen wird. =)

Answer 3

An der Grenze ist es möglich, neu zu verwenden [] wenn der Standard-Konstruktor für nur zugewiesen Objekte reserviert, und wenn die/Bewegung/Kopierkonstruktoren/Zuweisungsoperator und destructor von T die Informationen verbreiten gerade zugeordnet oder Benutzerobjekt. Die Lösung in std :: vector und ihrem Standard-Allokator ist dennoch ein weitaus besseres Design.

Die Konstruktion

buffer = new T[capacity]; 

anstelle von

buffer = (T*)malloc(capacity * sizeof(T)); 

und

delete [] buffer; 

anstelle von

free(buffer); 

die destructor jedes Objekts, wie am Beispiel automatisch aufrufen

class A { 
public: 
    ~A() { std::cout << "ok" << std::endl; } 
}; 

int main() { 
    A* a = new A[3]; 
    delete [] a; 
    return 0; 
} 

Dieser Code Ausgänge 3 „ok“. Dann sollte A zusätzliche Felder und einen nicht standardmäßigen Konstruktor enthalten, um die Zuordnung von der Benutzerkonstruktion zu unterscheiden.

Answer 4

push_back (const T & t) fügen Sie ein Element hinzu, rufen Sie realloc() falls erforderlich auf.

Es ist in Ordnung, solange Ttrivially copiable ist zum Beispiel versuchen, wieder doppelt verkettete Listen schieben und nach reallcoation man nehmen und durchlaufen nach hinten - die App wird wahrscheinlich zum Absturz bringen. Die Lösung besteht darin, die Funktion zweimal zu überladen, eine für Typen, die dreifach kopierbar sind, und eine für Objekte, die nicht kopierbar sind.

Im Gegensatz zu anderen, tut mir leid, dass die Standard-Container realloc nicht für Objekte verwenden, die trivial kopierbar sind. zumindest unter Windows prüft realloc zuerst, ob der aktuelle Block die neue Größe enthalten kann und wenn ja, aktualisiert er nur den Heap-Eintrag, was zu einer enormen Leistungssteigerung führt (kein Kopieren).

ruf ~ T() EXPLIZITLY bevor ich frei() den Speicher.

Ja, das ist der Standard-Allokator.nehmen size die Objektanzahl ist, Sie jedes iterieren und zerstören es manuell:

for (auto i=0U;i<size;i++){ 
    data[i].~T(); 
} 

Interessanterweise C++ 17 wird std::destruct hinzufügen, die genau das tut.

Bonus: Mit new[] und delete[] wird hier nicht helfen. in der Regel, dynamische Arrays speichert mehr Speicherplatz als das, was sie brauchen, um die Kapazität zu erreichen, ist der zusätzliche Platz nicht mit Live-Objekten gefüllt, nur Müll.

new[] füllt den gesamten Speicher mit Objekten. Kapazität kann auf diese Weise nicht implementiert werden. Das Array wird die gesamten Objekte verschieben/kopieren, wenn jemand neue Elemente zurückschiebt. also nach 1000 push_back wird es 1000 Neuzuweisungen geben. wir wollen amortisierte Zeit von O(log (n)).

auch die Standard-Allocator rufen new(size_t) oder malloc und nicht new[]

Answer 5

Hier sehen Sie ein Beispiel haben, wie es mehr oder weniger std :: vector funktioniert:

#ifndef __STDVECTOR__ 
#define __STDVECTOR__ 

#include <iostream> 

using namespace std; 

template <typename T> 
    class StdVector{ 
     private: 
      T *buffer; 
      unsigned int capacity; 
     public: 
      //Constructor. 
      StdVector(){ 
       capacity=0; 
       buffer=new T[capacity]; 
      } 
      //Copy constructor. 
      StdVector(const StdVector &asv){ 
       int i; 

       capacity=asv.getCapacity(); 
       buffer=new T[asv.getCapacity()]; 
       for (i=0; i<capacity; i++){ 
        buffer[i]=asv[i]; 
       } 
      } 
      //Destructor. 
      ~StdVector(){ 
       delete []buffer; 
      } 
      void push_back(T obj){ 
       StdVector oldSV(*this); 
       int i; 

       capacity++; 
       delete []buffer; 
       buffer=new T[capacity]; 
       for (i=0; i<oldSV.getCapacity(); i++){ 
        buffer[i]=oldSV[i]; 
       } 
       buffer[i]=obj; 
      }; 
      T getBuffer() const{ 
       if (capacity==0){ 
        throw exception(); 
       } 
       return *buffer; 
      }; 
      T &operator[](int index) const{ 
       if (index>=capacity){ 
        //Out of range. 
        throw exception(); 
       } 
       else{ 
        return buffer[index]; 
       } 
      } 
      StdVector &operator=(const StdVector &obj){ 
       capacity=obj.getCapacity(); 
       delete []buffer; 
       buffer=new T[capacity]; 
       buffer=obj.getBuffer(); 
       return *this; 
      } 
      unsigned int getCapacity() const{ 
       return capacity; 
      }; 
    }; 

#endif 

int main(){ 
    try{ 
     StdVector<int> test; 
     StdVector<string> test2; 
     unsigned int i; 

     test.push_back(5); 
     test.push_back(4); 
     test.push_back(3); 
     test.push_back(2); 
     test.push_back(1); 
     test.push_back(0); 
     test.push_back(-1); 
     test.push_back(-2); 
     test.push_back(-3); 
     test.push_back(-4); 
     test.push_back(-5); 
     for (i=0; i<test.getCapacity(); i++){ 
      cout << test[i] << endl; 
     } 
     test2.push_back("Hello"); 
     test2.push_back(" "); 
     test2.push_back("World"); 
     test2.push_back("."); 
     cout << "---------------" << endl; 
     for (i=0; i<test2.getCapacity(); i++){ 
      cout << test2[i]; 
     } 
     cout << endl; 
    } 
    catch(...){ 
     cout << "Exception." << endl; 
    } 
    return 0; 
} 

Er druckt:

-1

-2

-3

-4

-5

--------- ------

Hallo Welt.

Vielleicht habe ich einen Fehler. Wenn Sie es wissen, sagen Sie mir bitte.