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

原文由 ethanjyx 发布，翻译遵循 CC BY-SA 4.0 许可协议

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();
}

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

原文由 cHao 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

作为一个非常简单的结构示例，在 C++11 中具有 O(n) 复杂性：

 template<typename TChar>
struct StringAppender {
  std::vector<std::basic_string<TChar>> buff;
  StringAppender& operator+=( std::basic_string<TChar> v ) {
    buff.push_back(std::move(v));
    return *this;
  }
  explicit operator std::basic_string<TChar>() {
    std::basic_string<TChar> 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<char> append;
append += s1;
append += s2;
std::string s3 = append;

这需要 O(n)，其中 n 是字符数。

最后，如果你知道所有的字符串有多长，只要做一个 reserve 有足够的空间就可以 append 或 += 总共需要 O(n)时间。但我同意这很尴尬。

使用 std::move 与上述 StringAppender （即 sa += std::move(s1) ）将显着提高非短字符串的性能（或将其与 xvalue 等一起使用）

我不知道 std::ostringstream 的复杂性，但是 ostringstream 用于漂亮的打印格式输出，或者高性能不重要的情况。我的意思是，它们还不错，它们甚至可以执行脚本/解释/字节码语言，但是如果您赶时间，则需要其他东西。

像往常一样，您需要进行分析，因为恒定因素很重要。

一个 rvalue-reference-to-this operator+ 可能也是一个不错的选择，但很少有编译器实现对 this 的 rvalue 引用。

原文由 Yakk - Adam Nevraumont 发布，翻译遵循 CC BY-SA 3.0 许可协议