7 
#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 が 3 回呼び出されるのはなぜですか?

4

2 に答える 2

8

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 サイズの割り当てについては、次のようになります。

  • 1 つは、空ベクトルをペアにコピーすることです。
  • 1 つは、空ベクトルのコピーをマップに格納することです。

この二つは明らかに必要です。私がよくわからないのはこれです：

  • 1 つは への呼び出しのどこかにベクトルをコピーすることinsertで、これも挿入の呼び出しで解放されます。

あたかもinsert(または内部で呼び出す何か) が、参照ではなく値によってパラメーターを取得してinsertいるか、新しいマップ ノードを割り当てる前に明示的に自動変数にコピーを取得しているようです。デバッガーの起動は、現時点では私の努力です。他の人に任せます。

追記：謎解き。ではなくinsertを取ります。空のベクトルの余分なコピーは、作成したペアを (別の) 一時的なものに変換する必要があるためです。その後、その一時的な参照が に渡されます。std::pair には、ほとんど何でも回避できるコンストラクター テンプレートがあります。20.2.2/4:std::pair<const int, vec>std::pair<int, vec>insert

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;

サイズ 4000 の 2 つの割り当てとサイズ 0 の 2 つの割り当てを行いますが、次のようになります。

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

サイズ 4000 の 3 を作成し、サイズ 0 は作成しません。最終的に、サイズが十分に大きくなるため、最初のコードでの余分な割り当ては、2 番目のコードでの余分なコピーよりも安くなります。

C++0x の move-constructors がこれに役立つ可能性がありますが、よくわかりません。

于 2010-03-09T12:48:37.847 に答える
6

空ベクトルの初期化に関する 3 つのケースすべて:

  1. 空のベクトルを含むツリーのルート要素 (std::map の内部実装) を初期化します。
  2. 「vec x」の独自の初期化。
  3. 変数 'x' の空のセットのコピーを呼び出す要素 'second' の std::pair のコピー コンストラクター
于 2010-03-09T10:25:03.560 に答える