Speicherzuordnung während Einsetzen in eine Karte

Question

#include <stdio.h> 
#include <stdlib.h> 
#include <memory.h> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <map> 
#include <utility> 
#include <algorithm> 

void * GetMemory(size_t n) { 
    void *ptr = malloc(n); 
    printf("getMem n %d ptr 0x%x\n", n, reinterpret_cast<unsigned int> (ptr)); 
    return ptr; 
} 

void FreeMemory(void *p) { 
    free(p); 
} 

void* operator new (size_t n) { 
    void *p = GetMemory(n); 
    return p; 
} 

void* operator new [] (size_t n) { 
    void *p = GetMemory(n); 
    return p; 
} 

void operator delete (void *p) { 
    FreeMemory(p); 
} 

void operator delete [] (void *p) { 
    FreeMemory(p); 
} 

typedef std::vector<int> vec; 

int main(int argc, char *argv[]) { 
    std::map<int, vec> z; 
    vec x; 
    z.insert(std::pair<int,vec>(1,x)); 
} 

Compile mit g ++ -Wall -ansi test.cpp -o Test

Run Test.

Warum gibt es drei Aufrufe von GetMemory mit n = 0?

Answer 1

-Stick einige Verfolgung in Freememory und ändern Haupt dazu aufruft:

int main(int argc, char *argv[]) { 
    printf("map\n"); 
    std::map<int, vec> z; 
    printf("vec\n"); 
    vec x; 
    printf("pair\n"); 
    std::pair<int,vec> y(1,x); 
    printf("insert\n"); 
    z.insert(y); 
    printf("inserted 1\n"); 
    y.first = 2; 
    printf("insert\n"); 
    z.insert(y); 
    printf("inserted 2\n"); 

}

Ausgang:

$ make mapinsert CXXFLAGS=-O3 -B && ./mapinsert 
g++ -O3 mapinsert.cpp -o mapinsert 
map 
vec 
pair 
getMem n 0 ptr 0x6b0258 
insert 
getMem n 0 ptr 0x6b0268 
getMem n 32 ptr 0x6b0278 
getMem n 0 ptr 0x6b02a0 
FreeMemory ptr 0x6b0268 
inserted 1 
insert 
getMem n 0 ptr 0x6b0268 
getMem n 32 ptr 0x6b02b0 
getMem n 0 ptr 0x6b02d8 
FreeMemory ptr 0x6b0268 
inserted 2 
FreeMemory ptr 0x6b0258 
FreeMemory ptr 0x6b02d8 
FreeMemory ptr 0x6b02b0 
FreeMemory ptr 0x6b02a0 
FreeMemory ptr 0x6b0278 

So Ihrer 3 0-sized allo Kationen:

• Eins ist, den leeren Vektor in das Paar zu kopieren.
• Eine besteht darin, eine Kopie des leeren Vektors in der Karte zu speichern.

Diese beiden sind eindeutig notwendig. Was ich nicht sicher bin, ist dies:

• Eine davon ist der Vektor irgendwo in dem Aufruf von insert zu kopieren, und dies wird auch in dem Ruf befreit einzufügen.

Es ist, als ob insert (oder etwas, das es intern Anrufe) wird seine Parameter als Wert statt durch Referenz genommen wird, oder insert explizit eine Kopie in eine automatische Variable etwas Zeit nehmen, bevor sie den neuen Karten Knoten zuordnet. Einen Debugger zu starten ist für mich im Moment eine Anstrengung, ich überlasse es jemand anderem.

Edit: Geheimnis gelöst. insert dauert ein std::pair<const int, vec>, kein std::pair<int, vec>. Die zusätzliche Kopie eines leeren Vektors besteht darin, dass das von Ihnen konstruierte Paar in ein (anderes) temporäres umgewandelt werden muss. Dann wird ein Verweis auf dieses temporäre Objekt an insert übergeben. std :: pair hat eine Konstruktorvorlage, mit der Sie mit fast allem durchkommen können. 20.2.2/4:

template<class U, class V> pair(const pair<U,V> &p); 

Effekte: benötigten initialisiert Mitglieder aus den entsprechenden Mitgliedern des Arguments, implizite Konvertierungen als ausführen.

Ich beobachte auch, dass in meiner Implementierung vec x; nicht getMem nennen, aber vec x(0); tut. Also eigentlich:

z[1] = vec(); 

Ist weniger Code und verweigert Ihnen die Möglichkeit, die zusätzliche Kopie zu machen (obwohl es operator= fordert stattdessen). Es macht immer noch 2 0 Zuteilungen, zumindest für mich. Der C++ - Standard definiert operator[], um das Ergebnis eines angegebenen Ausdrucks mit einem Aufruf an insert zurückzugeben. Ich bin nicht sicher, ob dies bedeutet, die Auswirkungen von operator[] sind "als ob" make_pair und insert wurden aufgerufen (das heißt, der Standard ist so gut wie die Angabe, was die Quelle für operator[] sein muss), oder nur, dass der Wert zurückgegeben wird Der gleiche Wert wie der angegebene Ausdruck würde ergeben. Wenn Letzteres dann vielleicht eine Implementierung könnte es mit einer einzigen 0-Größe Allokation tun. Aber sicherlich map hat keine garantierte Möglichkeit, einen Eintrag zu erstellen, ohne zuerst ein Paar zu erstellen, das den zugeordneten Typ enthält, so dass 2 Zuweisungen erwartet werden sollten. Oder genauer gesagt, 2 Kopien des gewünschten abgebildeten Wertes: Die Tatsache, dass das Kopieren eines 0-dimensionalen Vektors eine 0-dimensionale Zuweisung macht, ist implementierungsabhängig.

Also, wenn Sie einen Fall haben, wo der Wert wirklich teuer zu kopieren, aber wirklich billig-Konstrukt Standard (wie ein Container mit vielen Elementen), dann kann die folgenden nützlich sein:

std::map<int, vec> z; 
vec x(1000); 
z[1] = x; 
// i.e. (*(z.insert(std::pair<const int, vec>(1,vec())).first)).second = x; 

macht 2 Zuweisungen von Größe 4000 und 2 der Größe 0, während:

std::map<int, vec> z; 
vec x(1000); 
z.insert(std::pair<const int, vec>(2, x)); 

macht 3 von Größe 4000 und keine Größe 0. Schließlich wird die Größe ist groß genug, dass die zusätzliche Zuteilung in dem ersten Code ist billiger als das zusätzliche Kopieren im zweiten Code.

Es ist möglich, dass Move-Konstruktoren in C++ 0x dabei helfen, ich bin mir nicht sicher.

Answer 2

alle 3 Fälle mit der Initialisierung des leeren Vektor betroffen:

1. Wurzelelement des Baumes (interne Implementierung std :: map) init, die leeren Vektor enthalten würde.
2. Ihre eigene Initialisierung von 'vec x'.
3. Copykonstruktor für std :: pair für Element 'zweite', das Kopieren leere Menge der Variable 'x'