Ефективна конкатенація QString зі згорткою параметрів шаблону C++17

qt, QString, expression

У C++ зазвичай мати operator+to perform string concatenation (оператор+виконання конкатенації рядків), незалежно від того, чи використовується стандартна бібліотека (або STL) або Qt. Це дозволяє писати такі речі, як наступний фрагмент:

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

Але це має велику ваду - непотрібне створення тимчасових проміжних результатів. А саме, у попередньому прикладі є один часовий рядок для зберігання результату оператора + і порожній частині виразу, потім цей рядок поєднується з числом, яке повертає інший часовий рядок. Потім другий тимчасовий рядок з'єднується з точкою, що дає остаточний результат, після якого тимчасові знищуються.

Це означає, що є майже стільки ж непотрібних розподілів та відкріплень, скільки є звернень до operator+ (оператора+). Крім того, копіюються ті самі дані кілька разів. Наприклад, вміст рядка оператора спочатку копіюється в перший тимчасовий об'єкт, потім копіюється з першого тимчасового об'єкта в другий, а потім другого тимчасового об'єкта в кінцевий результат.

Тимчасові змінні

Це може бути реалізовано набагато більш ефективним способом, створивши екземпляр рядка, який попередньо виділяє пам'ять, необхідну для збереження кінцевого результату, а потім послідовно викликає функцію QString::appendmember для додавання кожного з рядків, які хочемо об'єднати по одному:

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::resizeinstead з QString::reserve, а потім використовувати std::copy(or std::memcpy), щоб скопіювати в нього дані (пізніше стане видно, як використовувати std::copy для конкатенації рядків). Це, ймовірно, трохи підвищить продуктивність (залежить від оптимізації компілятора), тому що QString::append повинен перевірити, чи достатньо ємності рядка, щоб вмістити отриманий рядок. std::copyalgorithm не має цієї непотрібної додаткової перевірки, яка може дати йому невелику перевагу.

Обидва ці підходи значно ефективніші, ніж використання operator+ (оператора+), але було б прикро писати такий код щоразу, коли хочеться об'єднати кілька рядків.

Алгоритм std::accumulate

Перш ніж продовжити те, як Qt вирішує цю проблему зараз, і можливий спосіб покращити її в Qt 6 за допомогою чудових функцій, які отримали в C++17, потрібно розглянути один з найважливіших і потужних алгоритмів зі стандартної бібліотеки - алгоритм std: :accumulate .

Уявіть, що дана послідовність (наприклад, aQVector) рядків, які хочемо об'єднати замість того, щоб мати їх в окремих змінних.

З std::accumulate конкатенація рядків виглядатиме так:

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

Алгоритм робить те, що ви очікуєте в цьому прикладі - він починається з порожнього рядка QString і додає до нього кожен рядок вектора, створюючи таким чином конкатенований рядок.

Це було б так само неефективно, як у початковому прикладі використання operator+ для конкатенації, оскільки std::accumulate використовує operator+ всередині за промовчанням.

Щоб оптимізувати цю реалізацію, як у попередньому розділі, можна просто використовувати 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 - підсумовування деякого виду. Але це досить спрощений погляд.

У першому прикладі дійсно підсумовувалися всі рядки у векторі. Але другий приклад трохи інший. Насправді елементи вектора не підсумовуються. Вектор містить QStrings і додають цілі числа.

Сила std::accumulate у тому, що можна передати йому користувальницьку операцію. Операція приймає раніше накопичене значення і один елемент вихідної колекції, і генерує нове накопичене значення. Вперше, коли std::accumulate викликав цю операцію, він передасть йому початкове значення як акумулятор і перший елемент колекції джерела. Він візьме результат і передасть наступному виклику операції разом з другим елементом вихідної колекції. Це повторюватиметься доти, доки вся вихідна колекція не буде оброблена, і алгоритм поверне результат останнього виклику операції.

Як видно з попереднього фрагмента коду, акумулятор не повинен бути такого самого типу, що і значення у векторі. Був вектор рядків, а акумулятор був цілим числом.

Вищезгаданий алгоритм std::copy приймає послідовність елементів, які мають бути скопійовані (як пара вхідних ітераторів), та місце призначення (як вихідний ітератор), куди мають бути скопійовані елементи. Він повертає ітератор, що вказує на елемент після останнього скопійованого елемента в цільову колекцію.

Це означає, що якщо скопіювати дані одного вихідного рядка в рядок призначення, використовуючи std::copy, то отримаємо ітератор, що вказує на точне місцезнаходження, куди потрібно скопіювати дані другого рядка.

Отже, є функція, яка приймає рядок (як пара ітераторів) і один вихідний ітератор і дає новий вихідний ітератор. Це схоже на те, що можна використовувати як операцію для 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(). Він поверне ітератор у рядок результатів відразу після останнього скопійованого символу, і саме туди буде скопійовано другий рядок із вектора. Після цього буде скопійовано третій рядок і таке інше.

Тимчасові змінні

Наприкінці отримуємо конкатенований рядок.

Шаблони рекурсивних виразів

Тепер можна повернутися до ефективної конкатенації рядків, використовуючи operator+ Qt.

QString result = statement + space + number + period;

Видно, що проблема з конкатенацією рядків випливає з того факту, що C++ оцінює попередній вираз поетапно, викликаючи operator+ кілька разів, коли кожен виклик повертає новий екземпляр QString.

Хоча неможливо змінити спосіб оцінки цього C++, можна використовувати техніку, звану expression templates (шаблонами виразів), для затримки фактичного обчислення результуючого рядка до тих пір, поки не буде визначено все вираз. Це можна зробити, змінивши повертаний тип operator+ не на QString, а на деякий тип користувача, який просто зберігає рядки, які повинні бути об'єднані без фактичного виконання об'єднання.

Фактично це саме те, що Qt робить з 4.6, якщо ви активуєте швидку конкатенацію рядків. Замість повернення QString operator+ поверне екземпляр прихованого шаблону класу QStringBuilder. QStringBuilderclass - це просто фіктивний тип, який містить посилання на аргументи, що передаються operator+.

Більш складна версія наступного:

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

Коли ви об'єднуєте кілька рядків, ви отримуєте складніший тип, в якому кілька QStringBuilders вкладені один в одного. Щось на зразок цього:

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

Цей тип є просто складним способом сказати: «Я тримаю чотири рядки, які повинні бути об'єднані».

Коли запитуємо перетворення QStringBuilder в QString (наприклад, привласнюючи його результату QString), він спочатку обчислює загальний розмір всіх рядків, що містяться, потім виділяє QStringinstance цього розміру і, нарешті, скопіює рядки один за одним в результуючий рядок.

По суті, він робитиме те саме, що робилося раніше, але це буде зроблено автоматично, без необхідності «піднімати палець».

Шаблони зі змінною кількістю аргументів

Проблема з поточною реалізацією QStringBuilder полягає в тому, що він реалізує контейнер із довільним числом рядків за допомогою вкладення. Кожен екземпляр QStringBuilder може містити рівно два елементи, будь то рядки або інші екземпляри QStringBuilder.

Це означає, що всі екземпляри QStringBuilder є своєрідним двійковим деревом, в якому QString є кінцевими вузлами. Щоразу, коли потрібно щось робити з рядками, що містяться, QStringBuilder повинен обробляти своє ліве піддерево, а потім праве піддерево рекурсивно.

Замість того, щоб створювати бінарні дерева, можна використовувати шаблони зі змінною кількістю аргументів (доступно з C++11, яке не було доступне під час створення QStringBuilder). Шаблони зі змінним числом аргументів дозволяють створювати класи та функції з довільним числом аргументів шаблону.

Це означає, що за допомогою std::tuplewe можна створити шаблон класу QStringBuilder, який містить стільки рядків, скільки хочеться:

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

Коли отримаємо новий рядок для додавання в QStringBuilder, можна просто додати його в кортеж, використовуючи std::tuple_cat, який об'єднує два кортежі (використовуватимемо operator% замість operator+, тому що цей оператор також підтримується QStringand 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 отримали нову конструкцію для обробки пакетів параметрів, звану згортка параметрів шаблону.

Загальна форма згортки параметрів шаблону виглядає так (operator+ можна замінити іншим бінарним оператором, таким як *, %…):

(init + ... + pack)

або:

(pack + ... + init)

Перший варіант називається ліва згортка параметрів шаблону (left fold expression) , обробляє операцію, як left-associative (асоціативну зліва), а другий варіант називається права згортка параметрів шаблону (right fold expression) , оскільки він обробляє операцію, як right -Associative (асоціативну справа).

Якби хотіли об'єднати рядки в пакеті параметрів шаблону за допомогою згортки параметрів шаблону, можна було б зробити так:

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

Спочатку буде викликаний operator+ для початкового значення QString {} та першого елемента пакета параметрів. Потім він викличе operator+ для результату попереднього дзвінка та другий елемент пакета параметрів. І так доти, доки всі елементи не будуть оброблені.

Звучить знайомо, чи не так?

Те саме поведінка бачили з 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++ - оператор крапки (comma operator).

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

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

    return result;
}

Це викликає додавання для кожного рядка в пакеті параметрів, даючи, в результаті, об'єднаний рядок.

Оператори користувача зі згортками параметрів шаблону

Другий підхід, який використовувався з std::accumulate, був трохи складнішим. Потрібно було надати користувальницьку операцію для накопичення. Акумулятор (накопичувальний суматор) був ітератором цільової колекції, який позначав, куди необхідно скопіювати наступний рядок.

Якщо хочемо мати користувальницьку операцію зі згортками параметрів шаблону, потрібно створити бінарний оператор. Оператору, так само як lambda (лямбда), який передали в std::accumulate, потрібно взяти один вихідний ітератор та один рядок, йому потрібно викликати 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::getto для доступу до значень усередині кортежу.

Цей пакет легко створюється за допомогою std::index_sequence, який представляє список цілих чисел під час компіляції. Можна створити допоміжну функцію, яка прийматиме std::index_sequence як аргумент, а потім використовувати std::get (_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;
    }
};

Потрібно створити функцію-обгортку, яка створює індексну послідовність для кортежу, і викликати функцію c concatenateHelper:

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

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

Висновок

Ця стаття присвячена лише фактичній конкатенації рядків. Щоб застосувати це до реального QStringBuilder, знадобиться ще кілька речей, і реалізація стане трохи переважною для читання у вигляді статті у блозі.

Необхідно бути обережними з навантаженням операторів. Потрібно було б використовувати std::enable_iflike, як поточну реалізацію QStringBuilder, щоб вона працювала з усіма типами Qt, що конкатенуються, і не псувала глобальний простір цими операторами.

Також було б корисно мати можливість обробляти тимчасові значення, що передаються в конкатенацію рядків, безпечнішим способом, оскільки QStringBuilder зберігає лише посилання на рядки, які у разі тимчасових рядків можуть легко стати висящими посиланнями.