3

似乎 std::string - 因为它不使用表达式模板 - 对于连接等某些操作具有 O(n^2) 复杂性而不是可能的 O(n) 复杂性。当您必须插入许多元素时，与 std::stringstream 类相同。

我想了解这一点，至少如果有人可以就这一点有一些很好的链接，那就太好了。

4

4 回答 4

3

将多个字符串连接在一起在 C++ 中具有不同的复杂性，具体取决于它是如何完成的。我相信您正在考虑的情况是：

string result = string("Hello, ") + username + "! " +
                "Welcome to " + software_product + ".";

它连接了 6 个字符串。第一个字符串被复制 5 次，第二个字符串被复制 4 次，以此类推。正如Leonid Volnitsky在他的回答中指出的那样，这个 Θ(NM) 的确切界限，其中 M 是连接操作的数量，N 是被连接的字符串的总长度。当 M <= N 时，我们也可以称之为 O(N^2)。请注意，不能保证 M <= N，因为您可以通过尝试连接空字符串来增加 M 而不会增加 N。

表达式模板可以帮助加速这个用例，尽管它会导致C++11 中的类型推断auto和decltypeC++98 中的模板类型推断出现问题。所有这些都会推断出的类型

auto result = string("Hello, ") + username + "! " +
              "Welcome to " + software_product + ".";

是用于使表达式模板魔术发生的惰性求值字符串模板类型。表达式模板不是一个好主意的其他原因包括Leonid Volnitsky关于减慢编译时间的回答。它可能还会增加已编译二进制文件的大小。

相反，C++ 中还有其他解决方案可用于获得 Θ(N) 连接：

string result = "Hello, ";
result += username;
result += "! ";
result += "Welcome to ";
result += software_product;
result += ".";

在这个版本中，字符串被原地修改，虽然已经复制到的数据result有时需要重新复制，但 C++ 字符串通常实现为动态数组，以指数方式分配新空间，因此每个新字符的插入都会分期恒定时间，导致重复连接的整体 Θ(N) 行为。

以下是做同样事情的一种方式，几乎在一条线上。它在内部使用相同的原理，但也支持使用 << 重载将非字符串类型转换为字符串。

stringstream result;
result << "Hello, " << username << "! " << "Welcome to " << software_product
       << ".";
// do something with result.str()

最后，C++ 标准库不包含此功能，但可以定义以下函数，其中包含一些字符串流魔术。该实现留给读者作为练习。

template <typename... Items>
std::string concat(std::string const& a, std::string const& b, Items&&... args)

然后，您可以concat在 O(N) 时间内在一行上调用重复连接：

string result = concat("Hello, ", username, "! ", "Welcome to ",
                       software_product, ".");

据推测，所有这些都是比通过创建表达式模板类型来搞乱类型推断更好的解决方案。

于 2012-12-23T14:30:29.397 回答
2

如果我们有字符串表达式的总长度N和M连接操作，那么复杂度应该是O(NM)。

使用表达式模板可以加快速度。可能因为它们的复杂性，它没有完成。编译速度也会更慢——它需要 M 递归类型。

于 2012-12-23T13:32:54.623 回答
1

我很难相信串联会上升到O(n^2)，但这里有一些与您的问题相关的答案：

C++ 标准没有指定实现细节，仅在某些情况下指定了复杂性要求。std::string 操作的唯一复杂性要求是 size()、max_size()、operator[]、swap()、c_str() 和 data() 都是常数时间。其他任何事情的复杂性取决于实现您正在使用的库的人所做的选择。

参见参考：C++ string::find complex

于 2012-12-23T11:54:05.620 回答
1

怎么可能是 O(N^2)？字符串连接是：

  • 必要时重新分配（恒定摊销时间）；
  • 找到第一个字符串的结尾（恒定时间，因为它们是计数字符串）；
  • 从第二个字符串 (O(N)) 复制字符。

我看不出模板与此有什么关系。

于 2012-12-23T12:11:07.130 回答