C ++和Java中的字符串连接复杂性 [英] String concatenation complexity in C++ and 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）。

On each concatenation a new copy of the string is created, so that the overall complexity is O(n^2). Fortunately in Java we could solve this with a StringBuffer, which has O(1) complexity for each append, then the overall complexity would be O(n).

在C ++中， std :: string :: append（）的复杂性为 O（n），我不清楚的复杂性stringstream 。

While in C++, std::string::append() has complexity of O(n), and I'm not clear about the complexity of stringstream.

在C ++中，是否存在类似 StringBuffer 中的方法复杂性？

In C++, are there methods like those in StringBuffer with the same complexity?

推荐答案

C ++字符串是可变的，并且几乎与StringBuffer一样动态可变。与Java中的等价物不同，此代码每次都不会创建新的字符串;它只是附加到当前的那个。

C++ strings are mutable, and pretty much as dynamically sizable as a StringBuffer. Unlike its equivalent in Java, this code wouldn't create a new string each time; it just appends to the current one.

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

如果您预留这将以线性时间运行预先需要的尺寸。问题是，循环向量以获取大小是否比让字符串自动调整大小要慢。那个，我不能告诉你。时间吧。 ：）

This runs in linear time if you reserve the size you'll need beforehand. The question is whether looping over the vector to get sizes would be slower than letting the string auto-resize. That, i couldn't tell you. Time it. :)

如果由于某种原因你不想使用 std :: string 本身（你应该考虑它;它是一个非常值得尊敬的类），C ++也有字符串流。

If you don't want to use std::string itself for some reason (and you should consider it; it's a perfectly respectable class), C++ also has string streams.

#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 ，但在其他情况下它更灵活一点 - 您可以使用它来串行化任何基本类型，以及指定运算符的任何类型< <（ostream&，its_type&）覆盖。

It's probably not any more efficient than using std::string, but it's a bit more flexible in other cases -- you can stringify just about any primitive type with it, as well as any type that has specified an operator <<(ostream&, its_type&) override.

这篇关于C ++和Java中的字符串连接复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！