allocazione di memoria durante l'inserimento in una mappa

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));
}

Compila con g ++ -Wall -ansi test.cpp -o test

Test Run.

Perché ci sono tre chiamate al GetMemory con n = 0?

Answer 1

Stick alcuni tracing in FreeMemory e cambiare principale di questo:

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");

}

Output:

$ 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

Quindi, dei tuoi 3 allocazioni 0 dimensioni:

• One è copiare il vettore vuoto nella coppia.
• Uno è quello di conservare una copia del vettore vuoto nella mappa.

Questi due sono strettamente necessario. Quello che non sono sicuro di questo:

• Uno è quello di copiare il vettore da qualche parte nella chiamata a insert, e questo è anche liberato nella chiamata da inserire.

È come se insert (o qualcosa che definisce internamente) sta prendendo il suo parametro per valore anziché per riferimento, o insert sta prendendo esplicitamente una copia in una variabile automatica del tempo prima che alloca il nuovo nodo cartina. Sparare su un debugger è lo sforzo per me in questo momento, lascio a qualcun altro.

Modifica: mistero risolto. insert prende un std::pair<const int, vec>, non un std::pair<int, vec>. La copia aggiuntiva di un vettore vuoto è perché la coppia si costruisce deve essere convertito in un (altro) temporanea, quindi un riferimento a quella temporanea viene passato insert. std :: coppia ha un modello costruttore che consente di ottenere via con quasi tutto. 20.2.2 / 4:

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

  

Effetti: inizializza membri del   membri del parametro corrispondente,   eseguire conversioni implicite come   necessario.

Ho anche osservare che nella mia realizzazione, vec x; non chiama getMem, ma vec x(0); lo fa. Quindi, in realtà:

z[1] = vec();

è meno codice e si nega la possibilità di effettuare la copia in più (anche se chiama operator= invece). Lo fa ancora fare 2 assegnazioni 0 dimensioni, almeno per me.

La serie C ++ definisce operator[] per restituire il risultato di un'espressione specificata coinvolge una chiamata a insert. Io non sono sicuro se questo significa che gli effetti di operator[] sono "come se" make_pair e insert sono stati chiamati (vale a dire, lo standard è buono come specificando quale sia la fonte deve essere per operator[]), o semplicemente che il valore restituito è il stesso valore dell'espressione specificata produrrebbe. Se quest'ultimo allora forse un'implementazione potrebbe fare con una dotazione unica 0 dimensioni. Ma certamente map non ha modo garantito per creare una voce senza prima creare una coppia che contiene il tipo mappato, in modo da 2 assegnazioni dovrebbe essere previsto. O più propriamente, 2 copie del valore mappato desiderato:. Il fatto che la copia di un vettore 0-sized effettua una ripartizione 0 dimensioni dipende dall'implementazione

Quindi, se si ha un caso in cui il valore era molto costoso per copiare, ma davvero a buon mercato a (come un contenitore con un sacco di elementi) costrutto Default-, allora la seguente potrebbe essere utile:

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;

fa 2 assegnazioni di dimensioni 4000 e 2 di dimensione 0, mentre:

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

fa 3 di dimensioni 4000 e nessuno di dimensione 0. Alla fine la dimensione è abbastanza grande che l'allocazione in più nel primo codice è più conveniente che la copia in più nel secondo codice.

E 'possibile che si muovono-costruttori in C ++ 0x aiuterà con questo, non sono sicuro.

Answer 2

Tutti 3 casi interessati alla inizializzazione del vettore vuoto:

1. all'elemento init radice di albero (implementazione interna di std :: map) che dovrebbe contenere vettore vuoto.
2. la propria inizializzazione delle 'x vec'.
3. costruttore di copie per std :: coppia per elemento 'seconda' che richiama copiando insieme vuoto di variabile 'x'