C ++中有效的string连接

我听到一些人表示担心std :: string中的“+”运算符和各种解决方法,以加快串联。 这些真的有必要吗? 如果是这样,在C ++中连接string的最佳方法是什么?

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

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

STLstring类的效率取决于您正在使用的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的最大大小一无所知,也不知道你将如何连接它。 你可能有这方面的知识,并可以根据这些信息做事情。 这将导致更less的重新分配。
  • 您将手动控制缓冲区,这样您可以确保在不希望发生这种情况时,不会将整个string复制到新的缓冲区中。
  • 你可以使用你的缓冲区堆栈,而不是更有效的堆栈。
  • string+运算符将创build一个新的string对象,并返回它,因此使用新的缓冲区。

实施考虑:

  • 跟踪string的长度。
  • 保持一个指向string结尾和开始位置的指针,或者只是开始,并使用start +长度作为偏移量来查找string的结尾。
  • 确保你存储你的string的缓冲区足够大,所以你不需要重新分配数据
  • 使用strcpy而不是strcat,所以你不需要遍历string的长度来查找string的结尾。

绳索数据结构:

如果你需要真正快速的连接,可以考虑使用绳索数据结构 。

保留你的最终空间,然后使用附加方法和缓冲区。 例如,假设您预期您的最终string长度为100万个字符:

 std::string s; s.reserve(1000000); while (whatever) { s.append(buf,len); } 

我不会为此担心的。 如果你在一个循环中执行,string将总是预先分配内存,以最小化重新分配 – 在这种情况下,只需使用operator+= 。 如果你手动做,像这样或更长的东西

 a + " : " + c 

然后创build临时对象 – 即使编译器可以消除一些返回值副本。 这是因为在连续调用的operator+它不知道引用参数是引用一个已命名的对象,还是从子operator+调用返回的临时值。 在不首先进行简介之前,我宁愿不担心它。 但让我们举一个例子来表明这一点。 我们首先引入括号来使绑定清晰。 我将这些参数直接放在函数声明之后,这是为了清晰起见。 在那之下,我展示了结果expression式是什么:

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

现在,另外, tmp1是第一次调用operator +返回的显示参数。 我们假设编译器非常聪明,优化了返回值副本。 所以我们最终得到一个包含a" : "连接的新string。 现在,这发生了:

 (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> 

它使用相同的函数临时和命名的string! 所以编译器必须将参数复制到一个新的string中,并附加到该string中,并从operator+主体返回。 它不能把一个暂时的记忆和追加到这个。 expression越大,string的副本就越多。

接下来Visual Studio和GCC将支持c ++ 1x的移动语义 (补充复制语义 )和右值引用作为实验添加。 这可以确定参数是否引用临时或不。 这将使得这样的增加非常快速,因为所有这些将最终在一个“添加pipe道”没有副本。

如果事实certificate是一个瓶颈,你仍然可以做到

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

append调用将参数附加到*this ,然后返回对自己的引用。 所以没有临时复制在那里完成。 或者,也可以使用operator+= ,但是需要使用丑陋的圆括号来确定优先级。

对于大多数应用程序来说,这并不重要。 只要写下自己的代码,就不会意识到+运营商的工作方式,只有把它看成是一个明显的瓶颈,才能掌握自己的想法。

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

也许std :: stringstream呢?

但是我同意这种观点,你应该保持可维护性和可理解性,然后确定是否真的有问题。

Imperfect C ++中 ,Matthew Wilson提出了一个dynamic的string连接器,它预先计算最终string的长度,以便在连接所有部分之前只有一个分配。 我们也可以通过使用expression式模板来实现静态连接器。

这种想法已经在STLport std :: string实现中实现 – 由于这种精确的破解而不符合标准。

对于小string,这并不重要。 如果你有大string,你最好将它们存储在vector或其他集合中作为零件。 并且使用你的algorithm来处理这些数据,而不是一个大的string。

我更喜欢std :: ostringstream复杂的连接。

和大多数事情一样,做事情比做事更容易。

如果你想输出一个大的string到一个GUI,那么无论你输出什么东西,都可以比string更好地处理string(例如,在文本编辑器中连接文本 – 通常它们保持单独的行结构)。

如果你想输出到一个文件,stream数据,而不是创build一个大的string,并输出。

如果我从慢代码中删除不必要的连接,我从来没有发现需要更快速地进行连接。

std::string operator+分配一个新的string,并每次复制两个操作数string。 重复许多次,它变得昂贵,O(N)。

std::string appendoperator+=另一方面,每当string需要增长时,容量会增加50%。 这大大减less了内存分配和复制操作的数量,O(log n)。

封装在跟踪数组大小和分配字节数的类中的简单字符数组是最快的。

诀窍是在开始时只做一个大的分配。

https://github.com/pedro-vicente/table-string

基准

对于Visual Studio 2015,x86debugging版本,通过C ++ std :: string进行基本的改进。

 | API | Seconds | ----------------------|----| | SDS | 19 | | std::string | 11 | | std::string (reserve) | 9 | | table_str_t | 1 |