C ++和Java中的字符串连接复杂性
考虑这段代码：
public String joinWords(String[] words) { String sentence = ""; for(String w : words) { sentence = sentence + w; } return sentence; } 在每个连接上创建字符串的新副本，以便总体复杂度为O(n^2) 。 幸运的是，在Java中，我们可以使用StringBuffer来解决这个问题，每个附加都有O(1)复杂度，然后总体复杂度为O(n) 。
在C ++中， std::string::append()具有O(n)的复杂性，我不清楚stringstream的复杂性。
在C ++中， StringBuffer方法是否具有相同的复杂性？
C ++字符串是可变的，并且几乎与StringBuffer一样动态可变。 与Java中的等价物不同，此代码每次都不会创建新的字符串; 它只是附加到当前的一个。
std::string joinWords(std::vector const &words) { std::string result; for (auto &word : words) { result += word; } return result; }
如果您预先reserve所需的尺寸，则会以线性时间运行。 问题是，循环向量以获取大小是否比让字符串自动resize要慢。 那个，我不能告诉你。 时间吧。 🙂
如果由于某种原因你不想使用std::string本身（你应该考虑它;它是一个非常值得尊敬的类），C ++也有字符串流。
#include ... std::string joinWords(std::vector const &words) { std::ostringstream oss; for (auto &word : words) { oss << word; } return oss.str(); }
它可能不比使用std::string更有效，但在其他情况下它更灵活一点 - 你可以用它来串行化任何基本类型，以及任何指定了operator <<(ostream&, its_type&)类型operator <<(ostream&, its_type&)覆盖。
这与您的问题有些相关，但仍然相关。 （而且评论太大了！）
在每个连接上创建字符串的新副本，以便总体复杂度为O（n ^ 2）。
在Java中， s1.concat(s2)或s1 + s2的复杂度为O(M1 + M2) ，其中M1和M2是各自的字符串长度。 将其转化为一系列连接的复杂性通常是困难的。 但是，如果假设N串联长度为M的字符串，那么复杂度确实是O(M * N ^ 2) ，它与您在问题中所说的相匹配。
幸运的是，在Java中，我们可以使用
StringBuffer来解决这个问题，每个附加都有O(1)复杂度，然后总体复杂度为O(n)。
在StringBuilder情况下，对于大小为M字符串， N调用sb.append(s)的分摊复杂度为O(M*N) 。 这里的关键词是摊销 。 将字符追加到StringBuilder ，实现可能需要扩展其内部数组。 但扩展策略是将arrays的大小加倍。 如果你进行数学计算，你会发现缓冲区中的每个字符平均会在整个append调用序列中被复制一次。 所以整个序列仍然可以作为O(M*N) ……并且，当它发生时， M*N是总的字符串长度。
所以你的最终结果是正确的，但你关于单个append调用的复杂性的陈述是不正确的。 （我明白你的意思，但你说它的方式是不正确的。）
最后，我要注意在Java中你应该使用StringBuilder而不是StringBuffer除非你需要缓冲区是线程安全的。
作为在C ++ 11中具有O(n)复杂度的非常简单的结构的示例：
template struct StringAppender { std::vector> buff; StringAppender& operator+=( std::basic_string v ) { buff.push_back(std::move(v)); return *this; } explicit operator std::basic_string () { std::basic_string retval; std::size_t total = 0; for( auto&& s:buff ) total+=s.size(); retval.reserve(total+1); for( auto&& s:buff ) retval += std::move(s); return retval; } };
使用：
StringAppender append; append += s1; append += s2; std::string s3 = append;
这需要O（n），其中n是字符数。
最后，如果您知道所有字符串的长度，只需要有足够空间的reserve使得append或+=总共花费O（n）时间。 但我同意这很尴尬。
使用std::move与上面的StringAppender （即sa += std::move(s1) ）将显着提高非短字符串的性能（或使用xvalues等）
我不知道std::ostringstream的复杂性，但是ostringstream用于漂亮的打印格式化输出，或者高性能并不重要的情况。 我的意思是，它们并不坏，甚至可以执行脚本/解释/字节码语言，但如果你匆忙，你还需要别的东西。
像往常一样，您需要分析，因为恒定因素很重要。
rvalue-reference-to-this operator +也可能是一个好的，但是很少有编译器实现rvalue引用。