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

StackOverflow https://stackoverflow.com/questions/611263

题

我听到一些人对 std::string 中的“+”运算符以及加快连接速度的各种解决方法表示担忧。这些真的有必要吗？如果是这样，在 C++ 中连接字符串的最佳方法是什么？

有帮助吗？

解决方案

额外的工作可能不值得，除非你真的需要效率。 只需使用运算符 += 代替，您可能会获得更高的效率。

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

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 和＆quot;的串联的新字符串。 ：“。现在，这发生了：

(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 + = ，但是您需要使用丑陋的括号来修复优先级。

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

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

或许是std :: stringstream？

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

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

这种想法已在STLport std :: string实现中实现 - 由于这种精确的黑客攻击而不符合标准。

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

另一方面，

std :: string 追加和 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!");
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top