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

Question

我听到一些人表达了对std :: string中"+"运算符的担忧以及加速连接的各种变通方法.这些都真的有必要吗？如果是这样,在C++中连接字符串的最佳方法是什么？

Answer 1

额外的工作可能不值得,除非你真的需要效率. 只需使用operator + =,您可能会有更好的效率.

现在在免责声明之后,我将回答你的实际问题......

STL字符串类的效率取决于您正在使用的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类对字符串的最大大小一无所知,也不知道你连接它的频率.您可能拥有此知识,并且可以根据获取此信息来执行操作.这将减少重新分配.
• 您将手动控制缓冲区,这样您就可以确保在不希望发生这种情况时不会将整个字符串复制到新的缓冲区中.
• 您可以将堆栈用于缓冲​​区而不是堆,这样可以提高效率.
• string +运算符将创建一个新的字符串对象,并使用新的缓冲区返回它.

实施的考虑因素:

• 跟踪字符串长度.
• 保持指向字符串末尾和开头的指针,或者只是开始,并使用start + the length作为偏移量来查找字符串的结尾.
• 确保存储字符串的缓冲区足够大,因此您无需重新分配数据
• 使用strcpy而不是strcat,因此您不需要遍历字符串的长度来查找字符串的结尾.

绳索数据结构:

如果您需要非常快速的连接,请考虑使用绳索数据结构.

Answer 2

之前保留最后一个空格,然后使用带缓冲区的append方法.例如,假设您希望最终的字符串长度为100万个字符:

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

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

Answer 3

我不担心.如果你在循环中执行它,字符串将始终预分配内存以最小化重新分配 - 只是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的移动语义(补充复制语义)和rvalue引用作为实验添加.这允许确定参数是否引用临时参数.这将使得这样的添加速度惊人地快,因为上述所有内容将最终出现在一个没有副本的"添加管道"中.

如果它成为瓶颈,你仍然可以做到

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

该append调用参数追加到*this,然后返回一个引用到自己.因此,那里没有复制临时工.或者,operator+=可以使用,但你需要丑陋的括号来修复优先级.

Answer 4

对于大多数应用来说,这无关紧要.只需编写代码,幸福地不知道+运算符的工作原理,只有当它成为一个明显的瓶颈时才能自己动手.

Answer 5

std::string operator+每次分配一个新字符串并复制两个操作数字符串。重复多次，它变得昂贵，O(n)。

std::string append而operator+=在另一方面，50％每次字符串需要成长时间撞击的能力。这显着减少了内存分配和复制操作的数量，O(log n)。

Answer 6

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

Answer 7

也许是std :: stringstream而已？

但我同意这样的观点,即你应该保持它的可维护性和可理解性,然后分析一下你是否确实遇到了问题.

Answer 8

在《不完美的 C++》中，Matthew Wilson 提出了一种动态字符串连接器，它预先计算最终字符串的长度，以便在连接所有部分之前仅进行一次分配。我们还可以通过使用表达式模板来实现静态连接器。

这种想法已在 STLport std::string 实现中实现——由于这种精确的 hack，它不符合标准。