パフォーマンス - 文字列コンストラクタを使用し、連結を使用して

Question

私はC++を比較的新しく使用しています。私はコーディングの問題を練習していて、文字列を回文に変換することに関連していました。

Iはベクトルでアルファベットのカウントを記憶し、後でこのようなパリンドロームを生成した -

string palindrome_string; 
for (short i = 0; i < 26; ++i) { 
    alphabet_count[i] /= 2; 
    for (short j = 0; j < alphabet_count[i]; ++j) 
     palindrome_string += string(1, static_cast<char>('a' + i)); 
} 

しかし、特定のテストケース（のみ2.10^5 e S含有入力）のために、プログラムを超えましたメモリの制限は256 MBです。次に、このステートメントで内部ループを置き換えました。

palindrome_string += string(alphabet_count[i], static_cast<char>('a' + i)); 

このプログラムは約2.4 MBしか使用しないで正常に動作しました。

これは、コンカチネーションとコンストラクタ関数を使用した場合のパフォーマンスに関連しているかどうかを確認したい場合は、それが可能な理由は何ですか？そしてthe successful one：the failed one（10テストケース） - それは問題にした場合、それが助け場合

、私はMS VC++ 2010

でプログラムをコンパイルし、ここでの提出（コード）があります。

Answer 1

std::stringは、償却された一定時間を達成する方法でメモリを割り当てる必要があります。 hereと記載されているように、より多くのスペースが必要となるたびに、2倍の単純な実装が可能です。

内側ループのpalindrome_stringに何かを追加するたびに、その文字列がメモリを再割り当てする可能性があります。しかし、私はそれがひどいことがどうなるかは分かりません。つまり、上記の単純な実装で内部ループの繰り返しでメモリが2倍になったとしても、次の繰り返しの多くでスペースを再割り当てする必要はありません。

Answer 2

問題はパフォーマンスではなく、内側のループでした。 jはタイプshortであり、alphabet_count[i]はタイプlongであるため、そのようになっています。