開發(fā)框架Qt使用教程：使用C++17 fold表達(dá)式實(shí)現(xiàn)高效的QString拼接

---

Qt是目前最先進(jìn)、最完整的跨平臺C++開發(fā)工具。它不僅完全實(shí)現(xiàn)了一次編寫，所有平臺無差別運(yùn)行，更提供了幾乎所有開發(fā)過程中需要用到的工具。如今，Qt已被運(yùn)用于超過70個行業(yè)、數(shù)千家企業(yè)，支持?jǐn)?shù)百萬設(shè)備及應(yīng)用。

點(diǎn)擊下載Qt最新版

在C++中，不論使用標(biāo)準(zhǔn)庫（即STL）還是Qt,我們都習(xí)慣使用運(yùn)算符+實(shí)現(xiàn)字符串拼接。我們可以編寫如下代碼：

QString statement{"I'm not"};
QString number{"a number"};
QString space{" "};
QString period{". "};
QString result = statement + space + number + period;

但這會有一個很大的缺陷：不必要地產(chǎn)生臨時的中間結(jié)果。也就是說，在前面的示例中，我們有一個臨時字符串來保存statement + space的結(jié)果，然后該字符串與number拼接起來，這會產(chǎn)生另一個臨時字符串。第二個臨時字符串再與period拼接，并產(chǎn)生最終結(jié)果字符串，最后銷毀前述所有臨時字符串。

這意味著我們有幾乎和運(yùn)算符+一樣多不必要的內(nèi)存分配和釋放。而且，還要多次拷貝相同的內(nèi)容。例如，statement字符串的內(nèi)容首先被復(fù)制到第一個臨時對象中，然后從第一個臨時對象復(fù)制到第二個臨時對象中，然后從第二個臨時對象復(fù)制到最終結(jié)果中。

可以用一個效率高得多的方式，即創(chuàng)建一個字符串實(shí)例，預(yù)先分配最終所需的內(nèi)存，然后反復(fù)調(diào)用QString::append函數(shù)來逐個追加所有要拼接的字符串：

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）把數(shù)據(jù)復(fù)制到其中（稍后我們將看到如何使用std::copy進(jìn)行字符串拼接）。這可能會稍微提高性能（取決于編譯器的優(yōu)化），因?yàn)镼String::append需要檢查字符串的容量是否足夠大以包含結(jié)果字符串。std::copyalgorithm沒有這個無用的額外檢查，這可能會給它一點(diǎn)優(yōu)勢。

這兩種方法都比使用運(yùn)算符+效率高得多，但是如果每次我們想要拼接幾個字符串時都必須這樣寫代碼會很煩人。

std::accumulate算法

在我們繼續(xù)討論Qt如何解決這個問題之前，還有一個可行的方法：Qt 6中我們將引入一個C++ 17中的優(yōu)雅的特性，它可以解決這個問題，這里就要介紹一下這個標(biāo)準(zhǔn)庫中最重要和最強(qiáng)大的算法之一：std::accumulate。

假設(shè)我們有一個字符串序列（例如QVector），我們希望將它們拼接起來，而不是將它們放在單獨(dú)的變量中。

使用std::accumulate的字符串拼接代碼如下：

QVector<QString> strings{ . . . };
std::accumulate(strings.cbegin(), strings.cend(), QString{});

該算法實(shí)現(xiàn)了您期望的功能——它從一個空的QString開始，并將向量中的每個字符串相加，從而創(chuàng)建一個拼接字符串。

然而由于在默認(rèn)情況下std::accumulate在內(nèi)部使用運(yùn)算符+，因此這與我們最初使用運(yùn)算符+進(jìn)行拼接的示例一樣效率低下。

為了像前一節(jié)一樣優(yōu)化這個實(shí)現(xiàn)，我們可以只使用std::accumulate來計算結(jié)果字符串的大小，而不使用它進(jìn)行整體拼接：

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對大多數(shù)人的意義——某種求和算法。但這只是一種相當(dāng)粗淺的認(rèn)知。

 在第一個例子中，我們對向量中的所有字符串進(jìn)行了求和（即拼接字符串）。但第二個例子有點(diǎn)不同。我們實(shí)際上不是求向量元素的和。該向量包含QString，而我們求和的是int。

這就是std::accumulate功能強(qiáng)大的原因：事實(shí)上，我們可以向它傳遞一個自定義操作。該操作函數(shù)輸入先前的累積值和源集合的一個元素，并生成新的累積值。std::accumulate第一次調(diào)用操作函數(shù)時，會把初始值作為累積值傳遞給它，同時把源集合的第一個元素傳遞給它。該操作函數(shù)將計算出新的累積值并將其與源集合的第二個元素一起傳遞給操作函數(shù)的下一個調(diào)用。這將重復(fù)，直到處理完整個源集合，算法將返回最終操作函數(shù)調(diào)用的結(jié)果。

 如前一個代碼片段所示，累積值甚至不需要與向量中的元素具有相同的類型。當(dāng)累積值是整數(shù)時，源向量是一個字符串向量。

我們可以利用它來做一些有趣的事情。

前面提到的std::copy算法接收一個被復(fù)制的序列（是一對輸入iterator）和復(fù)制目標(biāo)（是一個輸出iterator），它指向拷貝的目標(biāo)集合和起始點(diǎn)。算法返回一個iterator，指向復(fù)制目標(biāo)集合中最后一個被復(fù)制項(xiàng)之后的元素。

這就說明，如果我們使用std::copy將一個源字符串的數(shù)據(jù)復(fù)制到目標(biāo)字符串中，我們應(yīng)該讓iterator指向?qū)⒁娣抛址當(dāng)?shù)據(jù)的位置。

于是，我們就有了一個這樣的函數(shù)：它接受一個字符串（作為一對iterator）和一個輸出迭代器，并為我們返回一個新的輸出迭代器。這就可以用于std::accumulate的操作函數(shù)，來實(shí)現(xiàn)高效的字符串拼接了：

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的第一次調(diào)用將把第一個字符串復(fù)制到result.begin()指向的目標(biāo)。它將返回result字符串中最后一個復(fù)制字符之后的iterator，然后vector中的第二個字符串將從這個位置開始復(fù)制。之后再復(fù)制第三個字符串，依此類推。

最終，我們得到一個拼接后的字符串。

遞歸表達(dá)式模板

現(xiàn)在我們可以回來討論如何用Qt的運(yùn)算符+實(shí)現(xiàn)高效的字符串拼接了。

QString result = statement + space + number + period;

我們已經(jīng)知道，字符串拼接的性能問題源于C++會分步解析上述表達(dá)式，多次調(diào)用運(yùn)算符+，并且每次調(diào)用都會產(chǎn)生新的QString實(shí)例。

雖然我們不能改變C++的解析過程，但是我們可以使用一種稱為表達(dá)式模板（expression templates）的方式來延遲結(jié)果字符串的實(shí)際計算，直到整個表達(dá)式解析全部完成。這需要將運(yùn)算符+的返回類型從原來的QString改為一種自定義類型，該類型只存儲要被拼接的字符串，而不實(shí)際執(zhí)行拼接。

實(shí)際上，這正是Qt從4.6版本開始且當(dāng)快速字符串拼接功能被激活后的運(yùn)行機(jī)制。運(yùn)算符+將返回名為QStringBuilder的隱藏模板類的實(shí)例而不是QString。QStringBuilder模板類只是一個簡單形式，它包含對傳遞給運(yùn)算符+的參數(shù)引用。

基本上，就產(chǎn)生了一個更復(fù)雜的版本：

template <typename Left, typename Right>
class QStringBuilder {
    const Left& _left;
    const Right& _right;
};

拼接多個字符串時，您將得到一個更復(fù)雜的類型，其中多個QStringBuilder相互嵌套。像這樣：

QStringBuilder<QString, QStringBuilder<QString, QStringBuilder<QString, QString>>>

這種類型只是用了一種復(fù)雜的方式來表達(dá)“我有四個字符串需要拼接”。

當(dāng)我們請求將QStringBuilder轉(zhuǎn)換為QString時（例如，通過將其分配給結(jié)果QString），它將首先計算所有包含的字符串的總大小，然后將分配該大小的QStringinstance，最后，它將字符串逐個復(fù)制到結(jié)果字符串中。

從本質(zhì)上講，它的功能與我們之前做的完全相同，但它是自動完成的，完全不需要我們費(fèi)力。

可變參模板（Variadic templates）

當(dāng)前QStringBuilder實(shí)現(xiàn)的問題是：它通過嵌套實(shí)現(xiàn)能容納任意數(shù)量字符串的容器。每個QStringBuilder實(shí)例可以恰好包含兩個項(xiàng)，可以是字符串或是其他QStringBuilder實(shí)例。

這意味著QStringBuilder的所有實(shí)例都是一種二叉樹，其中QString是葉節(jié)點(diǎn)。每當(dāng)需要對包含的字符串執(zhí)行某些操作時，QStringBuilder需要處理其左子樹，然后遞歸地處理右子樹。

除了使用二叉樹，我們還可以使用可變參模板（C++ 11引入，設(shè)計QStringBuilder時還沒有）?？勺儏?模板允許我們創(chuàng)建具有任意數(shù)量的模板參數(shù)的類和函數(shù)。

這意味著，通過使用std::tuple（元組，C++11引入的新特性）我們可以創(chuàng)建一個QStringBuilder模板類，包含任意多個字符串：

template <typename... Strings>
class QStringBuilder {
    std::tuple<Strings...> _strings;
};

每當(dāng)獲得一個新的字符串且要添加到QStringBuilder時，我們只需使用std::tuple_cat將兩個元組拼接起來（通過運(yùn)算符%而不是運(yùn)算符+，因?yàn)镼String和QStringBuilder支持此運(yùn)算符）：

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

折疊表達(dá)式

大概思路就是這樣，但問題是我們?nèi)绾翁幚砜勺儏⒛０宓膮?shù)包（即Strings ...）。

 在C++ 17中，我們得到了一個新的結(jié)構(gòu)體，用于處理可變參模板的參數(shù)包，稱為折疊表達(dá)式（Fold expressions）。

折疊表達(dá)式的一般形式如下（運(yùn)算符+可以替換為其他一些二元運(yùn)算符，如*，%等）：

(init + ... + pack)

或者

(pack + ... + init)

第一個變體稱為左折疊表達(dá)式，將操作視為左結(jié)合性（即從左到右優(yōu)先結(jié)合），第二個變體稱為右折疊表達(dá)式，因?yàn)樗鼘⒉僮饕暈橛医Y(jié)合性（即從右到左優(yōu)先結(jié)合）。

如果想使用折疊表達(dá)式拼接模板參數(shù)包中的字符串，可以這樣做：

template <typename... Strings>
auto concatenate(Strings... strings)
{
    return (QString{} + ... + strings);
}

這將首先對初始值QString{}和參數(shù)包的第一個元素調(diào)用運(yùn)算符+。然后，它將根據(jù)上一次調(diào)用的結(jié)果和參數(shù)包的第二個元素調(diào)用運(yùn)算符+。以此類推，直到處理完所有元素都。

聽起來很熟悉，對吧？

可以發(fā)現(xiàn)，它和std::accumulate的行為非常類似。唯一的區(qū)別是std::accumulate算法是處理數(shù)據(jù)的運(yùn)行時序列（向量、數(shù)組、列表等），而折疊表達(dá)式處理的是編譯時序列，即可變參模板的參數(shù)包。

我們可以遵循與std::accumulate相同的步驟來優(yōu)化之前的拼接實(shí)現(xiàn)。首先，我們需要計算所有字符串長度的和。這對于折疊表達(dá)式來說非常簡單：

template <typename... Strings>
auto concatenate(Strings... strings)
{
    const auto totalSize = (0 + ... + strings.length());
    . . .
}

當(dāng)折疊表達(dá)式展開參數(shù)包時，它將得到以下表達(dá)式：

0 + string1.length() + string2.length() + string3.length()

于是，我們得到了結(jié)果字符串的大小?，F(xiàn)在可以繼續(xù)分配一個能夠容納結(jié)果的字符串，并將源字符串逐個追加到該字符串中。

如前所述，折疊表達(dá)式可以與C++的二元運(yùn)算符一起使用。如果想為參數(shù)包中的每個元素執(zhí)行一個函數(shù)，我們可以使用C和C++中最神奇的運(yùn)算符之一：逗號運(yùn)算符。

template <typename... Strings>
auto concatenate(Strings... strings)
{
    const auto totalSize = (0 + ... + strings.length());
    QString result;
    result.reserve(totalSize);

    (result.append(strings), ...);

    return result;
}

以上會為參數(shù)包中的每個字符串調(diào)用append函數(shù)，最后返回拼接完成的字符串。

使用折疊表達(dá)式自定義運(yùn)算符

之前對std::accumulate采用的第二種方式有些復(fù)雜：我們必須提供一個自定義的累加操作函數(shù)。而累計值是目標(biāo)集合中的迭代器，它指向下一個字符串的復(fù)制位置。

如果我們想使用折疊表達(dá)式自定義操作函數(shù)，那么就需要創(chuàng)建一個二元運(yùn)算符。就像我們傳遞給std::accumulate的lambda表達(dá)式一樣，該運(yùn)算符需要獲得一個輸出迭代器和一個字符串，它需要調(diào)用std::copy將字符串內(nèi)容復(fù)制到該迭代器，同時返回一個新的迭代器，該迭代器指向最后復(fù)制的字符之后的元素。

于是，我們重載了操作符<<：

template <typename Dest, typename String>
auto operator<< (Dest dest, const String& string)
{
    return std::copy(string.cbegin(), string.cend(), dest);
}

有了這個操作符，使用折疊表達(dá)式將所有字符串復(fù)制到目標(biāo)緩沖區(qū)就變得非常簡單。初始值是目標(biāo)緩沖區(qū)的初始迭代器，我們將參數(shù)包中的每個字符串傳遞給操作符<<：

template <typename... Strings>
auto concatenate(Strings... strings)
{
    const auto totalSize = (0 + ... + strings.length());
    QString result;
    result.resize(totalSize);

    (result.begin() << ... << strings);

    return result;
}

折疊表達(dá)式和元組

現(xiàn)在，我們知道如何有效地拼接字符串集合，無論是使用向量還是可變模板參數(shù)包。

問題是我們的QStringBuilder兩者都沒用。它將字符串存儲在std::tuple中，既不是可迭代集合，也不是參數(shù)包。

 為了使用折疊表達(dá)式，我們需要參數(shù)包。我們可以創(chuàng)建一個包含從0到n-1的索引列表的參數(shù)包來代替包含字符串的參數(shù)包，稍后我們可以使用std::get來訪問元組內(nèi)部的值。

 通過std::index_sequence很容易創(chuàng)建這個參數(shù)包，該序列表示一個編譯時的整數(shù)列表。我們可以創(chuàng)建一個helper函數(shù)，它以std::index_sequence<Idx…>作為參數(shù)，然后在折疊表達(dá)式中使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;
    }
};

我們只需要創(chuàng)建一個包裝函數(shù)來為元組創(chuàng)建索引序列，然后調(diào)用concatenateHelper函數(shù)：

template <typename... Strings>
class QStringBuilder {
    . . .

    auto concatenate() const
    {
        return concatenateHelper(
            std::index_sequence_for<Strings...>{});
    }
};

總結(jié)

本文只討論了字符串拼接部分的實(shí)現(xiàn)。對于真正的QStringBuilder，還有很多東西，但是細(xì)節(jié)的實(shí)現(xiàn)作為博客文章閱讀來說會變得有點(diǎn)繁瑣。

我們需要小心運(yùn)算符重載：比如像當(dāng)前的QStringBuilder實(shí)現(xiàn)，我們必須使用std::enable_if以使其對Qt中的所有可拼接類型都有效，而且這些操作符不會污染全局命名空間。

還需要用一種安全的方式處理傳遞給字符串拼接過程的臨時變量，就像QStringBuilder只存儲對字符串的引用，對于臨時字符串，這些引用很容易成為懸掛引用。

能夠以更安全的方式處理傳遞給字符串連接的臨時變量也是有益的，因?yàn)镼StringBuilder只存儲對字符串的引用，在臨時字符串的情況下，這些引用很容易成為懸掛引用。

=====================================================

購買Qt正版授權(quán)的朋友可以點(diǎn)擊""哦~~~

掃描關(guān)注慧聚IT微信公眾號，及時獲取最新動態(tài)及最新資訊