1

C++ 標準std:stringでは、指数関数的な成長ポリシーに従っているため、capacity()連結中の文字列は必要に応じて常に増加すると思います。ただし、テストtest.cppしたところ、for ループでは、代入中に2 回ごとcapacity()に縮小されることがわかりました。length()

この動作が文字列の長さに依存するのではなく、文字列を変更する頻度に依存するのはなぜですか? ある種の最適化ですか？

次のコードは でテストされていg++ -std=c++11ます。

test.cpp: 

#include <iostream>  
int main(int argc, char **argv) {
  std::string s = "";
  for (int i = 1; i <= 1000; i++) {
    //s += "*";
    s = s + "*";
    std::cout << s.length() << " " << s.capacity() << std::endl;
  }
  return 0;
}

出力は次のようになります。 

1 1
2 2
3 4
4 4
5 8
6 6    // why is capacity shrunk?
7 12
8 8    // and again?
9 16
10 10  // and again?
11 20
12 12  // and again?
13 24
14 14  // and again?
15 28
16 16  // and again?
17 32
...
996 996
997 1992
998 998  // and again?
999 1996
1000 1000  // and again?
4

2 に答える 2

1

これを行う場合:

s = s + "*";

"*"コンテンツの最後に連結された新しい一時文字列を作成し、sその新しい文字列を にコピー割り当てしますs。

+縮小しているのは ではなく、=です。ある文字列から別の文字列にコピー割り当てする場合、容量をコピーする理由はなく、実際に使用されているバイトだけです。

コメントアウトされたコードはこれを行います：

s += "*";

…"*"の末尾に追加するという1 つのことだけを行っていsます。したがって、「最適化」が発生する場所はありません (発生した場合、指数関数的成長の目的全体を無効にする悲観化になります)。

于 2014-06-25T03:09:43.387 に答える
1

文字列が移動されたり、割り当てられたりしたときに何が起こるかは、実際には C++ 標準では規定されていませんcapacity()。これは欠陥である可能性があります。唯一の制約は、操作に指定された時間計算量から導き出されるものです。

ベクトルに関する同様の議論については、こちらを参照してください。

于 2014-06-25T03:30:50.713 に答える