3

std::string は、式テンプレートを使用しないため、連結などの一部の操作では、おそらく O(n) の複雑さではなく、O(n^2) の複雑さを持っているようです。多くの要素を挿入する必要がある場合は、 std::stringstream クラスでも同じです。

少なくとも誰かがこの点についていくつかの良いリンクを持っていれば、それは素晴らしいことです。

4

4 に答える 4

3

C++ では、複数の文字列を連結する方法によって複雑さが異なります。あなたが考えている状況は次のとおりだと思います。

string result = string("Hello, ") + username + "! " +
                "Welcome to " + software_product + ".";

6 つの文字列を連結します。最初の文字列は 5 回コピーされ、2 番目の文字列は 4 回コピーされます。Leonid Volnitskyが彼の回答で指摘しているように、この Θ(NM) の正確な境界です。ここで、M は連結操作の数、N は連結される文字列の全長です。M <= N の場合、これを O(N^2) と呼ぶこともできます。空の文字列を連結しようとすることで、N を増やさずに M を増やすことができるため、M <= N であるとは限りません。

式テンプレートを使用すると、このユース ケースを高速化できますが、C++11 での型推論autoやdecltype、C++98 でのテンプレート型推論で問題が発生する可能性があります。これらはすべて、次のタイプを推測します。

auto result = string("Hello, ") + username + "! " +
              "Welcome to " + software_product + ".";

式テンプレートの魔法を実現するために使用された、遅延評価された文字列テンプレート型になります。式テンプレートが優れたアイデアではないその他の理由には、このコンパイル時間の遅延に関するLeonid Volnitskyの回答が含まれます。おそらく、コンパイルされたバイナリのサイズも増加します。

代わりに、C++ には、Θ(N) 連結を取得するために使用できる他のソリューションがあります。

string result = "Hello, ";
result += username;
result += "! ";
result += "Welcome to ";
result += software_product;
result += ".";

このバージョンでは、文字列はその場で変更され、すでにコピーされているデータを再コピーするresult必要がある場合もありますが、C++ 文字列は通常、新しいスペースを指数関数的に割り当てる動的配列として実装されるため、新しい文字の挿入ごとに償却されます。一定の時間であり、繰り返される連結の全体的な Θ(N) の動作につながります。

以下は、ほぼ 1 行で同じことを行う方法です。内部で同じ原則を使用しますが、<< オーバーロードを使用して文字列以外の型を文字列に変換することもサポートしています。

stringstream result;
result << "Hello, " << username << "! " << "Welcome to " << software_product
       << ".";
// do something with result.str()

最後に、C++ 標準ライブラリにはこれが含まれていませんが、内部に stringstream マジックを使用して次の関数を定義できます。実装は、読者の課題として残されています。

template <typename... Items>
std::string concat(std::string const& a, std::string const& b, Items&&... args)

concat次に、O(N) 時間で 1 行に繰り返し連結を呼び出すことができます。

string result = concat("Hello, ", username, "! ", "Welcome to ",
                       software_product, ".");

おそらく、これらはすべて、式テンプレート型を作成して型推論を台無しにするよりも優れたソリューションです。

于 2012-12-23T14:30:29.397 に答える
2

文字列式の全長NとM連結操作がある場合、複雑さは になりますO(NM)。

式テンプレートを使用して高速化することは間違いなく可能です。おそらくそれらの複雑さのために、それは行われませんでした。コンパイル速度も遅くなります - M 再帰型が必要になります。

于 2012-12-23T13:32:54.623 に答える