Asignación de memoria durante la inserción en un mapa

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

Compilar con g ++ -wall -ansi test.cpp -o test

Ejecute la prueba.

¿Por qué hay tres llamadas a GetMemory con n = 0?

Answer 1

Realice un poco de seguimiento en FreeMemory y cambie main a esto:

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

}

Producción:

$ 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

Entonces, de sus 3 asignaciones de tamaño 0:

• Una es copiar el vector vacío en el par.
• Una es almacenar una copia del vector vacío en el mapa.

Estos dos son claramente necesarios.De lo que no estoy seguro es de esto:

• Una es copiar el vector en algún lugar de la llamada a insert, y esto también se libera en la llamada a insertar.

Es como si insert (o algo que llama internamente) está tomando su parámetro por valor en lugar de por referencia, o insert está tomando explícitamente una copia en una variable automática algún tiempo antes de asignar el nuevo nodo del mapa.Activar un depurador es un esfuerzo para mí en este momento, se lo dejaré a otra persona.

Editar:misterio resuelto. insert toma una std::pair<const int, vec>, No un std::pair<int, vec>.La copia adicional de un vector vacío se debe a que el par que construye debe convertirse en un (otro) temporal, luego se pasa una referencia a ese temporal insert.std::pair tiene una plantilla de constructor que te permite hacer casi cualquier cosa.20.2.2/4:

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

Efectos:Inicializa a los miembros de los miembros correspondientes del argumento, realizando conversiones implícitas según sea necesario.

También observo que en mi implementación, vec x; no llama getMem, pero vec x(0); hace.Entonces en realidad:

z[1] = vec();

Es menos código y le niega la oportunidad de hacer la copia extra (aunque llama operator= en cambio).Todavía hace asignaciones de tamaño 20, al menos para mí.

El estándar C++ define operator[] para devolver el resultado de una expresión especificada que implica una llamada a insert.No estoy seguro de si esto significa los efectos de operator[] son "como si" make_pair y insert fueron llamados (es decir, el estándar es tan bueno como especificar cuál debe ser la fuente para operator[]), o simplemente que el valor devuelto es el mismo valor que produciría la expresión especificada.Si es esto último, tal vez una implementación podría hacerlo con una única asignación de tamaño 0.Pero ciertamente map no tiene una forma garantizada de crear una entrada sin crear primero un par que contenga el tipo asignado, por lo que se deben esperar 2 asignaciones.O más propiamente, 2 copias del valor mapeado deseado:el hecho de que copiar un vector de tamaño 0 genere una asignación de tamaño 0 depende de la implementación.

Entonces, si tuviera un caso en el que el valor fuera muy costoso de copiar, pero muy barato de construir de forma predeterminada (como un contenedor con muchos elementos), entonces lo siguiente podría ser útil:

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;

realiza 2 asignaciones de tamaño 4000 y 2 de tamaño 0, mientras que:

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

hace 3 de tamaño 4000 y ninguno de tamaño 0.Al final, el tamaño es lo suficientemente grande como para que la asignación adicional en el primer código sea más barata que la copia adicional en el segundo código.

Es posible que los constructores de movimientos en C++ 0x ayuden con esto, no estoy seguro.

Answer 2

Todos los 3 casos relacionados con la inicialización del vector vacío:

1. para init elemento raíz del árbol (aplicación interna de std :: mapa) que contendría vector vacío.
2. su propia inicialización de 'x vec'.
3. constructor de copia para std :: par de elemento de 'segunda' que invoca la copia de conjunto vacío de la variable 'x'