Эффективная конкатенация 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)));
    }
};

Свёртка параметров шаблона

Это все хорошо, но вопрос в том, как обрабатывает пакеты свёртка параметров шаблона (fold expression) (часть 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 для доступа к значениям внутри кортежа.

Этот пакет легко создается с помощью the 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 хранит только ссылки на строки, которые в случае временных строк могут легко стать висячими ссылками.