35

考虑这段代码：

public String joinWords(String[] words) {
    String sentence = "";
    for(String w : words) {
        sentence = sentence + w;
    }
    return sentence;
}

在每次串联时，都会创建一个新的字符串副本，因此总体复杂度为O(n^2). 幸运的是，在 Java 中，我们可以用 a 来解决这个问题StringBuffer，它对每个追加都有O(1)复杂性，那么整体复杂性将是O(n)。

虽然在 C++ 中，std::string::append()具有 的复杂性O(n)，但我不清楚stringstream.

在 C++ 中，是否有类似StringBuffer复杂度相同的方法？

4

3 回答 3

33

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&)覆盖的类型进行字符串化。

于 2013-03-14T03:43:41.367 回答
17

这与您的问题有些相切，但仍然相关。（评论太大了！！）

在每次串联时，都会创建一个新的字符串副本，因此总体复杂度为 O(n^2)。

s1.concat(s2)在 Java 中， ors1 + s2的复杂性在O(M1 + M2)哪里M1，M2是各自的字符串长度。一般来说，将其转化为串联序列的复杂性是很困难的。但是，如果您假设N长度为 Strings 的串联M，那么复杂性确实O(M * N * N)与您在问题中所说的相匹配。

幸运的是，在 Java 中，我们可以用 a 来解决这个问题StringBuffer，它对每个追加都有O(1)复杂性，那么整体复杂性将是O(n)。

在这种StringBuilder情况下，对大小字符串的调用的摊销复杂度为. 这里的关键词是摊销。当您将字符附加到 a时，实现可能需要扩展其内部数组。但是扩展策略是将数组的大小加倍。如果您进行数学计算，您会发现缓冲区中的每个字符在整个调用序列中平均将被复制一次。所以整个序列仍然可以计算为......并且，碰巧是总字符串长度。Nsb.append(s)M O(M*N)StringBuilderappendO(M*N)M*N

所以你的最终结果是正确的，但是你关于单个调用复杂性的陈述append是不正确的。（我明白你的意思，但你说的方式表面上不正确。）

最后，我注意到在 Java 中你应该使用StringBuilder而不是StringBuffer除非你需要缓冲区是线程安全的。

于 2013-03-14T04:20:02.793 回答
2

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

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有足够空间的情况下执行 a 就可以append或+=总共花费 O(n) 时间。但我同意这很尴尬。

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

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

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

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

于 2013-03-14T03:32:14.953 回答