c++ - ベクトルの途中で要素を追加または削除するのが遅いのはなぜですか?

Question

Accelerated C++ によると:

この戦略を使用するには、ベクターから要素を削除する方法が必要です。良いニュースは、そのような施設が存在することです。悪いニュースは、ベクトルから要素を削除すると、大量の入力データに対してこのアプローチを使用することに反対するほど遅いことです。処理するデータが非常に大きくなると、パフォーマンスが驚くほど低下します。

たとえば、すべての生徒が失敗した場合、これから表示される関数の実行時間は、生徒数の 2 乗に比例して増加します。つまり、100 人の学生のクラスの場合、プログラムの実行には、1 人の学生の場合の 10,000 倍の時間がかかることになります。問題は、入力レコードが高速ランダム アクセス用に最適化されたベクトルに格納されていることです。その最適化の代償の 1 つは、ベクターの末尾以外の要素を挿入または削除するとコストがかかる可能性があることです。

著者は、ベクトルが 10,000 人以上の学生にとって非常に遅い理由と、ベクトルの途中で要素を追加または削除するのが一般的に遅い理由を説明していません。Stack Overflowの誰かが私に美しい答えを出してくれませんか?

Answer 1

すべての要素の途中に要素を挿入または削除する場合はstd::vector<T>、変更点の後にすべての要素を移動する必要があります。挿入する場合は、それらをさらに奥に移動する必要があり、削除する場合は、ギャップを閉じるために前方に移動する必要があります。背景は、std::vector<T>基本的に要素の連続したシーケンスであるということです。

この操作は特定のタイプではそれほど悪くはありませんが、比較的遅くなる可能性があります。ただし、コンテナーのサイズはある程度適切なサイズにするか、移動のコストを大きくする必要があることに注意してください。小さなベクトルの場合、中間への挿入/中間からの削除は、リストなどの他のデータ構造を使用するよりもおそらく高速です。ただし、最終的には、より複雑な構造を維持するコストが報われます。

Answer 2

std::vector はメモリを 1 つのエクステントとして割り当てます。拡張の途中に要素を挿入する必要がある場合は、ベクターのすべての要素を右にシフトして、新しい要素を挿入する空きスロットを作成する必要があります。さらに、エクステントがすでに要素でいっぱいの場合、ベクトルは新しい大きなエクステントを割り当て、すべての要素を元のエクステントから新しいエクステントにコピーする必要があります。