c++ - コンテナー: ベクトル クラス....遅い

Question

ベクターコンテナで push_back 操作が通常遅い理由を誰か説明できますか? と言う人もいますが、少し遅い理由がわかりません。

初心者として vector と push_back を使用したいのですが、パフォーマンスを向上させる他のオプションはありますか? 私にお知らせください。ありがとう、

Answer 1

ベクターは、そのオブジェクトを連続した配列に格納します。オブジェクトを格納するために一定量のスペース (その容量) を割り当てます。オブジェクトの数 (そのサイズ) が容量を超えそうになると、より大きなスペースが割り当てられ、既存のオブジェクトがコピー (または移動) されます。

これには時間がかかる場合があります。それを回避し、再割り当てする必要がないことを保証するために、必要に応じて十分な大きさのブロックを事前に割り当てるように呼び出すことがpush_backできます。insertreserve

Answer 2

に項目を追加または挿入すると、std::vectorそれを保管するのに十分なスペースがない場合があります。これにより、ベクターはすべての要素を保持するのに十分なストレージを割り当て、それらを新しいメモリ ブロックにコピーします。ポインタではなく値でオブジェクトを格納している場合、これは完全なコピーが作成されます。複雑なタイプの場合、これが関係する場合があり、追加の割り当てとコピーが含まれます。このような状況では、ベクトルのサイズに応じてパフォーマンスが影響を受ける可能性があります。大きなベクトルの場合、パフォーマンスへの影響はより顕著になります。

Answer 3

push_back動作が常に遅くなるわけではありません。一定の複雑さ (償却時間) があります。唯一遅いのは、再割り当てが発生した場合です。便利なことの 1 つはstd::vector、サイズに関係なく、いつでもベクトルにオブジェクトを追加できることです。ベクトルの容量が 10 で、ベクトルに 10 個のオブジェクトがあるとすると、再割り当てが発生してベクトルが大きくなります。通常、ベクター サイズは 2 倍になり、オブジェクトは新しいベクターにコピーされますが、これは操作が遅くなります。