我听到一些人表达了对 std::string 中“+”运算符的担忧,以及各种加快连接速度的变通方法。这些真的有必要吗?如果是这样,在 C++ 中连接字符串的最佳方法是什么?
13 回答
除非你真的需要效率,否则额外的工作可能不值得。 只需使用运算符 += 代替,您可能会获得更好的效率。
现在,在免责声明之后,我将回答您的实际问题......
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 + 运算符将创建一个新的字符串对象并将其返回,因此使用新的缓冲区。
实施注意事项:
- 跟踪字符串长度。
- 保留指向字符串结尾和开头的指针,或者只是开头并使用开头 + 长度作为偏移量来查找字符串的结尾。
- 确保您存储字符串的缓冲区足够大,因此您不需要重新分配数据
- 使用 strcpy 而不是 strcat,这样您就不需要遍历字符串的长度来查找字符串的结尾。
绳子数据结构:
如果您需要真正快速的连接,请考虑使用绳索数据结构。
之前保留最后的空间,然后使用带有缓冲区的 append 方法。例如,假设您希望最终的字符串长度为 100 万个字符:
std::string s;
s.reserve(1000000);
while (whatever)
{
s.append(buf,len);
}
我不会担心的。如果您在循环中执行此操作,字符串将始终预先分配内存以最小化重新分配 - 只需operator+=
在这种情况下使用。如果你手动做,像这样或更长
a + " : " + c
然后它正在创建临时文件——即使编译器可以消除一些返回值副本。这是因为在连续调用operator+
中,它不知道引用参数是引用命名对象还是从子operator+
调用返回的临时对象。在没有先进行分析之前,我宁愿不担心它。但是,让我们举一个例子来说明这一点。我们首先引入括号以使绑定清晰。为了清楚起见,我将参数直接放在函数声明之后。在此之下,我展示了结果表达式是什么:
((a + " : ") + c)
calls string operator+(string const&, char const*)(a, " : ")
=> (tmp1 + c)
现在,除此之外,tmp1
第一次调用 operator+ 时返回的是显示的参数。我们假设编译器非常聪明并且优化了返回值副本。所以我们最终得到一个包含a
and连接的新字符串" : "
。现在,这发生了:
(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+=
可以使用,但您需要丑陋的括号来修复优先级。
对于大多数应用程序来说,这无关紧要。只需编写代码,完全不知道 + 运算符的工作原理,只有当它成为明显的瓶颈时,才将事情掌握在自己手中。
std::string
operator+
分配一个新字符串并每次复制两个操作数字符串。重复很多次,它变得昂贵,O(n)。
std::string
append
另一方面,operator+=
每当字符串需要增长时,将容量提高 50%。这显着减少了内存分配和复制操作的数量,O(log n)。
与 .NET System.Strings 不同,C++ 的 std::strings是可变的,因此可以通过简单的连接来构建,就像通过其他方法一样快。
也许是 std::stringstream ?
但我同意这样的观点,即您可能应该保持它的可维护性和可理解性,然后进行分析以查看您是否真的遇到问题。
在Imperfect C++中,Matthew Wilson 提出了一个动态字符串连接器,它预先计算最终字符串的长度,以便在连接所有部分之前只有一个分配。我们还可以通过使用表达式模板来实现静态连接器。
这种想法已在 STLport std::string 实现中实现——由于这种精确的黑客攻击,它不符合标准。
对于小字符串来说没关系。如果您有大字符串,最好将它们存储在向量中或作为部分存储在其他集合中。并添加您的算法以使用此类数据集而不是一个大字符串。
我更喜欢 std::ostringstream 进行复杂的连接。
与大多数事情一样,不做比做更容易。
如果您想将大字符串输出到 GUI,那么无论您输出到什么,都可能比大字符串更好地处理字符串(例如,在文本编辑器中连接文本 - 通常它们将行分开结构)。
如果要输出到文件,请流式传输数据,而不是创建一个大字符串并输出它。
如果我从慢代码中删除了不必要的串联,我从来没有发现需要使串联更快。
如果您在结果字符串中预先分配(保留)空间,则可能是最佳性能。
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!");
一个简单的字符数组,封装在一个跟踪数组大小和分配字节数的类中是最快的。
诀窍是在开始时只进行一次大分配。
在
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 |
您可以尝试为每个项目保留内存:
namespace {
template<class C>
constexpr auto size(const C& c) -> decltype(c.size()) {
return static_cast<std::size_t>(c.size());
}
constexpr std::size_t size(const char* string) {
std::size_t size = 0;
while (*(string + size) != '\0') {
++size;
}
return size;
}
template<class T, std::size_t N>
constexpr std::size_t size(const T (&)[N]) noexcept {
return N;
}
}
template<typename... Args>
std::string concatStrings(Args&&... args) {
auto s = (size(args) + ...);
std::string result;
result.reserve(s);
return (result.append(std::forward<Args>(args)), ...);
}