Accumulate c что это
Перейти к содержимому

Accumulate c что это

Веселые старты 2: for_each vs accumulate

Наша цель — понять, насколько можно доверять оптимизацию своего кода компилятору, и можно ли облегчить (осложнить) его задачу?

Почему все одинаково?

Повторим наши замеры (смотри предыдущую статью), попросив компилятор оптимизировать наш код. Чтобы компилятор не увлекся, в код добавим вывод суммы:

Сравним этот результат с результатом for_each:

Варианты с явным циклом дают схожий результат.
Почему скорость после оптимизации стала одинаковой? Для того, чтобы ответить на этот вопрос, давайте заглянем в STL и посмотрим, что из себя представляет функция for_each:

Как видно for_each это и есть цикл, единственная оптимизация — компилятор делает функцию for_each встроенной:

Тут компилятору кажется разумным и лямбду сделать встроенной. Итераторы вектора по своей сути — указатели, поэтому в итоге конечный ассемблерный код выглядит приблизительно так:

Даже если бы я писал код вручную, у меня не получилось бы лучше. Так как программа у нас небольшая и переменных совсем немного, компилятор поместил их в регистры. Никакого лишнего копирования или вызовов функций — превосходно, даже сложение происходит сразу по двум элементам.

Теперь становиться очевидным, почему на скорость конечного кода не влияют “ручные” оптимизации циклов, и даже ключевое слово register.

Всегда ли скорость одинаковая?

Давайте вместо int суммировать простенький классик размером с sizeof(int):

UPDATE. Спасибо 0xd34df00d, kmu1990 за подсказку — оператор += должен возвращать ссылку, но в данном случае это не важно, мы не используем результат оператора.

А его реализацию поместим в отдельный файл.

Теперь вариант с for_each:

Компилируем и запускаем:

Неужели циклы все-таки быстрее? На самом деле — нет, просто корректный вариант с for_each теперь должен выглядеть так:

Дело в том, что компилятор не имеет право просто убрать копирование аргумента, так как он не знает, какие добрые дела мы творим в написанном нами операторе копирования.

Скорость работы for_each сравнялась со скоростью цикла, а вот вариант с accumulate:

Почему так? Посмотрим на ассемблерный код варианта с for_each:

И сравним его с кодом варианта с accumulate:

Все из-за того, что компилятор из оператора «+ cpp»>template<typename _InputIterator, typename _Tp> accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)

Отсюда и лишние операции перемещения.
Кстати, вам не кажется странным тот факт, что специализированная функция для подсчета суммы дает худший результат, чем цикл или использование for_each?

Вывод

Компилятор не на столько умен, как человек. И достаточно легкого изменения кода, чтобы компилятор запутался и выдал нам не совсем то, что мы бы хотели или ожидали.

Если мы хотим получить гарантированный результат — нужно все делать “самому”, либо каждый раз проверять, что там компилятор улучшил, а что — ухудшил. Стандартом не гарантируется, что for_each будет оптимизирована так же хорошо, как и цикл, а это важно, если вы пишете переносимый код.

Если же скорость работы не критична — всегда выбирайте STL. Код получается более читабельным, и в среднем код на STL работает быстрее.

Функции <numeric>

Вычисляет сумму всех элементов в указанном диапазоне, включая некоторое начальное значение, вычисляя последовательные частичные суммы. Или вычисляет результат последовательных частичных результатов указанной двоичной операции.

Параметры

first
Входной итератор, адресующий первый элемент в диапазоне для суммирования или объединения с помощью binary_op.

last
Входной итератор, адресующий последний элемент в диапазоне для суммирования или объединения с помощью binary_op, это одна позиция за последним элементом, фактически включенным в итерированное накопление.

init
Начальное значение, к которому каждый элемент, в свою очередь, добавляется или объединяется с помощью binary_op.

binary_op
Двоичная операция, применяемая к каждому элементу в указанном диапазоне и результату предыдущих приложений.

Возвращаемое значение

Сумма инициализации и всех элементов в указанном диапазоне для первой функции шаблона или, для второй функции шаблона, результат применения двоичной операции binary_op вместо операции суммы (*PartialResult, in_iter), где PartialResult является результатом предыдущих приложений операции и in_iter является итератором, указывающим на следующий элемент в диапазоне.

Remarks

Начальное значение гарантирует наличие четко определенного результата, если диапазон пуст, в этом случае возвращается инициализация . Двоичная операция не должна быть ассоциативной или коммутативной. Результат инициализируется в инициализацию начального значения, а затем результат = binary_op(результат, in_iter) вычисляется итеративно по диапазону, где in_iter является итератором, указывающим на каждый последовательный элемент в диапазоне. Диапазон должен быть допустимым, а сложность линейной с размером диапазона. Возвращаемый тип бинарного оператора должен поддерживать преобразование в Type, чтобы гарантировать закрытие в ходе перебора.

Пример

adjacent_difference

Вычисляет последовательные различия между каждым элементом и его предшественником во входном диапазоне. Выводит результаты в диапазон назначения. Или вычисляет результат обобщенной процедуры, в которой операция разности заменяется другой указанной двоичной операцией.

Параметры

exec
Политика выполнения.

first
Итератор ввода, обращающийся к первому элементу в диапазоне ввода, элементы которого необходимо отличить от соответствующих им предшественников или где с парой значений должна быть выполнена другая заданная бинарная операция.

last
Итератор ввода, обращающийся к последнему элементу в диапазоне ввода, элементы которого необходимо отличить от соответствующих им предшественников или где с парой значений должна быть выполнена другая заданная бинарная операция.

result
Итератор вывода, обращающийся к первому элементу в диапазоне назначения, где необходимо сохранить ряд различий или результаты определенной операции.

binary_op
Двоичная операция, применяемая в обобщенной операции, заменив операцию вычитания в процедуре разных выражений.

Возвращаемое значение

Выходной итератор, адресующий конец диапазона назначения: result + ( — last first ).

Remarks

Результат итератора вывода может быть тем же итератором, что adjacent_difference и входной итератор первым, чтобы значения могли быть вычислены на месте.

Для последовательности значений a1, a2, a3 в входном диапазоне первая функция шаблона сохраняет последовательные adjacent_difference значения a1, a2a1, a3 — a2, в диапазоне назначения.

Для последовательности значений a1, a2, a3 во входном диапазоне вторая функция шаблона сохраняет последовательные adjacent_difference значения a1, a2binary_opa1, a3binary_opa2 в диапазоне назначения.

Двоичная операция binary_op не обязательно должна быть ассоциативной или коммутативной, так как указан порядок применения операций.

Пример

exclusive_scan

Вычисляет операцию суммирования монопольных префиксов с помощью заданного std::plus<>() двоичного оператора по диапазону с учетом начального значения. Записывает результаты в диапазон, начиная с указанного места назначения. Монопольная сумма префикса означает, что входной элемент nth не включен в nth sum. Перегрузки, включающие аргумент политики выполнения, выполняются в соответствии с указанной политикой.

Параметры

exec
Политика выполнения.

first
Входной итератор, адресующий первый элемент в диапазоне для суммирования или объединения с помощью binary_op.

last
Входной итератор, адресующий последний элемент в диапазоне для суммирования или объединения с помощью binary_op, это одна позиция за последним элементом, фактически включенным в итерированное накопление.

result
Выходной итератор, адресующий первый элемент диапазона назначения, в котором должны храниться ряд сумм или результаты указанной операции.

init
Начальное значение, к которому каждый элемент, в свою очередь, добавляется или объединяется с помощью binary_op.

binary_op
Двоичная операция, применяемая к каждому элементу в указанном диапазоне и результату предыдущих приложений.

Возвращаемое значение

Выходной итератор, адресующий конец диапазона назначения: result + (lastfirst — ).

Вычисляет наибольший общий делитель целых чисел m и n.

Параметры

m, n
Значения целочисленного типа.

Возвращаемое значение

Возвращает наибольший общий делитель абсолютных значений m и n, или ноль, если оба значения m и n равны нулю. Результаты не определены, если абсолютные значения m или n не представляются в качестве значений типа common_type_t<M,N> .

inclusive_scan

Вычисляет инклюзивную операцию суммирования префиксов с помощью любого std::plus<>() или указанного двоичного оператора по диапазону с учетом начального значения. Записывает результаты в диапазон, начиная с указанного места назначения. Инклюзивная сумма префикса означает, что входной элемент nth включается в nth sum. Перегрузки, включающие аргумент политики выполнения, выполняются в соответствии с указанной политикой.

Параметры

exec
Политика выполнения.

first
Входной итератор, адресующий первый элемент в диапазоне для суммирования или объединения с помощью binary_op.

last
Входной итератор, адресующий последний элемент в диапазоне для суммирования или объединения с помощью binary_op, это одна позиция за последним элементом, фактически включенным в итерированное накопление.

result
Выходной итератор, адресующий первый элемент диапазона назначения, в котором должны храниться ряд сумм или результаты указанной операции.

init
Начальное значение, к которому каждый элемент, в свою очередь, добавляется или объединяется с помощью binary_op.

binary_op
Двоичная операция, применяемая к каждому элементу в указанном диапазоне и результату предыдущих приложений.

Возвращаемое значение

Выходной итератор, адресующий конец диапазона назначения: result + (lastfirst — ).

inner_product

Вычисляет сумму поэлементного умножения двух диапазонов и добавляет ее к указанному начальному значению либо вычисляет результат обобщенной процедуры, где бинарные операции суммы и умножения заменены на другие указанные бинарные операции.

Параметры

first1
Входной итератор, адресующий первый элемент в первом диапазоне, для которого нужно вычислить внутреннее произведение или обобщенное внутреннее произведение со вторым диапазоном.

last1
Входной итератор, адресующий последний элемент в первом диапазоне, для которого нужно вычислить внутреннее произведение или обобщенное внутреннее произведение со вторым диапазоном.

first2
Входной итератор, адресующий первый элемент во втором диапазоне, для которого нужно вычислить внутреннее произведение или обобщенное внутреннее произведение с первым диапазоном.

init
Начальное значение, к которому прибавляется внутреннее произведение или обобщенное внутреннее произведение диапазонов.

binary_op1
Бинарная операция, которая заменяет операцию внутреннего произведения суммирования, применяемую к поэлементным произведениям в обобщении внутреннего произведения.

binary_op2
Бинарная операция, которая заменяет операцию внутреннего поэлементного произведения умножения в обобщении внутреннего произведения.

Возвращаемое значение

Первая функция-член возвращает сумму поэлементного произведения и добавляет к ней указанное начальное значение. Таким образом, для диапазонов значений ai и bi она возвращает:

путем итеративной замены инициализации на инициализацию + (ai * bi).

Вторая функция-член возвращает:

путем итеративной замены инициализации на инициализациюbinary_op1 (aibinary_op2bi).

Remarks

Начальное значение гарантирует наличие четко определенного результата, если диапазон пуст. В этом случае возвращается инициализация . Двоичные операции не должны быть ассоциативными или коммутативными. Диапазон должен быть допустимым, а сложность линейной с размером диапазона. Возвращаемый тип бинарного оператора должен поддерживать преобразование в Type, чтобы гарантировать закрытие в ходе перебора.

Пример

Сохраняет начальное значение, начиная с первого элемента и заполняя последовательными приращениями этого значения ( value++ ) в каждом из элементов интервала [first, last) .

Параметры

first
Входной итератор, адресующий первый элемент в диапазоне для заполнения.

last
Входной итератор, адресующий последний элемент в диапазоне для заполнения.

value
Начальное значение для хранения в первом элементе и последующее увеличение для последующих элементов.

Пример

Следующий пример показывает некоторые способы использования функции iota заполнением списка целых чисел, а затем заполнением вектора list , так что можно будет использовать функцию random_shuffle.

partial_sum

Вычисляет ряд сумм в входном диапазоне от первого элемента через n-й элемент и сохраняет результат каждой такой суммы в N-м элементе диапазона назначения. Или вычисляет результат обобщенной процедуры, в которой операция суммы заменяется другой указанной двоичной операцией.

Параметры

first
Итератор ввода, обращающийся к первому элементу в диапазоне, который необходимо частично суммировать или объединить в соответствии с заданной бинарной операцией.

last
Итератор ввода, обращающийся к последнему элементу в диапазоне, который необходимо частично суммировать или объединить в соответствии с указанной бинарной операцией, который расположен на одну позицию далее за последним элементом, фактически включенным в совокупности, в которой проводятся итерации.

result
Выходной итератор, адресующий первый элемент диапазона назначения для хранения ряда частичных сумм или последовательных результатов указанной двоичной операции.

binary_op
Двоичная операция, применяемая в обобщенной операции, заменяя операцию суммы в процедуре частичной суммы.

Возвращаемое значение

Выходной итератор, адресующий конец диапазона назначения: результат + (lastfirst — ).

Remarks

Результат выходного итератора может быть тем же итератором , что и первый входной итератор, чтобы частичные суммы можно было вычислить на месте.

Для последовательности значений a1, a2, . ax в входном диапазоне первая функция шаблона сохраняет последовательные частичные суммы в целевом диапазоне. N-й элемент задается (a1 + a2 + a3 + . + an).

Для последовательности значений a1, a2, a3, во входном диапазоне вторая функция шаблона сохраняет последовательные частичные результаты в диапазоне назначения. N-й элемент присваивается ((. ((a1binary_opa2) binary_opa3) binary_op . ) binary_opan).

Двоичная операция binary_op не обязательно должна быть ассоциативной или коммутативной, так как указан порядок примененных операций.

Пример

reduce

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

Параметры

exec
Политика выполнения.

first
Входной итератор, обращающийся к первому элементу в диапазоне для суммирования или объединения с помощью binary_op.

last
Входной итератор, обращающийся к последнему элементу в диапазоне для суммирования или объединения с помощью binary_op, это одна позиция за последним элементом, фактически включенным в итерированное накопление.

result
Выходной итератор, указывающий на первый элемент диапазон назначения, в котором должны храниться ряд сумм или результаты указанной операции.

init
Начальное значение, к которому каждый элемент, в свою очередь, добавляется или объединяется с помощью binary_op.

binary_op
Двоичная операция, применяемая к каждому элементу в указанном диапазоне и результату предыдущих приложений.

Возвращаемое значение

Результат применения binary_op или std::plus<>() инициализации и всех элементов в указанном диапазоне (*PartialResult, in_iter), где PartialResult является результатом предыдущих приложений операции, а in_iter — итератор, указывающий на некоторый элемент в диапазоне. В перегрузках, которые не указывают инициализацию, используемое значение инициализации эквивалентно typename iterator_traits<InputIterator>::value_type .

Remarks

reduce поведение недетерминировано, если binary_op не является ассоциативным и коммутативным. Поведение не определено, если binary_op изменяет любой элемент или делает недействительным любой итератор в интервале [первый, последний], включительно.

transform_exclusive_scan

Преобразует элементы диапазона с указанным унарным оператором, а затем вычисляет монопольную операцию суммы префикса с помощью либо std::plus<>() указанного двоичного оператора по диапазону, учитывая начальное значение. Записывает результаты в диапазон, начиная с указанного назначения. Монопольная сумма префикса означает, что входной элемент nth не включен в nth sum. Перегрузки, включающие аргумент политики выполнения, выполняются в соответствии с указанной политикой. Суммирование может выполняться в произвольном порядке.

Параметры

exec
Политика выполнения.

first
Входной итератор, обращающийся к первому элементу в диапазоне для суммирования или объединения с помощью binary_op.

last
Входной итератор, обращающийся к последнему элементу в диапазоне для суммирования или объединения с помощью binary_op, это одна позиция за последним элементом, фактически включенным в итерированное накопление.

result
Выходной итератор, указывающий на первый элемент диапазон назначения, в котором должны храниться ряд сумм или результаты указанной операции.

init
Начальное значение, к которому каждый элемент, в свою очередь, добавляется или объединяется с помощью binary_op.

binary_op
Двоичная операция, применяемая к каждому элементу в указанном диапазоне и результату предыдущих приложений.

unary_op
Унарная операция, применяемая к каждому элементу в указанном диапазоне.

transform_inclusive_scan

Преобразует элементы диапазона с указанным унарным оператором, а затем вычисляет операцию суммы включаемых префиксов с помощью любого std::plus<>() или указанного двоичного оператора по диапазону с учетом начального значения. Записывает результаты в диапазон, начиная с указанного места назначения. Инклюзивная сумма префикса означает, что входной элемент nth включается в nth sum. Перегрузки, включающие аргумент политики выполнения, выполняются в соответствии с указанной политикой. Суммирование может выполняться в произвольном порядке.

Параметры

exec
Политика выполнения.

first
Входной итератор, адресующий первый элемент в диапазоне для суммирования или объединения с помощью binary_op.

last
Входной итератор, адресующий последний элемент в диапазоне для суммирования или объединения с помощью binary_op, это одна позиция за последним элементом, фактически включенным в итерированное накопление.

result
Выходной итератор, адресующий первый элемент диапазона назначения, в котором должны храниться ряд сумм или результаты указанной операции.

binary_op
Двоичная операция, применяемая к каждому элементу в указанном диапазоне и результату предыдущих приложений.

unary_op
Унарная операция, применяемая к каждому элементу в указанном диапазоне.

init
Начальное значение, к которому каждый элемент, в свою очередь, добавляется или объединяется с помощью binary_op.

transform_reduce

Преобразует диапазон элементов, а затем применяет фанктор, который уменьшает преобразованные элементы в произвольном порядке. Фактически, за transform которым следует . reduce

Параметры

exec
Политика выполнения.

first
Входной итератор, адресующий первый элемент в диапазоне для суммирования или объединения с помощью binary_op.

first1
Входной итератор, адресующий первый элемент в диапазоне для суммирования или объединения с помощью binary_op1.

last
Входной итератор, адресующий последний элемент в диапазоне для суммирования или объединения с помощью binary_op, это одна позиция за последним элементом, фактически включенным в итерированное накопление.

last1
Входной итератор, адресующий последний элемент в диапазоне для суммирования или объединения с помощью binary_op1, это одна позиция за последним элементом, фактически включенным в итерированное накопление.

result
Выходной итератор, адресующий первый элемент диапазона назначения, в котором должны храниться ряд сумм или результаты указанной операции.

init
Начальное значение, к которому каждый элемент, в свою очередь, добавляется или объединяется с помощью binary_op.

binary_op
Двоичная операция, применяемая к каждому элементу в указанном диапазоне и результату предыдущих приложений.

unary_op
Унарная операция, применяемая к каждому элементу в указанном диапазоне.

Эффективная конкатенация QString со свёрткой параметров шаблона C++17

В C++ привычно иметь operator+to perform string concatenation (оператор+выполнение конкатенации строк), независимо от того, используется ли стандартная библиотека (или STL) или Qt. Это позволяет писать такие вещи, как следующий фрагмент:

Но это имеет большой недостаток — ненужное создание временных промежуточных результатов. А именно, в предыдущем примере есть одна временная строка для хранения результата оператора + и пустой части выражения, затем эта строка объединяется с числом, которое возвращает другую временную строку. Затем вторая временная строка соединяется с точкой, что дает окончательный результат, после которого временные уничтожаются.

Это означает, что есть почти столько же ненужных распределений и откреплений, сколько имеется обращений к operator+ (оператору+). Кроме того, копируются одни и те же данные несколько раз. Например, содержимое строки оператора сначала копируется в первый временный объект, затем копируется из первого временного объекта во второй, а затем из второго временного объекта в конечный результат.

  1. 1. Алгоритм std::accumulate
  2. 2. Шаблоны рекурсивных выражений
  3. 3. Шаблоны с переменным числом аргументов
  4. 4. Свёртка параметров шаблона
  5. 5. Пользовательские операторы со свёртками параметров шаблона
  6. 6. Свёртка параметров шаблона и кортежи
  7. 7. Заключение

Это может быть реализовано намного более эффективным способом, создав экземпляр строки, который предварительно выделяет память, необходимую для сохранения конечного результата, и затем последовательно вызывает функцию QString::appendmember для добавления каждой из строк, которые хотим объединить по одной:

В качестве альтернативы, можно было бы использовать 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 конкатенация строк будет выглядеть так:

Алгоритм делает то, что вы ожидаете в этом примере — он начинается с пустой строки QString и добавляет к ней каждую строку из вектора, создавая таким образом конкатенированную строку.

Это было бы так же неэффективно, как в первоначальном примере использования operator+ для конкатенации, так как std::accumulate использует operator+ внутри по умолчанию.

Чтобы оптимизировать эту реализацию, как в предыдущем разделе, можно просто использовать std::accumulate, чтобы вычислить размер результирующей строки, вместо того, чтобы выполнить полную конкатенацию с ней:

На этот раз std::accumulate начинается с начального значения 0 и для каждой строки в векторе строк, он добавляет длину к этому начальному значению и, наконец, возвращает сумму длин всех строк в векторе.

Это то, что для большинства людей означает std::accumulate — суммирование некоторого вида . Но это довольно упрощенный взгляд.

В первом примере действительно суммировались все строки в векторе . Но второй пример немного другой. На самом деле элементы вектора не суммируются. Вектор содержит QStrings и добавляются целые числа.

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

Как видно из предыдущего фрагмента кода, аккумулятор не должен быть того же типа, что и значения в векторе. Имелся вектор строк, а аккумулятор был целым числом.

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

Это означает, что если скопировать данные одной исходной строки в строку назначения, используя std::copy, то получим итератор, указывающий на точное местоположение, куда нужно скопировать данные второй строки.

Итак, есть функция, которая принимает строку (как пара итераторов) и один выходной итератор и впоследствии дает новый выходной итератор. Это похоже на то, что можно использовать в качестве операции для std::accumulate для реализации эффективной конкатенации строк:

Первый вызов std::copy скопирует первую строку в место назначения, определенное в result.begin(). Он вернет итератор в строку результатов сразу после последнего скопированного символа, и именно туда будет скопирована вторая строка из вектора. После этого будет скопирована третья строка и так далее.


Временные переменные

В конце получаем конкатенированную строку.

Шаблоны рекурсивных выражений

Теперь можно вернуться к эффективной конкатенации строк, используя operator+ в Qt.

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

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

Фактически, это именно то, что Qt делает с 4.6, если вы активируете быструю конкатенацию строк. Вместо возврата QString operator+ вернет экземпляр скрытого шаблона класса называемого QStringBuilder. Шаблон QStringBuilderclass — это просто фиктивный тип, который содержит ссылки на аргументы, передаваемые operator+.

Более сложная версия следующего:

Когда вы объединяете несколько строк, вы получаете более сложный тип, в котором несколько QStringBuilders вложены друг в друга. Что-то вроде этого:

Этот тип просто сложный способ сказать: «Я держу четыре строки, которые должны быть объединены».

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

По сути, он будет делать то же самое, что делалось ранее, но это будет сделано автоматически, без необходимости «поднимать палец».

Шаблоны с переменным числом аргументов

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

Это означает, что все экземпляры QStringBuilder являются своего рода двоичным деревом, в котором QString являются конечными узлами. Всякий раз, когда нужно что-то делать с содержащимися строками, QStringBuilder должен обрабатывать свое левое поддерево, а затем правое поддерево рекурсивно.

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

Это означает, что с помощью std::tuplewe можно создать шаблон класса QStringBuilder, который содержит столько строк, сколько хочется:

Когда получим новую строку для добавления в QStringBuilder, можно просто добавить его в кортеж, используя std::tuple_cat, который объединяет два кортежа (будем использовать operator% вместо operator+, так как этот оператор также поддерживается QStringand QStringBuilder):

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

Это все хорошо, но вопрос в том, как обрабатывает пакеты свёртка параметров шаблона (fold expression) (часть Strings).

С C++17 получили новую конструкцию для обработки пакетов параметров, называемую свёртка параметров шаблона.

Общая форма свёртки параметров шаблона выглядит следующим образом (operator+ можно заменить другим бинарным оператором, таким как *, %…):

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

Если бы желали объединить строки в пакете параметров шаблона с помощью свёртки параметров шаблона, можно было бы сделать это так:

Сначала будет вызван operator+ для начального значения QString и первого элемента пакета параметров. Затем он вызовет operator+ для результата предыдущего вызова и второй элемент пакета параметров. И так до тех пор, пока все элементы не будут обработаны.

Звучит знакомо, не правда ли?

То же самое поведение видели с std::accumulate. Единственное отличие состоит в том, что алгоритм std::accumulate работает с последовательностями данных во время выполнения (векторами, массивами, списками и т. д.). В то время, как свёртки параметров шаблона работают с последовательностями времени компиляции, то есть с пакетами параметров шаблона с переменным числом аргументов.

Можно выполнить те же шаги для оптимизации предыдущей реализации конкатенации, которую использовали для std::accumulate. Сначала нужно вычислить сумму всех длин строк. Это довольно просто с свёрткой параметров шаблона:

Когда свёртка параметров шаблона расширяет пакет параметров, оно получит следующее выражение:

Итак, получили размер результативной строки. Теперь можно перейти к выделению строки, достаточно большой для результата, и добавить к ней исходные строки одну за другой.

Как упоминалось ранее, свёртка параметров шаблона работает с бинарными операторами C++. Если хотим выполнить функцию для каждого элемента в пакете параметров, можно использовать один из самых странных операторов в C и C++ — оператор многоточия (comma operator).

Это вызовет добавление для каждой из строк в пакете параметров, давая, в итоге, объединенную строку.

Пользовательские операторы со свёртками параметров шаблона

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

Если хотим иметь пользовательскую операцию со свёртками параметров шаблона, нужно создать бинарный оператор. Оператору, так же как lambda (лямбда), который передали в std::accumulate, нужно взять один выходной итератор и одну строку, ему нужно вызвать std::copy, чтобы скопировать строковые данные в этот итератор, и он должен вернуть новый итератор указывая на элемент после последнего скопированного символа.

Для этого можно переопределить оператор <<:

С этим осуществленной свёрткой параметров шаблона, которая копирует все строки в буфер назначения это становится довольно простым. Начальным значением является начальный итератор целевого буфера, и <<каждую из строк в пакете параметров к нему:

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

Теперь известно, как эффективно объединить коллекцию строк — будь то векторный или пакет параметров с переменным числом элементов.

Проблема в том, что QStringBuilder этого также не имеет. Он хранит строки внутри std::tuple, который не является ни повторяемой коллекцией, ни пакетом параметров.

Для работы со свёрткой параметров шаблона нужны пакеты параметров. Вместо пакета параметров, содержащего строки, можно создать пакет, содержащий список индексов от 0 до n-1, который можно позже использовать с std::getto для доступа к значениям внутри кортежа.

Этот пакет легко создается с помощью the std::index_sequence, который представляет список целых чисел во время компиляции. Можно создать вспомогательную функцию, которая будет принимать std::index_sequence в качестве аргумента, а затем использовать std::get (_strings) для доступа к строкам из кортежа одна за другой из сверток параметра шаблона.

Нужно создать функцию-обертку, которая создает индексную последовательность для кортежа, и вызвать функцию c concatenateHelper:

Заключение

Эта статья посвящена только фактической конкатенации строк. Чтобы применить это к реальному QStringBuilder, понадобится еще несколько вещей, и реализация станет немного подавляющей для чтения в виде статьи в блоге.

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

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

Добавить комментарий

Ваш адрес email не будет опубликован.