c++ - std::string 实现和表达式模板

Question

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

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

Answer 1

将多个字符串连接在一起在 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 和 decltype 类型推断以及模板类型出现问题C++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++ 字符串通常实现为 dynamic arrays以指数方式分配新空间，因此每个新字符的插入都需要摊销常数时间，从而导致重复连接的整体 Θ(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, ".");

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