22

標準が連続していると定義しているという事実に加えて、なぜ std::vector が連続しているのでしょうか?

スペースが不足している場合は、続行する前に、新しいブロックを再割り当てし、古い​​ブロックを新しいブロックにコピーする必要があります。

隣接していなかったら？ストレージがいっぱいになると、新しいブロックが割り当てられ、古いブロックが保持されます。イテレータを介してアクセスする場合、単純な >, < チェックを実行して、インデックスがどのブロックにあるかを確認し、それを返します。この方法では、スペースがなくなるたびに配列をコピーする必要はありません。

これは本当にうまくいきますか？または私は何かが欠けていますか？

4

5 に答える 5

27

連続性が保証されない場合std::vectorは、新しいコンテナが発明されます。

連続性の保証により、連続した配列を期待する既存のコードとの相互運用が容易になります。また、キャッシュに適しているため、非常に優れたパフォーマンスが得られます。(このため、中間での挿入/削除は実際には中程度のサイズでは非常に高速です。)

展開時に配列をコピーするのは驚くほど安価です。一度に 100 万個の要素をベクトルに追加すると、各要素は平均して約 1 回コピーされます。

于 2013-11-09T12:48:43.103 に答える
11

これにはいくつかの理由があります。

まず、連続したコンテナーに対する反復は、2 つの要因により、連続していないコンテナーよりもはるかに高速です。1 つ目は分岐予測です。コンテナ、およびパイプラインのリセットが少ないということは、コードが高速であることを意味します。2 つ目は、メモリの連続したブロックを完全にキャッシュする方が、さまざまな小さなブロックをまとめてキャッシュするよりもはるかに簡単であり、配列全体がキャッシュされる可能性がはるかに高くなることです。

第 2 に、C コードとやり取りする必要のある C++ コードが大量に書き込まれています。そのコードの多くは、配列/バッファーを受け取るときに連続したメモリ空間を期待します。これは、データ構造の実装に依存しない方法であるためです。それをするために。バッファ/配列を常に期待するコードと対話している場合、配列への変換のオーバーヘッドはstd::deque、配列への事実上瞬時の通過と比較して、その犠牲にstd::vectorなります(基本的には、内部配列へのポインタを与えるだけです)。 .

これらすべてが、連続したコンテナの存在を正当化します。他の人が言ったように、高速な反復やメモリの連続性が必要ない場合は、いつでもstd::deque.

于 2013-11-09T15:12:28.547 に答える
9

連続させるstd::vectorことで、配列のように扱うことができます。ただし、サイズ変更も可能です。そのサイズは、コンパイル時ではなく実行時に定義できます。また、ベクトルを使用して、バッファを必要とする関数にメモリを割り当てることもできます。これの利点は、メモリがvector範囲外になると解放されることです。たとえばReadFile、ベクターを使用する場合は、バッファーを作成するために使用できます。

unsigned int bytesRead = 0;
std::vector<char> buffer(fileSize);
// open file, etc.
ReadFile(hFileIn, buffer.data(), buffer.size(), &bytesRead, nullptr);

dataC++11 の新機能であることに注意してください。古いコードでは、最初の要素のアドレスを返す同等の&(buffer.at(0))orがおそらく見られるでしょう。&(buffer[0])

Astd::dequeは、あなたが説明しているものにより適しています。

于 2013-11-09T12:48:32.670 に答える
3

他の回答を補完するものとして (それらは非常に完全です)、ベクターが連続しないことを好む状況が 1 つあります。それは、ベクターのサイズを同時に変更する必要がある場合です。これが、Intel Thread Building Block が tbb::concurrent_vector を提供する理由です。

「ストレージがいっぱいになると、新しいブロックを割り当てて古いブロックを保持します。イテレータを介してアクセスすると、単純な>、<チェックを実行して、インデックスがどのブロックにあるかを確認し、それを返します。」

次に、tbb::concurrent_vector と std::vector を比較すると、連続したメモリの利点 (速度) と欠点 (std::vector を同時に拡張できない) をよりよく理解できます。私は tbb::concurrent_vector が std::deque よりも最適化されることを期待しています。そのため、tbb::concurrent_vector と std::vector の比較がより公正な比較となります。

于 2013-11-09T16:28:39.860 に答える