11

ベクトルでのメモリ割り当てがどのように行われるかを判断するための小さなコードを書きました。

#include <iostream>
#include <vector>
using namespace std;
int main ()
{
  vector<unsigned int> myvector;
  unsigned int capacity = myvector.capacity();

  for(unsigned int i = 0; i <  100000; ++i) {
    myvector.push_back(i);
    if(capacity != myvector.capacity())
    {
      capacity = myvector.capacity();
      cout << myvector.capacity() << endl;
    }
  }
  return 0;
}

私はこれをUbuntuでVisualStudio2008とg++4.5.2を使用してコンパイルし、次の結果を得ました。

Visual Studio：

1 2 3 4 6 9 13 19 28 42 63 94141 211316474711 1066 1599 2398 3597 5395 8092 12138 18207 27310 40965 61447 92170 138255

capacity = capacity * 1.5;

g ++：

1 2 4 8 16 32 641282565121024 2048 4096 8192 16384 32768 65536 131072

capacity = capacity * 2;

ご覧のとおり、これらは2つの非常に異なる結果です。なんでこんな感じなの？それはコンパイラーだけに依存しているのでしょうか、それとも他の要因に依存しているのでしょうか？

多数の要素がある場合でも、容量を2倍にし続けることは本当に意味がありますか？

4

3 に答える 3

8

がどのようにvector成長しているかは、実装によって定義されます。したがって、同じ数の要素を挿入した後、さまざまな戦略を使用して容量が異なる可能性があります

割り当てられたアイテムの数に依存する必要がある場合はreserve、および/またはresizeメソッドを使用する必要がありますvector

于 2012-07-19T12:28:56.573 に答える
4

ご覧のとおり、VS は小さなチャンクで余分なスペースを追加していますが、G++ は 2 のべき乗でそれを行っています。これは、同じ基本的な考え方の単なる実装です。追加する要素が多いほど、次回はより多くのスペースが割り当てられます (追加のデータを追加する可能性が高いためです)。

ベクトルに 1 つの要素を追加したとします。私は 1000 を追加しました。さらに 1000 を追加する可能性が高く、そうする可能性は低くなります。これが、このようなスペース割り当て戦略の理由です。

正確な数は確かに何かに依存しますが、それはコンパイラメーカーの推論です。彼らはそれを好きなように実装できるからです。

于 2012-07-19T12:31:29.190 に答える
3

標準では、ベクターの動作のみが定義されています。内部で実際に何が起こるかは、実装によって異なります。容量を 2 倍にすると、n 要素をプッシュ/ポップするための償却された O(n) コストが発生します。これはベクトルに必要だと思います。詳しくはこちらをご覧ください。

于 2012-07-19T12:34:26.103 に答える