性能 - C ++中的高效字符串连接
我听到一些人表达了对" +"的担忧。 std :: string中的运算符以及加速连接的各种变通方法。 这些都真的有必要吗? 如果是这样,在C ++中连接字符串的最佳方法是什么?
额外的工作可能不值得,除非你真的需要效率。 只需使用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,因此您不需要遍历字符串的长度来查找字符串的结尾。
绳索数据结构:
如果您需要非常快速的连接,请考虑使用绳索数据结构。
之前保留最后一个空格,然后使用带缓冲区的append方法。 例如,假设您希望最终的字符串长度为100万个字符:
std::string s;
s.reserve(1000000);
while (whatever)
{
s.append(buf,len);
}
我不担心。 如果你在循环中执行它,字符串将始终预分配内存以最小化重新分配 - 在这种情况下只需使用operator+=
。 如果您手动执行此操作,则需要更长时间
a + " : " + c
然后它创造了临时性 - 即使编译器可以消除一些返回值副本。 这是因为在连续调用append
时,它不知道引用参数是引用命名对象还是从子*this
调用返回的临时对象。 在没有首先进行分析之前,我宁愿不担心它。 但是,让我们举一个例子来证明这一点。 我们首先引入括号以使绑定清晰。 为了清楚起见,我在函数声明之后直接放了参数。 在下面,我展示了结果表达式是什么:
((a + " : ") + c)
calls string operator+(string const&, char const*)(a, " : ")
=> (tmp1 + c)
现在,在该添加中,append
是第一次调用operator +并返回显示的参数。 我们假设编译器非常聪明并优化了返回值副本。 所以我们最终得到一个包含*this
和operator+=
串联的新字符串。现在,这种情况发生了:
(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>
它对临时字符串和命名字符串使用相同的函数! 因此编译器必须将参数复制到一个新字符串并追加到该字符串并从append
的正文中返回它。它不能占用临时的内存并附加到该字符串。 表达式越大,字符串的副本就越多。
接下来,Visual Studio和GCC将支持c ++ 1x的移动语义(补充复制语义)和rvalue引用作为实验添加。 这允许确定参数是否引用临时参数。 这将使得这样的添加速度惊人,因为上述所有内容最终都会出现在“添加管道”中。 没有副本。
如果它成为瓶颈,你仍然可以做到
std::string(a).append(" : ").append(c) ...
append
调用将参数附加到*this
,然后返回对自己的引用。 因此,那里没有复制临时工。 或者,可以使用operator+=
,但是您需要使用丑陋的括号来修复优先级。
对于大多数应用来说,它只是无所谓。 只需编写代码,幸福地不知道+运算符的工作原理,只有当它成为一个明显的瓶颈时才能自己动手。
与.NET System.Strings不同,C ++的std :: strings是可变的,因此可以通过简单的连接来构建,就像通过其他方法一样快。
也许是std :: stringstream而已?
但我同意这样的观点,即你应该保持它的可维护性和可理解性,然后分析一下你是否真的遇到问题。
在Imperfect C ++中,Matthew Wilson提出了一个动态字符串连接器,它预先计算最终字符串的长度,以便在连接所有部分之前只进行一次分配。 我们还可以通过使用表达式模板来实现静态连接器。
这种想法已在STLport std :: string实现中实现 - 由于这种精确的黑客攻击而不符合标准。
std::string
append
分配新字符串并每次复制两个操作数字符串。 重复多次,它变得昂贵,O(n)。
另一方面,std::string
append
和operator+=
,每次字符串需要增长时,将容量减少50%。 这显着减少了内存分配和复制操作的数量,O(log n)。
对于小弦乐而言并不重要。如果你有大字符串,你最好将它们存储在矢量或其他集合中作为部分存储。 并添加您的算法来处理这样的数据集而不是一个大字符串。
我更喜欢std :: ostringstream用于复杂的连接。
与大多数事情一样,做某事比做事更容易。
如果你想将大字符串输出到GUI,可能是你输出的任何东西都可以比一个大字符串更好地处理字符串(例如,在文本编辑器中连接文本 - 通常它们保持行 作为单独的结构)。
如果要输出到文件,请流式传输数据,而不是创建大型字符串并输出该字符串。
如果我从慢速代码中删除不必要的连接,我从未发现需要更快地进行连接。
一个简单的字符数组,封装在一个跟踪数组大小和分配字节数的类中是最快的。
诀窍是在开始时只做一个大的分配。
在
[https://github.com/pedro-vicente/table-string]
基准
对于Visual Studio 2015,x86调试构建,对C ++ std :: string的改进。
| API | Seconds
| ----------------------|----|
| SDS | 19 |
| std::string | 11 |
| std::string (reserve) | 9 |
| table_str_t | 1 |
如果在结果字符串中预先分配(保留)空间,则可能是最佳性能。
template<typename... Args>
std::string concat(Args const&... args)
{
size_t len = 0;
for (auto s : {args...}) len += strlen(s);
std::string result;
result.reserve(len); // <--- preallocate result
for (auto s : {args...}) result += s;
return result;
}
用法:
std::string merged = concat("This ", "is ", "a ", "test!");