C++中字符串拼接的开销

Question

C++中字符串拼接的开销

4

我正在从ifstream读取随机ascii文本文件。我需要将整个消息放入字符串类型以进行字符解析。我目前的解决方案有效，但我认为在处理更长的文件时会浪费过多的处理时间，因为我使用了类似于以下内容的等效内容：

std::string result;

for (std::string line; std::getline(std::cin, line); )
{
    result += line;
}

我担心像这样连接字符串所带来的开销（这会发生几千次，每个消息长达数万个字符）。我花了几天时间浏览不同的潜在解决方案，但仍然没有找到完全适合的...我不知道消息的长度，因此我认为使用动态大小的字符数组不是我的答案。

我阅读了这个SO线程，它听起来几乎适用，但仍让我感到不确定；

有什么建议吗？

- Jeremy

1

这是一个真正的问题吗？ - mfontanini

3

@mfontanini说：不，他只是为了好玩而凭空编造的。和你我一样，没有更好的事情可做。 - Lightness Races in Orbit

3

ifstream 意味着一个文件，文件意味着你可以 stat，你可以 stat 意味着你知道它的大小；我是否漏掉了什么？ - Alex Chamberlain

@LightnessRacesinOrbit - 嗯，他可能会成为第一个解析15GB文件的人。而且考虑到他正在逐行阅读整个文件并进行字符串连接（同样是那个15GB的字符串）- 而且他不是逐行解析。 - dtech

1

好的，所以如果他不知道尺寸，也不想连接，为什么不直接逐行解析呢？在我看来，连接并不是一个太大的问题。 - dtech

显示剩余7条评论

4个回答

0

你正在为文件中的每一行复制结果数组（因为你在扩展结果）。相反，预先分配结果并呈指数增长。

std::string result;
result.reserve(1024); // pre-allocate a typical size

for (std::string line; std::getline(std::cin, line); )
{
    // every time we run out of space, double the available space
    while(result.capacity() < result.length() + line.length())
        result.reserve(result.capacity() * 2);

    result += line;
}

- Aaron

0

如果您知道文件大小，可以使用结果的成员函数'reserve()'一次。

- dan

知道文件的大小并不等同于知道他感兴趣阅读内容的长度。 - user334856

@Sancho：没错。然而，后者才是有用的。如果文件大小为600MB，而您的消息长度只有1MB，那么保留整个文件大小就相当愚蠢了。 - Lightness Races in Orbit

@LightnessRacesinOrbit - “相当愚蠢”，“相当短视”...你是在居高临下吗？OP似乎不知道自己想做什么，而你却提出了一些惊人的场景来展示某种优越感...不酷😉 - dtech

@ddriver：*耸肩*我只是说出我所看到的。保留600倍于你所需内存确实是“相当愚蠢”的，而你在对OP能够做什么和不能做什么方面的假设上确实是“相当短视”的。我成功地解析了要求，并且我的解释得到了确认。 - Lightness Races in Orbit

@LightnessRacesinOrbit - 哦，是的，我们知道，你很厉害 ;) 真遗憾他没有确认那个 15 GB 的输入文件，那将是一场真正的大爆炸。 - dtech

哇，一个不明确的问题能引发这么多争论！@LightnessRacesinOrbit- 我同意，只要存在一个相当聪明的解决方案，预留内存就是“相当愚蠢”的。 - dan

0

我现在太困了，无法为您提供任何实际数据，但是，最终，如果事先不知道大小，您总是需要做类似于这样的某些事情。事实上，您的标准库实现足够聪明，可以相当智能地处理字符串调整大小。（尽管对于std::string，没有像std::vector那样的指数增长保证。）

因此，尽管您可能会在前五十次迭代中看到不必要的重新分配，但是经过一段时间后，重新分配的块变得非常大，重新分配变得很少。

如果您进行分析并发现这仍然是瓶颈，也许可以使用std::string::reserve和典型数量自己进行预留。

- Lightness Races in Orbit

2

参考局部性意味着列表几乎从来没有用处；绳索可能有意义，但我严重怀疑性能问题是由于内存分配引起的... - Alex Chamberlain

@AlexChamberlain：好吧，接下来的复制也不会有所帮助。 - Lightness Races in Orbit

关于复杂度 - cppreference 说带有范围的字符串构造函数具有线性复杂度，但我在标准中没有看到确认（尽管对于向量它提供了）。有趣的是，这是cppreference的错误吗？ - Evgeny Panasyuk

@EvgenyPanasyuk：表99，第5行。我发现容器要求的布局最不够优化。 - Lightness Races in Orbit

1

@LightnessRacesinOrbit，嗯，我看到了这一行 :) 它不是看起来那样 - X(t, m)。m 是分配器，而不是迭代器。 - Evgeny Panasyuk

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Qortex · Accepted Answer

问题在于你事先并不知道完整的大小，因此无法适当地分配内存。我认为你所遇到的性能问题与此有关，而不是与 string 的连接方式有关，因为它在标准库中已经被有效地处理了。

因此，我建议在你知道最终 string 的完整大小之前推迟连接操作。也就是说，你可以像下面这样，首先将所有字符串存储在一个大的 vector 中：

using namespace std;
vector<string> allLines;
size_t totalSize = 0;
// If you can have access to the total size of the data you want
// to read (size of the input file, ...) then just initialize totalSize
// and use only the second code snippet below.
for (string line; getline(cin, line); )
{
    allLines.push_back(line);
    totalSize += line.size();
}

然后，你可以预先知道其大小并创建你的大型字符串：string。

string finalString;
finalString.reserve(totalSize);
for (vector<string>::iterator itS = allLines.begin(); itS != allLines.end(); ++itS)
{
    finalString += *itS;
}

虽然我应该提到，只有在遇到性能问题时才需要这样做。不要试图优化不需要优化的东西，否则你将会使你的程序变得复杂而没有明显的好处。需要优化的地方通常是违反直觉的，并且可能因环境而异。因此，只有在分析工具告诉你需要这样做时才这样做。