15

私の質問は、の効果に関するvector::push_backものです。ベクトルの最後に要素が追加されることはわかっていますが、フードの下ではどうなりますか？

IIRCメモリオブジェクトは順番に割り当てられるので、私の質問はvector::push_back、ベクトルの直後により多くのメモリを割り当てるかどうかです。割り当てられる場合、その場所に十分な空きメモリがない場合はどうなりますか？または、ベクトルが継続する場所に「ホップ」するように、「終了」にポインタが追加されている可能性がありますか？それとも、十分なスペースがある別の場所にコピーして古いコピーを破棄するだけで再割り当てされますか？それとも何か他のもの？

4

7 に答える 7

23

すでに十分なスペースが割り当てられている場合、オブジェクトは所定の引数からコピー構築されます。十分なメモリがない場合、ベクトルはある種の等比数列に従って内部データバッファを拡張し（新しいサイズが[1]になるたびにk*old_size）k > 1、元のバッファに存在するすべてのオブジェクトが新しいバッファに移動されます。操作が完了すると、古いバッファがシステムに解放されます。

前の文では、 moveは技術的なmove-constructor / move-assignmentの意味では使用されていません。移動、コピー、または同等の操作が可能です。

[1]係数で成長k > 1すると、の償却原価push_backが一定になります。実際の定数は実装ごとに異なります（Dinkumwareは1.5を使用し、gccは2を使用します）。償却されたコストとは、 （その時点でのベクトルのサイズに関して）push_back非常に高価になることが多い場合でも、挿入のセット全体にわたるすべての操作のコストがO(N)挿入、したがって各挿入は一定のコストを平均します）

于 2011-10-26T07:52:51.417 に答える
4

ベクトルのスペースが不足すると、そのアロケータを使用してより多くのスペースを予約します。

これをどのように実装するかを決めるのはアロケータ次第です。

ただし、ベクトルは予約するスペースの量を決定します。標準では、ベクトル容量が幾何学的に少なくとも1.5 1 倍に増加することが保証されているため（コメントを参照）、「小さな」割り当てが繰り返されることによるひどいパフォーマンスを防ぎます。

要素の物理的な移動/コピーについて：

  • c ++ 11準拠の実装は、ムーブ代入と構築をサポートしている場合、要素を移動します
  • 私が知っているほとんどの実装（特にg ++）は、PODタイプにstd::copyを使用します。PODタイプのアルゴリズムの特殊化により、これが（本質的に）memcpy操作にコンパイルされることが保証されます。これは、システムで最速のCPU命令（SSE2命令など）でコンパイルされます。

1 n3242標準ドラフト文書からその参照引用を見つけようとしましたが、現時点では見つけることができませんでした。

于 2011-10-26T07:54:05.780 に答える
2

スペースが不足するvectorと、スペースが再割り当てされ、すべての要素が新しい配列にコピーされます。その後、古いアレイは破棄されます。

割り当ての数が多すぎないようにし、平均push_back()時間をを維持するO(1)には、再割り当てでは、サイズを少なくとも一定の係数で増やす必要があります。（1.5と2が一般的です）

于 2011-10-26T07:49:54.743 に答える
2

ベクトルは、すべての要素がメモリ内で隣接していることを保証します。

内部的には、3つのポインター（またはポインターのように機能するもの）として定義されていると考えることができます。

start:     Points at the beginning of the allocated block.
final:     Points one past the last element in the vector.
           If the vector is empty then start == final 
capacity:  Points one past the end of allocated memory.
           If final == capacity there is no room left.

あなたが押し戻すとき。

  1. ファイナルが容量よりも小さい場合：
    • 新しい要素は、finalが指す場所にコピーされます
    • finalは次の場所にインクリメントされます。
  2. finalが容量と同じである場合、ベクトルはいっぱいです
    • 新しいメモリを割り当てる必要があります。
    • X*(capacity - start)*sizeof(t)その後、コンパイラはバイトを割り当てます。
    • ここで、Xは通常1.5から2の間の値です。
    • 次に、すべての値を古いメモリバッファから新しいメモリバッファにコピーします。
    • 新しい値がバッファに追加されます。
    • 開始/最終/容量ポインタを転送します。
    • 古いバッファを解放します
于 2011-10-26T07:59:21.967 に答える
0

終了ポインタを呼び出すとvector::push_back、容量ポインタと比較されます。新しいオブジェクトに十分なスペースがある場合は、使用可能なスペースにオブジェクトを作成するために呼び出され、終了ポインターが増分されます。placement new

十分なスペースがない場合、vector呼び出しはアロケータを呼び出して、少なくとも既存の要素と新しい要素に十分な連続スペースを割り当てます（実装が異なれば、割り当てられたメモリが異なる乗数で増大する可能性があります）。次に、既存のすべての要素と新しい要素が、新しく割り当てられたスペースにコピーされます。

于 2011-10-26T07:54:47.493 に答える
0

std :: vector overallocates-通常、必要以上のメモリを自動的に割り当てます。sizeこれによる影響はありませんが、を介して制御できますcapacity。

std :: vectorは、追加の容量が十分でない場合、すべてをコピーします。

std :: vectorによって割り当てられたメモリはrawであり、配置newを使用して、オンデマンドでコンストラクターが呼び出されることはありません。

したがって、push_backは次のことを行います。

  • 新しい要素に対して容量が十分でない場合は、
    • 新しいブロックを割り当てます
    • 既存のすべての要素をコピーします（通常はコピーコンストラクターを使用します）
  • サイズを1つ増やします
  • 新しい要素を新しい場所にコピーします
于 2011-10-26T07:55:06.650 に答える
0

配列の最終的なサイズがある程度わかっている場合は、vector::reserve最初にメモリを試してみてください。reserveとは異なることに注意してくださいvector::resize。配列のは変更されreserveませんvector::size()

于 2012-03-23T07:52:00.640 に答える