std::string とその自動メモリサイズ変更

Question

私は C++ についてはかなり初心者ですが、std::string クラスのようにメモリをむやみに使用することはできないことはわかっています。例えば：

std::string f = "asdf";
f += "fdsa";

文字列クラスは、大きくなったり小さくなったりするのをどのように処理するのでしょうか?デフォルトの量のメモリが割り当てられ、さらに多くのメモリが必要な場合は、 news はメモリのより大きなブロックであり、そこに自分自身をコピーします。しかし、サイズを変更する必要があるたびに文字列全体をコピーしなければならないのは、かなり非効率ではないでしょうか?それ以外にそれを実現する方法は思いつきません（しかし、明らかに誰かがそれを実行しました）。

さらに言えば、vector、queue、stack などのすべての stdlib クラスは、どのようにして拡大と縮小を透過的に処理するのでしょうか?

Answer 1

通常、2倍のアルゴリズムがあります。言い換えれば、現在のバッファーを埋めると、2倍の大きな新しいバッファーを割り当て、現在のデータをコピーします。これにより、単一の割り当てブロックによる成長の代替手段よりも、操作の割り当て/コピーのコピーが少なくなります。

Answer 2

あなたの分析は正しいです - それは は サイズ変更が必要になるたびに文字列をコピーするのは非効率的です。そのため、一般的なアドバイスではそのパターンの使用を妨げます。文字列を使用します reserve 必要なものに十分なメモリを割り当てるように要求する関数 意図する その中に保管します。その後、さらなる操作によってそのメモリが埋められます。(ただし、ヒントが小さすぎることが判明した場合でも、文字列は自動的に大きくなります。)

また、コンテナは通常、必要以上のメモリを割り当てることで、頻繁な再割り当ての影響を軽減しようとします。一般的なアルゴリズムでは、文字列のスペースが不足していることが判明すると、 ダブルス 新しい値を保持するために必要な最小値を割り当てるだけではなく、バッファ サイズを変更します。文字列が一度に 1 文字ずつ増加する場合、この 2 倍化アルゴリズムにより、時間計算量が (二次時間ではなく) 償却線形時間に軽減されます。また、プログラムのメモリ断片化の影響も軽減します。

Answer 3

STD :: Stringの正確な実装はわかりませんが、動的なメモリの成長を処理する必要があるほとんどのデータ構造は、あなたの言うことを正確に実行することでそうします - デフォルトのメモリを割り当て、より多くが必要な場合はより大きなブロックを作成しますそして、自分自身をコピーします。

明らかな非効率性の問題を回避する方法は、必要以上のメモリを割り当てることです。使用済みメモリの比：ベクトル/文字列/リスト/などの総メモリは、しばしば 負荷率 （わずかに異なる意味のハッシュテーブルにも使用されます）。通常、それは1：2の比率です。つまり、必要なメモリを2倍割り当てます。スペースが足りなくなったら、現在の量の2倍のメモリを割り当てて使用します。これは、時間が経つにつれて、ベクター/文字列/などに物を追加し続ける場合、アイテムをますます少なくコピーする必要があることを意味します（メモリの作成が指数関数的であり、新しいアイテムの挿入はもちろん線形です）。したがって、このメモリ処理方法にかかった時間は、あなたが思うほど大きくありません。の原則によって 償却分析, 、その挿入を見ることができます m この方法を使用してベクトル/文字列/リストへのアイテムは、Mの大部分であり、Mではなく、².