34

私は本を​​調べていました: C++ Primer, Third Edition By Stanley B. Lippman, Josée Lajoie、 で与えられたプログラムで 1 つの間違いを見つけましたArticle 6.3 How a vector Grows Itself。このプログラムは s の "<" を見逃していましたcout:

#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> ivec;
    cout < "ivec: size: " < ivec.size() < " capacity: "  < ivec.capacity() < endl;
    
    for (int ix = 0; ix < 24; ++ix) {
        ivec.push_back(ix);
        cout < "ivec: size: " < ivec.size()
        < " capacity: "  < ivec.capacity() < endl;
    }    
}

その記事の後半：

「Rogue Wave の実装では、定義後の ivec のサイズと容量は両方とも 0 です。しかし、最初の要素を挿入すると、ivec の容量は 256 で、そのサイズは 1 です。」

しかし、コードを修正して実行すると、次の出力が得られます。

ivec: size: 0 capacity: 0
ivec[0]=0 ivec: size: 1 capacity: 1
ivec[1]=1 ivec: size: 2 capacity: 2
ivec[2]=2 ivec: size: 3 capacity: 4
ivec[3]=3 ivec: size: 4 capacity: 4
ivec[4]=4 ivec: size: 5 capacity: 8
ivec[5]=5 ivec: size: 6 capacity: 8
ivec[6]=6 ivec: size: 7 capacity: 8
ivec[7]=7 ivec: size: 8 capacity: 8
ivec[8]=8 ivec: size: 9 capacity: 16
ivec[9]=9 ivec: size: 10 capacity: 16
ivec[10]=10 ivec: size: 11 capacity: 16
ivec[11]=11 ivec: size: 12 capacity: 16
ivec[12]=12 ivec: size: 13 capacity: 16
ivec[13]=13 ivec: size: 14 capacity: 16
ivec[14]=14 ivec: size: 15 capacity: 16
ivec[15]=15 ivec: size: 16 capacity: 16
ivec[16]=16 ivec: size: 17 capacity: 32
ivec[17]=17 ivec: size: 18 capacity: 32
ivec[18]=18 ivec: size: 19 capacity: 32
ivec[19]=19 ivec: size: 20 capacity: 32
ivec[20]=20 ivec: size: 21 capacity: 32
ivec[21]=21 ivec: size: 22 capacity: 32
ivec[22]=22 ivec: size: 23 capacity: 32
ivec[23]=23 ivec: size: 24 capacity: 32

初期容量は式2^Nで容量は増加していますか? N説明してください。

4

6 に答える 6

89

ベクトルの容量が増加する速度は、実装に依存します。実装では、操作の償却された一定時間の要件を満たすために、ほとんどの場合、指数関数的な成長が選択されpush_backます。償却された一定の時間が何を意味し、指数関数的な成長がこれをどのように達成するかは興味深いものです。

ベクトルの容量が大きくなるたびに、要素をコピーする必要があります。ベクトルの存続期間にわたってこのコストを「償却」すると、指数関数的に容量を増やすと、償却された一定のコストになることがわかります。

これはおそらく少し奇妙に思えるので、これがどのように機能するかを説明しましょう...

  • サイズ: 1 容量 1 - 要素はコピーされていません。コピーの要素あたりのコストは 0 です。
  • size: 2 capacity 2 - ベクトルの容量が 2 に増加したとき、最初の要素をコピーする必要がありました。要素あたりの平均コピー数は 0.5 です
  • サイズ: 3 容量 4 - ベクトルの容量が 4 に増加したとき、最初の 2 つの要素をコピーする必要がありました。要素あたりの平均コピー数は (2 + 1 + 0) / 3 = 1 です。
  • サイズ: 4 容量 4 - 要素あたりの平均コピー数は (2 + 1 + 0 + 0) / 4 = 3 / 4 = 0.75 です。
  • サイズ: 5 容量 8 - 要素あたりの平均コピー数は (3 + 2 + 1 + 1 + 0) / 5 = 7 / 5 = 1.4
  • ...
  • サイズ: 8 容量 8 - 要素あたりの平均コピー数は (3 + 2 + 1 + 1 + 0 + 0 + 0 + 0) / 8 = 7 / 8 = 0.875
  • サイズ: 9 容量 16 - 要素あたりの平均コピー数は (4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 0) / 9 = 15 / 9 = 1.67
  • ...
  • サイズ 16 容量 16 - 要素あたりの平均コピー数は 15 / 16 = 0.938
  • サイズ 17 容量 32 - 要素あたりの平均コピー数は 31 / 17 = 1.82

ご覧のとおり、容量が急増するたびに、コピーの数が以前のアレイのサイズだけ増加します。ただし、容量が再び急増する前に配列のサイズを 2 倍にする必要があるため、要素あたりのコピー数は常に 2 未満のままです。

容量を 2 * N ではなく 1.5 * N 増やした場合、要素あたりのコピー数の上限が高くなることを除いて (私は 3 になると思います)、非常によく似た結果になります。

少しスペースを節約するためだけでなく、1.5 が黄金比に近いため、実装では 2 よりも 1.5​​ を選択すると思います。私は、黄金比に沿った成長率 (フィボナッチ数列との関係のため) が現実世界の負荷に対して最も効率的な成長率であることが証明されるという直観 (現在、具体的なデータによって裏付けられていません) を持っています。使用される余分なスペースと時間の両方を最小限に抑えるという点で。

于 2011-03-08T12:19:15.340 に答える
13

の最後に償却された定数時間の挿入を提供できるようにするstd::vectorには、実装は (必要に応じて) ベクトルのサイズを係数K>1(*) で拡大する必要がありますN。ベクトルは になりますK*N。

K異なる実装では、異なる利点を提供する異なる定数が使用されます。特に、ほとんどの実装では、 または のいずれK = 2かが使用されますK = 1.5。値が大きいほど、 growsKが少なくて済むため高速になりますが、同時にメモリへの影響が大きくなります。例として、 gccで、VS (Dinkumware)で。K = 2K = 1.5

(*) ベクトルが一定量だけ成長した場合、 の複雑さは償却定数push_backではなく線形になります。たとえば、必要に応じてベクトルが 10 要素増加した場合、増加 (すべての要素を新しいメモリ アドレスにコピー) のコストは(10 要素ごとに、すべてを移動) または になります。O( N / 10 )O( N )

于 2011-03-08T12:30:56.150 に答える
2

vector::push_backベクトルのサイズが であるとしnます。ここで気にするのは、これまでに発生したコピーの数ですy。ベクトルを大きくするたびにコピーが発生することに注意してください。

倍増 K

  y = K^1 + K^2 + K^3 ... K^log(K, n)
K*y =     + K^2 + K^3 ... K^log(K, n) + K*K^log(K, n)

K*y-y = K*K^log(K, n) - K
y = K(n-1)/(K-1) = (K/(K-1))(n-1)

T(n) = y/n = (K/(K-1)) * (n-1)/n < K/(K-1) = O(1)

K/(K-1)は定数であり、最も一般的なケースを参照してください。

  • K=2、T(n)=2/(2-1)=2
  • K=1.5、T(n)=1.5/(1.5-1)=3

実際には、さまざまな実装でK を 1.5 または 2 として選択する理由があります。このグラフを参照してください。T(n)KK

一定量で成長 C

y = C + 2*C + 3*C + 4*C +  ... (n/C) * C
  = C(1+2+3+...+n/C), say m = n/C
  = C*(m*(m-1)/2)
  = n(m-1)/2

T(n) = y/n = (n(m-1)/2)/n = (m-1)/2 = n/2C - 1/2 = O(n)

ご覧のとおりライナーです

于 2019-04-04T20:56:04.633 に答える
1

の容量vectorは完全に実装依存であり、それがどのように成長しているかは誰にもわかりません..

于 2011-03-08T12:09:25.233 に答える
1

「Rogue Wave」実装を使用していますか?

容量がどのように増加するかは、実装次第です。あなたは2 ^ Nを使用します。

于 2011-03-08T12:09:52.117 に答える
0

はい、超えるたびに容量が2倍になります。これは実装に依存します。

于 2011-03-08T12:09:54.693 に答える