C++中高效的字符串拼接

Question

C++中高效的字符串拼接

c++performancestringconcatenation

130

我听到有一些人对std :: string中的“+”运算符表示担忧，并提出各种加速字符串连接的解决方案。这些方法是否真的必要？如果是，什么是在C ++ 中拼接字符串的最佳方式？

- sneg

17

基本上，“+”不是连接运算符（因为它会生成一个新的字符串）。使用“+=”进行连接。 - Martin York

5

自从 C++11 以来，有一个重要的点：如果将 operator+ 的某个操作数传递为右值引用，则该运算符可以修改其中一个操作数并通过移动其返回它。例如 libstdc++ 中的实现方式。因此，当使用临时对象调用 operator+ 时，它几乎可以达到与其他方式相同的性能 - 这可能是默认情况下选择它的论点，出于可读性的考虑，除非有基准测试表明它是瓶颈。但是，一个标准化的可变参数 append() 不仅最优，而且更加易读... - underscore_d

14个回答

89

在最后预留空间，然后使用带有缓冲区的append方法。例如，假设您期望最终字符串长度为100万个字符：

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

- Carlos A. Ibarra

20

我不会担心这个问题。如果您在循环中执行此操作，则字符串始终会预先分配内存以最小化重新分配 - 只需在这种情况下使用operator+=即可。如果您要手动执行此操作，可以使用类似于以下内容或更长的内容：

a + " : " + c

然后它会创建临时对象 - 即使编译器可以消除一些返回值的复制。这是因为在连续调用 operator+ 中，它不知道引用参数是引用一个命名对象还是从子 operator+ 调用中返回的临时对象。在没有进行分析之前，我宁愿不去担心它。但是让我们通过一个例子来展示。我们首先加入括号以明确绑定。我直接在函数声明后面放置参数，以便更清晰地使用。下面是我展示结果表达式：

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

现在，在这个加法中，tmp1是第一次使用所示参数调用operator+返回的值。我们假设编译器非常聪明，并优化掉了返回值的复制操作。因此，我们最终得到一个新的字符串，其中包含a和" : "的连接。现在，发生了这样的事情：

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

将其与以下内容进行比较：

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

它对于临时字符串和命名字符串都使用相同的函数！因此编译器必须将参数复制到一个新的字符串中，然后附加到该字符串并从operator+的主体中返回它。它无法占用临时内存并在其上附加。表达式越大，就必须完成更多字符串副本。

接下来，Visual Studio和GCC将支持c++1x的移动语义(补充复制语义)和右值引用作为实验性添加。这可以确定参数是否引用临时对象。这将使得这种添加非常快速，因为所有上述操作最终都会在一个“添加管道”中完成而不需要额外复制。

如果发现存在瓶颈，仍然可以执行以下操作

 std::string(a).append(" : ").append(c) ...

append 调用会将其参数附加到 *this 并返回对自身的引用。因此，在这里不会复制临时对象。或者，可以使用 operator+=，但需要使用丑陋的括号来修复优先级。

- litb

1

我必须检查stdlib实现者是否真的这样做。:P libstdc++对于operator+(string const& lhs, string&& rhs)执行return std::move(rhs.insert(0, lhs))。然后，如果两个都是临时对象，它的operator+(string&& lhs, string&& rhs)如果lhs有足够的可用容量，将直接进行append()。我认为这比operator+=慢的风险在于，如果lhs没有足够的容量，则会回退到rhs.insert(0, lhs)，这不仅必须像append()一样扩展缓冲区并添加新内容，还需要向右移动rhs的原始内容。 - underscore_d

1

与 operator+= 相比，另一个开销是 operator+ 仍然必须返回一个值，因此它必须 move() 添加到的任何操作数。不过，我想相比于深度复制整个字符串，这只是一个相当小的开销（复制一些指针/大小），所以很好！ - underscore_d

13

std::string 的 operator+ 每次都会分配一个新的字符串并复制两个操作数字符串。如果重复多次，它会变得很昂贵，时间复杂度为O(n)。

另一方面，std::string 的 append 和 operator+= 在字符串需要增长时每次都会将容量增加50％。这将大大降低内存分配和复制操作的数量，时间复杂度为O(log n)。

- timmerov

1

我不太确定为什么这个被踩了。50%的数字并不是标准要求，但我记得在实践中，这个或100%是常见的增长度量。这个答案中的其他内容似乎都没有问题。 - underscore_d

2

几个月之后，我认为这并不完全准确，因为它是在C++11推出很久之后编写的，并且operator+的重载可以避免分配新的字符串，而是通过将其连接到一个操作数的现有缓冲区来传递一个或两个参数的右值引用（尽管如果容量不足，可能需要重新分配）。 - underscore_d

7

对于大多数应用程序而言，这并不重要。只需编写代码，无需关注+运算符的确切工作方式，只有在它成为明显的瓶颈时才需要自行处理。

- Pesto

11

当然，对于大多数情况来说这是不值得的，但这并没有真正回答他的问题。 - Brian R. Bondy

2

是的，我同意只是说“配置文件然后优化”可以作为对问题的评论 :) - Johannes Schaub - litb

1

很公平，但某些应用程序肯定需要它。所以在这些应用程序中，答案就变成了：“自己动手解决问题”。 - Brian R. Bondy

1

很抱歉这么挑剔。我只是认为需要解释一下为什么operator+不够高效，这样他才能确定在他的情况下是否需要这样做。 - Brian R. Bondy

1

标记为不答案的原因是它没有回答问题。 - Graeme

6

在编程世界中有一个扭曲的概念，认为性能不重要，我们可以忽略整个问题，因为计算机越来越快。但事实是，这并不是人们使用C++编程的原因，也不是他们在stackoverflow上发关于高效字符串拼接的问题的原因。@Pesto - MrFox

7

与.NET System.Strings不同，C++的std::strings是可变的，因此可以通过简单的连接方式构建，与其他方法一样快速。

- James Curran

3

特别是如果在开始之前使用 reserve() 来使缓冲区足够大以容纳结果。 - Mark Ransom

我认为他在谈论 operator+=。虽然这是一种退化情况，但它也是连接的。詹姆斯曾经是 VC++ MVP，所以我期望他对 C++ 有一些了解 :p - Johannes Schaub - litb

1

我毫不怀疑他在C++方面有广泛的知识，只是关于问题存在误解。该问题询问operator+的效率，每次调用它都会返回新的字符串对象，因此使用新的char缓冲区。 - Brian R. Bondy

1

是的。但他后来问到操作符+很慢，做连接的最佳方式是什么。这时就要用到操作符+=了。但我同意詹姆斯的回答有点简短。它让人觉得我们都可以使用操作符+并且它是最高效的 :p - Johannes Schaub - litb

@BrianR.Bondy operator+ 不一定要返回一个新的字符串。如果实现者通过右值引用传递了其中一个操作数，那么可以返回其中一个操作数进行修改。例如，libstdc++ 就是这样做的（参见 https://dev59.com/9nRB5IYBdhLWcg3weHLx#5t7onYgBc1ULPQZF5Fed）。因此，当使用临时对象调用 operator+ 时，它可以达到与返回新字符串相同或几乎相同的性能 - 这可能是默认使用它的另一个支持理由，除非有基准测试表明它代表了瓶颈。 - underscore_d

6

也许应该使用std::stringstream？但我同意这种想法，你应该保持代码可维护性和易懂性，然后进行性能分析，看看是否真的存在问题。

- Tim

4

stringstream速度较慢，参见https://groups.google.com/d/topic/comp.lang.c++.moderated/aiFIGb6za0w - ArtemGr

2

@ArtemGr stringstream 可能很快，请查看 http://www.codeproject.com/Articles/647856/Performance-Improvement-with-the-StringBuilder - mloskot

5

在《Imperfect C++》一书中，Matthew Wilson提出了一个动态字符串连接器，它预先计算最终字符串的长度，以便在连接所有部分之前只进行一次分配。我们还可以通过玩弄“表达式模板”来实现静态连接器。

这种想法已经被实现在STLport std::string实现中 - 由于这个特定的技巧，它不符合标准。

- Luc Hermitte

Glib::ustring::compose() 是 GLib 的 glibmm 绑定中的一个函数，它可以根据提供的格式字符串和可变参数估算并预留最终长度，然后在循环中逐个追加每个参数（或其格式化替换）。我认为这是一种相当常见的工作方式。 - underscore_d

3

对于小字符串，这并不重要。如果你有大字符串，最好将它们作为向量或其他集合的部分存储起来。并且调整你的算法以使用这样的数据集而不是一个大字符串。

我更喜欢使用std::ostringstream进行复杂的连接操作。

- Mykola Golubyev

什么是复杂的连接？ - Rishabh Bhatnagar

2

和大多数事情一样，不做某件事比做它更容易。

如果您想将大字符串输出到GUI，则可能无论您输出到什么都可以将字符串处理为较小的片段，而不是作为一个大字符串（例如，在文本编辑器中连接文本 - 通常它们将行保留为单独的结构）。

如果您想要输出到文件，请流式传输数据，而不是创建大字符串并将其输出。

我从未发现需要加快连接速度，如果我从慢速代码中删除了不必要的连接。

- Pete Kirkham

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

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

- Brian R. Bondy · Accepted Answer

除非你确实需要效率，否则额外的工作可能不值得。只使用operator += 就能获得更好的效率。

现在，在这个声明之后，我将回答你实际的问题...

STL string类的效率取决于您正在使用的STL实现。

您可以通过手动使用c内置函数进行连接，保证效率并自己拥有更大的控制权。 为什么operator + 不高效： 看一下这个接口：

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

你可以看到每个 + 后都返回了一个新的对象，这意味着每次使用了一个新的缓冲区。如果你进行了大量的额外 + 操作，那么效率就不高了。

为什么你可以使它更加高效：

- 你保证了效率，而不是信任委托方能够有效地完成。 - std::string类不知道你字符串的最大大小，也不知道你将多频繁地对其进行连接。你可能有这些知识，并且可以根据这些信息做出相应的处理。这将减少重新分配的次数。 - 你将手动控制缓冲区，因此可以确保在不希望发生时不会将整个字符串复制到新的缓冲区中。 - 你可以使用堆栈来存储缓冲区，这比使用堆要高效得多。 - 字符串 + 运算符将创建一个新的字符串对象并返回它，从而使用一个新的缓冲区。

实现时需要考虑的问题：

- 跟踪字符串长度。 - 保持指向字符串开头和结尾的指针，或者只保留开头并使用开头+长度作为偏移量来找到字符串的结尾。 - 确保存储字符串的缓冲区足够大，以便不需要重新分配数据。 - 使用strcpy而不是strcat，这样就不需要迭代整个字符串来找到字符串的结尾。

Rope数据结构：

如果您需要非常快速的字符串连接，请考虑使用绳子数据结构。