C + + 中高效的字符串串联

我听到一些人对 std: : string 中的“ +”操作符以及加速连接的各种变通方法表示担忧。这些真的有必要吗?如果是这样,在 C + + 中串联字符串的最佳方法是什么?

121156 次浏览

The extra work is probably not worth it, unless you really really need efficiency. You probably will have much better efficiency simply by using operator += instead.

在那个免责声明之后,我会回答你真正的问题..。

STL 字符串类的效率取决于您正在使用的 STL 的实现。

您可以自己通过 c 内置函数手动进行连接,从而实现 保证效率有更大的控制权

返回文章页面为什么 + 运营商效率低下:

看看这个界面:

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)

可以看到在每个 + 之后返回一个新对象。这意味着每次都要使用一个新的缓冲区。如果你正在做一大堆额外的 + 操作,这是没有效率的。

为什么你可以让它更有效率:

  • 你是在保证效率,而不是信任一个委托人为你高效地完成任务
  • String 类不知道字符串的最大大小,也不知道连接到它的频率。你可能有这方面的知识,可以做的事情的基础上有这些信息。这将导致更少的再分配。
  • 您将手动控制缓冲区,以确保在不希望发生这种情况时不会将整个字符串复制到新的缓冲区中。
  • 您可以将堆栈用于缓冲区,而不是使用效率更高的堆。
  • String + 运算符将创建一个新的字符串对象,并使用新的缓冲区返回该对象。

执行方面的考虑因素:

  • 跟踪字符串的长度。
  • 保留一个指向字符串末尾和开始的指针,或者仅仅指向开始,并使用开始 + 长度作为偏移量来找到字符串的末尾。
  • Make sure the buffer you are storing your string in, is big enough so you don't need to re-allocate data
  • 使用 strcpy 而不是 strcat,这样就不需要遍历字符串的长度来查找字符串的结尾。

Rope data structure:

If you need really fast concatenations consider using a 绳索数据结构绳索数据结构.

对于大多数应用程序来说,这并不重要。只需编写代码,幸福地不知道 + 运算符到底是如何工作的,只有在它成为明显的瓶颈时才亲自动手。

也许用字符串代替?

But I agree with the sentiment that you should probably just keep it maintainable and understandable and then profile to see if you are really having problems.

对于细小的弦来说,这并不重要。 如果你有很大的字符串,你最好将它们存储在向量中,或者作为部分存储在其他集合中。并调整您的算法,使其适用于这样的数据集,而不是一个大字符串。

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

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

如果你想把大字符串输出到 GUI 中,无论你输出什么,它都可以比大字符串更好地处理字符串(例如,在文本编辑器中连接文本——通常它们将行作为单独的结构)。

如果希望输出到文件,请对数据进行流处理,而不是创建一个大字符串并将其输出。

如果我从缓慢的代码中移除了不必要的连接,我从来没有发现有必要使连接更快。

我不会担心的。如果在循环中执行,字符串总是会预分配内存,以最小化重新分配——在这种情况下只需使用 operator+=。如果你手动操作,像这样或者更长

a + " : " + c

然后它创建临时的-即使编译器可以消除一些返回值的副本。这是因为在先后调用的 operator+中,它不知道引用参数是引用命名对象还是从子 operator+调用返回的临时对象。我宁愿不要担心它之前,没有首先侧写。让我们举个例子来说明。我们首先引入括号来清楚地说明绑定。为了清晰起见,我将参数直接放在函数声明之后。下面,我将显示结果表达式:

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

现在,除此之外,tmp1就是第一次调用操作符 + 时返回的值,其中包含所示的参数。我们假设编译器真的很聪明,并且优化了返回值的副本。所以我们最终得到一个包含 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 的 move semantics(补充 复制语义学)和 rvalue 引用作为实验性的添加。这样就可以确定参数是否引用临时的。这将使此类添加变得惊人地快,因为所有上述内容都将以一个没有副本的“添加管道”结束。

如果它最终成为一个瓶颈,您仍然可以这样做

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

append调用将参数追加到 *this,然后返回对它们自己的引用。所以不会在那里复制临时用户。或者,也可以使用 operator+=,但是您需要丑陋的括号来修复优先级。

Unlike .NET System.Strings, C++'s std::strings are mutable, and therefore can be built through simple concatenation just as fast as through other methods.

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

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


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

不完美的 C + + 中,Matthew Wilson 提供了一个 充满活力字符串连接器,它预先计算最终字符串的长度,以便在连接所有部分之前只有一个分配。我们还可以通过使用 表达式模板实现静态连接器。

That kind of idea have been implemented in STLport std::string implementation -- that does not conform to the standard because of this precise hack.

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

std::string append and operator+= on the other hand, bump the capacity by 50% every time the string needs to grow. Which reduces the number of memory allocations and copy operations significantly, O(log n).

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

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

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

Benchmarks

对于 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!");

你可以试试这个,每个项目都有内存保留:

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)), ...);
}

针对 Visual Studio C/C + + 17.2.5和 Ryzen 5600x 上的 Boost 1.79.0的基准测试:

n iter = 10
n parts = 10000000
total string result length = 70000000
Boost join: 00:00:02.105006
std::string append (Reserve): 00:00:00.485498
std::string append (simple): 00:00:00.679999
Note: times are cumulative sums over all iterations.

结论: 提升实现在性能方面不是很好。除非字符串的最终长度至少在几十兆字节左右,否则使用 std: : string 的储备不会太有影响。

在实践中,简单的附加(没有保留)甚至可能更快,因为基准使用了已经初始化的字符串部分向量。在实践中,该向量通常仅对 reserve/Boost 连接变量是必需的,因此会对它们造成额外的性能损失。

再跑一圈:

n iter = 100
n parts = 1000000
total string result length = 6000000
Boost join: 00:00:01.953999
std::string append (Reserve): 00:00:00.535502
std::string append (simple): 00:00:00.679002
Note: times are cumulative sums over all iterations.