C ++和Java中的字符串连接复杂度

Question

考虑这段代码：

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具有相同的复杂性？

Answer 1

C ++字符串是可变的，几乎与StringBuffer一样可动态调整大小。与Java中的等效语言不同，此代码不会每次都创建一个新字符串。它只是追加到当前的。

std::string joinWords(std::vector<std::string> const &words) {
    std::string result;
    for (auto &word : words) {
        result += word;
    }
    return result;
}

如果您reserve需要预先设置的大小，则会以线性时间运行。问题是，遍历向量以获取大小是否比让字符串自动调整大小要慢。那我不能告诉你。时间。:)

如果std::string由于某种原因不想使用自身（应该考虑；它是一个非常受人尊敬的类），则C ++也具有字符串流。

#include <sstream>
...

std::string joinWords(std::vector<std::string> const &words) {
    std::ostringstream oss;
    for (auto &word : words) {
        oss << word;
    }
    return oss.str();
}

它可能没有比using更加有效std::string，但是在其他情况下则更加灵活-您可以使用它来对任何原始类型以及指定了operator <<(ostream&, its_type&)覆盖的任何类型进行字符串化。