117

std::string の "+" 演算子と、連結を高速化するためのさまざまな回避策について心配している人が何人かいると聞きました。これらのうち、本当に必要なものはありますか? もしそうなら、C++ で文字列を連結する最良の方法は何ですか?

4

13 に答える 13

92

本当に効率が必要な場合を除き、余分な作業はおそらく価値がありません。 代わりに演算子 += を使用するだけで、おそらく効率が大幅に向上します。

その免責事項の後、私はあなたの実際の質問に答えます...

STL 文字列クラスの効率は、使用している STL の実装によって異なります。

C組み込み関数を介して手動で連結を行うことにより 、効率を保証し、より細かく制御できます。

operator+ が効率的でない理由:

このインターフェースを見てください：

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

各 + の後に新しいオブジェクトが返されることがわかります。つまり、毎回新しいバッファが使用されます。大量の余分な + 操作を行っている場合、効率的ではありません。

より効率的にできる理由:

  • デリゲートがあなたのために効率的にそれを行うことを信頼するのではなく、効率を保証しています
  • std::string クラスは、文字列の最大サイズや、文字列に連結する頻度について何も知りません。あなたはこの知識を持っている可能性があり、この情報に基づいて物事を行うことができます. これにより、再割り当てが少なくなります。
  • バッファーを手動で制御するので、文字列全体を新しいバッファーにコピーしたくない場合は、コピーしないようにすることができます。
  • はるかに効率的なヒープの代わりにスタックをバッファーに使用できます。
  • string + 演算子は、新しい文字列オブジェクトを作成して返すため、新しいバッファを使用します。

実装に関する考慮事項:

  • 文字列の長さを追跡します。
  • 文字列の末尾と先頭、または単に先頭へのポインターを保持し、先頭 + 長さをオフセットとして使用して、文字列の末尾を見つけます。
  • 文字列を保存するバッファが十分に大きいことを確認して、データを再割り当てする必要がないようにしてください
  • strcat の代わりに strcpy を使用すると、文字列の長さを繰り返し処理して文字列の末尾を見つける必要がなくなります。

ロープのデータ構造:

非常に高速な連結が必要な場合は、ロープ データ構造の使用を検討してください。

于 2009-03-04T16:14:01.940 に答える
19

私はそれについて心配しません。ループで行う場合、文字列は常にメモリを事前に割り当てて再割り当てを最小限に抑えます-operator+=その場合にのみ使用してください。そして、手動で行う場合、このようなものまたはそれ以上

a + " : " + c

次に、コンパイラがいくつかの戻り値のコピーを削除できたとしても、一時的なものを作成しています。これは、連続して呼び出された場合、参照パラメーターが名前付きオブジェクトを参照するのか、サブ呼び出しoperator+から返された一時オブジェクトを参照するのかがわからないためです。operator+最初にプロファイルを作成しない前に、私はむしろそれについて心配したくありません. しかし、それを示す例を見てみましょう。バインディングを明確にするために、最初に括弧を導入します。わかりやすくするために、関数宣言の直後に引数を配置します。その下に、結果の式が何であるかを示します。

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

さて、その追加でtmp1は、表示された引数を使用して operator+ への最初の呼び出しによって返されたものです。コンパイラは非常に賢く、戻り値のコピーを最適化すると仮定します。したがって、 と の連結を含む 1 つの新しい文字列にaなり" : "ます。今、これが起こります：

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

それを次のものと比較してください。

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

一時的な文字列と名前付き文字列に同じ関数を使用しています! したがって、コンパイラは引数を新しい文字列にコピーし、それに追加して、の本体から返す必要がありoperator+ます。一時的なメモリを取得してそれに追加することはできません。式が大きくなればなるほど、文字列のコピーをより多く行う必要があります。

次の Visual Studio と GCC は、実験的な追加として、 c++1x の移動セマンティクス(コピー セマンティクスを補完する) と右辺値参照をサポートします。これにより、パラメーターが一時的なものを参照しているかどうかを判断できます。これにより、上記のすべてがコピーなしで 1 つの「追加パイプライン」になるため、このような追加が驚くほど高速になります。

それがボトルネックであることが判明した場合でも、引き続き行うことができます

 std::string(a).append(" : ").append(c) ...

append呼び出しは引数を追加し、それ*this自体への参照を返します。そのため、一時的なコピーはそこで行われません。あるいは、operator+=を使用することもできますが、優先順位を修正するには醜い括弧が必要です。

于 2009-03-04T16:22:30.733 に答える
10

ほとんどのアプリケーションでは、問題になりません。+ 演算子が正確にどのように機能するかをまったく知らずにコードを書くだけで、それが明らかにボトルネックになった場合にのみ、問題を解決することができます。

于 2009-03-04T16:15:18.613 に答える
7

.NET System.Strings とは異なり、C++ の std::stringsは変更可能であるため、単純な連結によって他の方法と同じくらい高速に構築できます。

于 2009-03-04T16:23:33.447 に答える
6

おそらく std::stringstream 代わりに？

しかし、おそらくそれを保守可能で理解しやすいものに保ち、プロファイルを作成して、本当に問題が発生しているかどうかを確認する必要があるという意見に同意します.

于 2009-03-04T16:16:28.690 に答える
4

インパーフェクト C++で、マシュー ウィルソンは、すべての部分を連結する前に割り当てを 1 つだけにするために、最終的な文字列の長さを事前に計算する動的文字列連結器を提示しています。式テンプレートをいじって、静的連結子を実装することもできます。

この種のアイデアは STLport の std::string 実装に実装されていますが、これは正確なハックのために標準に準拠していません。

于 2009-03-04T17:04:00.807 に答える
2

小さい文字列の場合は問題ありません。大きな文字列がある場合は、それらをそのままベクトルに格納するか、他のコレクションにパーツとして格納することをお勧めします。そして、1 つの大きな文字列ではなく、そのようなデータ セットを処理するようにアルゴリズムを適応させます。

複雑な連結には std::ostringstream を好みます。

于 2009-03-04T16:20:05.967 に答える
2

ほとんどのことと同様に、何かをするよりもしない方が簡単です。

大きな文字列を GUI に出力したい場合、出力先が何であれ、文字列を大きな文字列として処理するよりも、文字列を分割して処理する方が適している可能性があります (たとえば、テキスト エディターでテキストを連結する場合 - 通常、行は別々に保持されます)。構造）。

ファイルに出力する場合は、大きな文字列を作成して出力するのではなく、データをストリーミングします。

遅いコードから不要な連結を削除した場合、連結を高速化する必要があるとは思いませんでした。

于 2009-03-04T16:22:13.090 に答える