c++ - 插入映射时的内存分配

#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

运行测试。

为什么在n = 0的情况下对GetMemory进行三个调用？

最佳答案

在FreeMemory中进行一些跟踪并将main更改为此:

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个0大小的分配中:

一种方法是将空 vector 复制到该对中。

一种方法是将空 vector 的副本存储在 map 中。

这两个显然是必要的。我不确定的是:

一种方法是将调用中的 vector 复制到insert，然后在插入中将其释放。

就像insert(或其内部调用的东西)正在通过值而不是通过引用获取其参数一样，或者insert在分配新的映射节点之前的某个时间明确地将一个副本复制到自动变量中。目前启动调试器是我的工作，我将其留给其他人。

编辑:谜团解决了。 insert接受std::pair<const int, vec>，而不是std::pair<int, vec>。空 vector 的额外副本是因为必须将您构造的对转换为一个(另一个)临时对象，然后将对该临时对象的引用传递给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大小的 vector 进行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，而3的大小都不为0。最终，该大小足够大，使得第一个代码中的额外分配要比第二个代码中的额外复制便宜。

我不确定，C++ 0x中的移动构造函数可能会对此有所帮助。