三月 19, 2020
本文翻译自：Efficient QString concatenation with C++17 fold expressions
原文作者：Ivan Cukic
翻译：Richard Lin
在C++中，不论使用标准库（即STL）还是Qt,我们都习惯使用运算符+实现字符串拼接。我们可以编写如下代码：
QString statement{"I'm not"};
QString number{"a number"};
QString space{" "};
QString period{". "};
QString result = statement + space + number + period;但这会有一个很大的缺陷：不必要地产生临时的中间结果。也就是说，在前面的示例中，我们有一个临时字符串来保存statement + space的结果，然后该字符串与number拼接起来，这会产生另一个临时字符串。第二个临时字符串再与period拼接，并产生最终结果字符串，最后销毁前述所有临时字符串。
这意味着我们有几乎和运算符+一样多不必要的内存分配和释放。而且，还要多次拷贝相同的内容。例如，statement字符串的内容首先被复制到第一个临时对象中，然后从第一个临时对象复制到第二个临时对象中，然后从第二个临时对象复制到最终结果中。
可以用一个效率高得多的方式，即创建一个字符串实例，预先分配最终所需的内存，然后反复调用QString::append函数来逐个追加所有要拼接的字符串：
QString result;
result.reserve(statement.length() + number.length() + space.length() + period.length();
result.append(statement);
result.append(number);
result.append(space);
result.append(period);
或者，我们可以使用QString::resize替换QString::reserve，然后使用std::copy（或std::memcpy）把数据复制到其中（稍后我们将看到如何使用std::copy进行字符串拼接）。这可能会稍微提高性能（取决于编译器的优化），因为QString::append需要检查字符串的容量是否足够大以包含结果字符串。std::copyalgorithm没有这个无用的额外检查，这可能会给它一点优势。
这两种方法都比使用运算符+效率高得多，但是如果每次我们想要拼接几个字符串时都必须这样写代码会很烦人。
std::accumulate算法
在我们继续讨论Qt如何解决这个问题之前，还有一个可行的方法：Qt 6中我们将引入一个C++ 17中的优雅的特性，它可以解决这个问题，这里就要介绍一下这个标准库中最重要和最强大的算法之一：std::accumulate。
假设我们有一个字符串序列（例如QVector），我们希望将它们拼接起来，而不是将它们放在单独的变量中。
使用std::accumulate的字符串拼接代码如下：
QVector<QString> strings{ . . . };
std::accumulate(strings.cbegin(), strings.cend(), QString{});该算法实现了您期望的功能——它从一个空的QString开始，并将向量中的每个字符串相加，从而创建一个拼接字符串。
然而由于在默认情况下std::accumulate在内部使用运算符+，因此这与我们最初使用运算符+进行拼接的示例一样效率低下。
为了像前一节一样优化这个实现，我们可以只使用std::accumulate来计算结果字符串的大小，而不使用它进行整体拼接：
QVector<QString> strings{ . . . };
QString result;
result.resize(
std::accumulate(strings.cbegin(), strings.cend(),
0, [] (int acc, const QString& s) {
return s.length();
}));这次，std::accumulate从初始值0开始，对于字符串向量中的每个字符串，它将该初始值的长度相加，最后返回向量中所有字符串的长度总和。
这就是std::accumulate对大多数人的意义——某种求和算法。但这只是一种相当粗浅的认知。
在第一个例子中，我们对向量中的所有字符串进行了求和（即拼接字符串）。但第二个例子有点不同。我们实际上不是求向量元素的和。该向量包含QString，而我们求和的是int。
这就是std::accumulate功能强大的原因：事实上，我们可以向它传递一个自定义操作。该操作函数输入先前的累积值和源集合的一个元素，并生成新的累积值。std::accumulate第一次调用操作函数时，会把初始值作为累积值传递给它，同时把源集合的第一个元素传递给它。该操作函数将计算出新的累积值并将其与源集合的第二个元素一起传递给操作函数的下一个调用。这将重复，直到处理完整个源集合，算法将返回最终操作函数调用的结果。
如前一个代码片段所示，累积值甚至不需要与向量中的元素具有相同的类型。当累积值是整数时，源向量是一个字符串向量。
我们可以利用它来做一些有趣的事情。
前面提到的std::copy算法接收一个被复制的序列（是一对输入iterator）和复制目标（是一个输出iterator），它指向拷贝的目标集合和起始点。算法返回一个iterator，指向复制目标集合中最后一个被复制项之后的元素。
这就说明，如果我们使用std::copy将一个源字符串的数据复制到目标字符串中，我们应该让iterator指向将要存放字符串数据的位置。
于是，我们就有了一个这样的函数：它接受一个字符串（作为一对iterator）和一个输出迭代器，并为我们返回一个新的输出迭代器。这就可以用于std::accumulate的操作函数，来实现高效的字符串拼接了：
QVector<QString> strings{ . . . };
QString result;
result.resize( . . . );
std::accumulate(strings.cbegin(), strings.cend(), result.begin(),
[] (const auto& dest, const QString& s) {
return std::copy(s.cbegin(), s.cend(), dest);
});对std::copy的第一次调用将把第一个字符串复制到result.begin()指向的目标。它将返回result字符串中最后一个复制字符之后的iterator，然后vector中的第二个字符串将从这个位置开始复制。之后再复制第三个字符串，依此类推。
最终，我们得到一个拼接后的字符串。
递归表达式模板
现在我们可以回来讨论如何用Qt的运算符+实现高效的字符串拼接了。
QString result = statement + space + number + period;我们已经知道，字符串拼接的性能问题源于C++会分步解析上述表达式，多次调用运算符+，并且每次调用都会产生新的QString实例。
虽然我们不能改变C++的解析过程，但是我们可以使用一种称为表达式模板（expression templates）的方式来延迟结果字符串的实际计算，直到整个表达式解析全部完成。这需要将运算符+的返回类型从原来的QString改为一种自定义类型，该类型只存储要被拼接的字符串，而不实际执行拼接。
实际上，这正是Qt从4.6版本开始且当快速字符串拼接功能被激活后的运行机制。运算符+将返回名为QStringBuilder的隐藏模板类的实例而不是QString。QStringBuilder模板类只是一个简单形式，它包含对传递给运算符+的参数引用。
基本上，就产生了一个更复杂的版本：
template <typename Left, typename Right>
class QStringBuilder {
const Left& _left;
const Right& _right;
};拼接多个字符串时，您将得到一个更复杂的类型，其中多个QStringBuilder相互嵌套。像这样：
QStringBuilder<QString, QStringBuilder<QString, QStringBuilder<QString, QString>>>这种类型只是用了一种复杂的方式来表达“我有四个字符串需要拼接”。
当我们请求将QStringBuilder转换为QString时（例如，通过将其分配给结果QString），它将首先计算所有包含的字符串的总大小，然后将分配该大小的QStringinstance，最后，它将字符串逐个复制到结果字符串中。
从本质上讲，它的功能与我们之前做的完全相同，但它是自动完成的，完全不需要我们费力。
可变参模板（Variadic templates）
当前QStringBuilder实现的问题是：它通过嵌套实现能容纳任意数量字符串的容器。每个QStringBuilder实例可以恰好包含两个项，可以是字符串或是其他QStringBuilder实例。
这意味着QStringBuilder的所有实例都是一种二叉树，其中QString是叶节点。每当需要对包含的字符串执行某些操作时，QStringBuilder需要处理其左子树，然后递归地处理右子树。
除了使用二叉树，我们还可以使用可变参模板（C++ 11引入，设计QStringBuilder时还没有）。可变参模板允许我们创建具有任意数量的模板参数的类和函数。
这意味着，通过使用std::tuple（元组，C++11引入的新特性）我们可以创建一个QStringBuilder模板类，包含任意多个字符串：
template <typename... Strings>
class QStringBuilder {
std::tuple<Strings...> _strings;
};每当获得一个新的字符串且要添加到QStringBuilder时，我们只需使用std::tuple_cat将两个元组拼接起来（通过运算符%而不是运算符+，因为QString和QStringBuilder支持此运算符）：
template <typename... Strings>
class QStringBuilder {
std::tuple<Strings...> _strings;
template <typename String>
auto operator%(String&& newString) &&
{
return QStringBuilder<Strings..., String>(
std::tuple_cat(_strings, std::make_tuple(newString)));
}
};折叠表达式
大概思路就是这样，但问题是我们如何处理可变参模板的参数包（即Strings ...）。
在C++ 17中，我们得到了一个新的结构体，用于处理可变参模板的参数包，称为折叠表达式（Fold expressions）。
折叠表达式的一般形式如下（运算符+可以替换为其他一些二元运算符，如*，%等）：
(init + ... + pack)或：
(pack + ... + init)第一个变体称为左折叠表达式，将操作视为左结合性（即从左到右优先结合），第二个变体称为右折叠表达式，因为它将操作视为右结合性（即从右到左优先结合）。
如果想使用折叠表达式拼接模板参数包中的字符串，可以这样做：
template <typename... Strings>
auto concatenate(Strings... strings)
{
return (QString{} + ... + strings);
}这将首先对初始值QString{}和参数包的第一个元素调用运算符+。然后，它将根据上一次调用的结果和参数包的第二个元素调用运算符+。以此类推，直到处理完所有元素都。
听起来很熟悉，对吧？
可以发现，它和std::accumulate的行为非常类似。唯一的区别是std::accumulate算法是处理数据的运行时序列（向量、数组、列表等），而折叠表达式处理的是编译时序列，即可变参模板的参数包。
我们可以遵循与std::accumulate相同的步骤来优化之前的拼接实现。首先，我们需要计算所有字符串长度的和。这对于折叠表达式来说非常简单：
template <typename... Strings>
auto concatenate(Strings... strings)
{
const auto totalSize = (0 + ... + strings.length());
. . .
}当折叠表达式展开参数包时，它将得到以下表达式：
0 + string1.length() + string2.length() + string3.length()于是，我们得到了结果字符串的大小。现在可以继续分配一个能够容纳结果的字符串，并将源字符串逐个追加到该字符串中。
如前所述，折叠表达式可以与C++的二元运算符一起使用。如果想为参数包中的每个元素执行一个函数，我们可以使用C和C++中最神奇的运算符之一：逗号运算符。
template <typename... Strings>
auto concatenate(Strings... strings)
{
const auto totalSize = (0 + ... + strings.length());
QString result;
result.reserve(totalSize);
(result.append(strings), ...);
return result;
}以上会为参数包中的每个字符串调用append函数，最后返回拼接完成的字符串。
使用折叠表达式自定义运算符
之前对std::accumulate采用的第二种方式有些复杂：我们必须提供一个自定义的累加操作函数。而累计值是目标集合中的迭代器，它指向下一个字符串的复制位置。
如果我们想使用折叠表达式自定义操作函数，那么就需要创建一个二元运算符。就像我们传递给std::accumulate的lambda表达式一样，该运算符需要获得一个输出迭代器和一个字符串，它需要调用std::copy将字符串内容复制到该迭代器，同时返回一个新的迭代器，该迭代器指向最后复制的字符之后的元素。
于是，我们重载了操作符<<：
template <typename Dest, typename String>
auto operator<< (Dest dest, const String& string)
{
return std::copy(string.cbegin(), string.cend(), dest);
}有了这个操作符，使用折叠表达式将所有字符串复制到目标缓冲区就变得非常简单。初始值是目标缓冲区的初始迭代器，我们将参数包中的每个字符串传递给操作符<<：
template <typename... Strings>
auto concatenate(Strings... strings)
{
const auto totalSize = (0 + ... + strings.length());
QString result;
result.resize(totalSize);
(result.begin() << ... << strings);
return result;
}折叠表达式和元组
现在，我们知道如何有效地拼接字符串集合，无论是使用向量还是可变模板参数包。
问题是我们的QStringBuilder两者都没用。它将字符串存储在std::tuple中，既不是可迭代集合，也不是参数包。
为了使用折叠表达式，我们需要参数包。我们可以创建一个包含从0到n-1的索引列表的参数包来代替包含字符串的参数包，稍后我们可以使用std::get来访问元组内部的值。
通过std::index_sequence很容易创建这个参数包，该序列表示一个编译时的整数列表。我们可以创建一个helper函数，它以std::index_sequence<Idx…>作为参数，然后在折叠表达式中使用std::get<Idx>（_strings）逐个访问元组中的字符串。
template <typename... Strings>
class QStringBuilder {
using Tuple = std::tuple<Strings...>;
Tuple _strings;
template <std::size_t... Idx>
auto concatenateHelper(std::index_sequence<Idx...>) const
{
const auto totalSize = (std::get<Idx>(_strings).size() + ... + 0);
QString result;
result.resize(totalSize);
(result.begin() << ... << std::get<Idx>(_strings));
return result;
}
};我们只需要创建一个包装函数来为元组创建索引序列，然后调用concatenateHelper函数：
template <typename... Strings>
class QStringBuilder {
. . .
auto concatenate() const
{
return concatenateHelper(
std::index_sequence_for<Strings...>{});
}
};总结
本文只讨论了字符串拼接部分的实现。对于真正的QStringBuilder，还有很多东西，但是细节的实现作为博客文章阅读来说会变得有点繁琐。
我们需要小心运算符重载：比如像当前的QStringBuilder实现，我们必须使用std::enable_if以使其对Qt中的所有可拼接类型都有效，而且这些操作符不会污染全局命名空间。
还需要用一种安全的方式处理传递给字符串拼接过程的临时变量，就像QStringBuilder只存储对字符串的引用，对于临时字符串，这些引用很容易成为悬挂引用。
能够以更安全的方式处理传递给字符串连接的临时变量也是有益的，因为QStringBuilder只存储对字符串的引用，在临时字符串的情况下，这些引用很容易成为悬挂引用。
关于作者
Ivan CukicIvan是KDAB的高级软件工程师。他是《Functional Programming in C++》的作者、KDE开发者、并且是自由软件软件运动的倡导者。他在网上的大部分活动都围绕着KDE的发展展开，最引人注目的是Activities和Plasma，经常出游于艺术品创作领域。Ivan拥有贝尔格莱德数学学院的博士学位。他在博客上讨论和编写C++相关文章来传授功能性编程和现代C++技术。