Распределение памяти при вставке в карту - PullRequest
7 голосов
/ 09 марта 2010
#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));
}

Компилировать с g ++ -Wall -ansi test.cpp -o test

Выполнить тест.

Почему три вызова GetMemory с n = 0?

Ответы [ 2 ]

8 голосов
/ 09 марта 2010

Вставьте некоторую трассировку в FreeMemory и измените основную на эту:

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

}

Выход:

$ 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

Итак, из ваших 3-х размеров:

  • Один - скопировать пустой вектор в пару.
  • Один - хранить копию пустого вектора на карте.

Эти два явно необходимы. В чем я не уверен, так это:

  • Один - скопировать вектор куда-нибудь в вызове в insert, и это также освобождается в вызове для вставки.

Это как если бы insert (или что-то вызываемое внутри) принимает свой параметр по значению, а не по ссылке, или insert явно копирует копию в автоматическую переменную некоторое время, прежде чем она выделяет новый узел карты. В данный момент для меня работа с отладчиком - это усилие, я оставлю это кому-то другому.

Редактировать: загадка раскрыта. insert занимает std::pair<const int, vec>, а не std::pair<int, vec>. Дополнительная копия пустого вектора заключается в том, что созданная вами пара должна быть преобразована во временный (другой), а затем ссылка на этот временный объект передается в insert. У std :: pair есть шаблон конструктора, который позволяет вам использовать практически все. 20.2.2 / 4:

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

Эффекты: инициализирует членов из соответствующие члены аргумента, выполнение неявных преобразований как необходимо.

Я также замечаю, что в моей реализации vec x; не вызывает getMem, а vec x(0); делает. Итак, на самом деле:

z[1] = vec();

Меньше кода и лишает вас возможности сделать дополнительную копию (хотя вместо этого она вызывает operator=). Это все еще делает 2 0 размера, по крайней мере для меня.

Стандарт C ++ определяет operator[] для возврата результата указанного выражения, включающего вызов insert. Я не уверен, означает ли это, что эффекты operator[] "как если бы" были названы make_pair и insert (то есть, стандарт так же хорош, как указание источника для operator[]), или просто то, что возвращаемое значение совпадает с указанным выражением. Если последнее, то, возможно, реализация могла бы сделать это с одним 0-размерным распределением. Но, безусловно, map не имеет гарантированного способа создания записи без предварительного создания пары, содержащей сопоставленный тип, поэтому следует ожидать 2 выделения. Или, точнее, 2 копии желаемого сопоставленного значения: тот факт, что копирование вектора с размером 0 делает распределение с размером 0, зависит от реализации.

Итак, если у вас был случай, когда значение было действительно дорогим для копирования, но действительно дешевым для конструирования по умолчанию (как контейнер с большим количеством элементов), тогда может пригодиться следующее:

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;

делает 2 выделения размера 4000 и 2 размера 0, тогда как:

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

делает 3 размера 4000 и ни одного размера 0. В конечном счете размер достаточно велик, чтобы дополнительное выделение в первом коде было дешевле, чем дополнительное копирование во втором коде.

Вполне возможно, что конструкторы перемещения в C ++ 0x помогут с этим, я не уверен.

6 голосов
/ 09 марта 2010

Все 3 случая, связанные с инициализацией пустого вектора:

  1. для инициации корневого элемента дерева (внутренняя реализация std :: map), который будет содержать пустой вектор.
  2. ваша собственная инициализация 'vec x'.
  3. конструктор копирования для std :: pair для элемента 'second', который вызывает копирование пустого набора переменных 'x'
...