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

Question

这个问题在这里已经有了答案:

C++ equivalent of StringBuffer/StringBuilder? (10 个回答)

关闭 9年前。

考虑这段代码:

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)，我不清楚 的复杂度>字符串流.

在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，这将在线性时间内运行您事先需要的尺寸。问题是遍历 vector 以获取大小是否比让字符串自动调整大小要慢。那，我不能告诉你。计时。 :)

如果您不想使用 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&) 的类型进行字符串化。覆盖。