2

ベクトルとリストの一般的な操作の複雑さに関する違いを理解しています。しかし、非常に大きなリストまたはベクトル (つまり、数百万の要素) を処理する必要があると仮定すると、ベクトルを操作するときにメモリ割り当てが失敗する可能性が高いと言えますか?

私の知る限り、ベクトルを操作する場合、要素は連続して保存されます。これは、すべての要素を格納するために大きなメモリ ブロックを割り当てる必要があることを意味します。これは、断片化されたヒープの場合に失敗する可能性が高くなります。

一方、リストを操作する場合、メモリの大きなブロックは割り当てられません。要素は連続して格納されません。

4

2 に答える 2

3

std::listがよりも機能し続ける可能性が高いシナリオが確実に存在しstd::vectorます。最も単純な方法は、アプリケーションで大量のメモリの断片化が発生している場合です。基本的に、割り当てが仮想メモリアドレス空間に分散されている場合。これにより、使用可能なメモリ量と連続するメモリの最大ブロックとの間に大きなギャップが生じます。このシナリオでは、大量の要素を持つ は、同じ量の要素を持つstd::vectorよりも失敗する可能性が高くなります。std::list

しかし、これは私がやみくもに決定を下すものではありません。問題のアプリケーションがメモリの断片化に悩まされていて、 を使用する能力に影響を与えていた場合は、std::vectorにジャンプすることを検討しstd::listます。しかし、最初は、自分のニーズに最も適していると感じたコレクションを選びました。

于 2013-04-02T19:09:44.957 に答える
3

この比較は、2 つのコンテナが要素ごとに異なるメモリ要件を持っていることに言及せずに不完全です。

  • 平均して、サイズのベクトルにはバイトがN必要N*sizeof(T)です (サイズを正確に取得するには、メモリをトリミングする必要がある場合がありますN) 。
  • サイズのリストにはバイトNが必要です。N*(sizeof(T)+2*sizeof(void*))

リストの各要素には 2 つの追加のポインタがあるため、非常に小さなオブジェクト ( ints など) のリストには、同じサイズのベクトルに必要なメモリ量の 3 倍から 5 倍が必要になる場合があります。リスト要素のサイズが大きくなると、追加のメモリ要件はそれほど顕著ではなくなりますが、小さなオブジェクトの場合、その影響は非常に大きくなります。そのため、ベクトルがメモリ割り当てで失敗する可能性が高いと言うのは公平ではありません: ベクトルはメモリの連続したブロックを必要としますが、合計量ははるかに小さい可能性があり、潜在的な失敗の領域。

2 つのポインターよりも大幅に (たとえば、10 倍以上) サイズのオブジェクトの場合、追加のメモリ要件を無視しても問題ありません。連続したスペースを割り当てるためにベクトルが必要なため、メモリの適切なチャンクが見つからない可能性が非常に高くなります。 .

于 2013-04-02T19:13:57.703 に答える