std::transform inclusive scan in C++
The Standard Library (std) in contemporary C++ offers a variety of algorithms to carry out tasks quickly and effectively. Std::transform_inclusive_scan is one such technique that provides a strong tool for inclusive prefix scans with transformations. In this article, we will examine the syntax, application, and real-world examples of std::transform_inclusive_scan.
A potent method in the C++ Standard Template Library (STL) called std::transform_inclusive_scan completes two crucial tasks in one go:
- Transformation: It transforms each element in an input range by applying a user-defined unary function (unary_op).
- All-inclusive Prefix total: All converted elements up to and including that point in the input range are added together to provide a cumulative total for each element in the output range.
Syntax:
It has the following syntax:
template <class InputIterator, class OutputIterator,
class BinaryOperation, class UnaryOperation>
OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
OutputIterator d_first, BinaryOperation binary_op,
UnaryOperation unary_op, T init = T());
- InputIterator: Bidirectional iterator type for the input range ([first, last)) from which elements are read.
- OutputIterator: Output iterator type for the destination range ([d_first, ...)), where the transformed and summed elements are written.
- BinaryOperation: Function object (functor or lambda) that defines the binary operation (binary_op) used for the cumulative summation. It takes two arguments (typically the previous sum and the current transformed element) and returns their sum.
- UnaryOperation: Function object (unary_op) applied to each element in the input range to produce transformed elements.
- T: Optional initial value (init) for the cumulative sum. Defaults to the value type of the transformed elements if not specified.
Example: Calculating Cumulative Sums of Squares
Let's consider a vector of integers data and demonstrate how to calculate the cumulative sum of squares:
#include <iostream>
#include <vector>
#include <numeric> // for std::iota
int main() {
std::vector<int> data = {1, 2, 3, 4, 5}; // Input data
std::vector<int> squares(data.size()); // Output vector to store squares
// Unary operation to square each element
auto square = [](int x) { return x * x; };
// Binary operation to add squares (can also use std::plus<>)
auto add_squares = [](int a, int b) { return a + b; };
// Calculate cumulative sum of squares, starting with 0 (optional)
std::transform_inclusive_scan(data.begin(), data.end(), squares.begin(), add_squares, square, 0);
std::cout << "Original data: ";
for (int num : data) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "Cumulative sums of squares: ";
for (int sum : squares) {
std::cout << sum << " ";
}
std::cout << std::endl;
return 0;
}
Output:
![std::transform_inclusive_scan in C++/>
<!-- /wp:html -->
<!-- wp:paragraph -->
<p><strong>Explanation:</strong></p>
<!-- /wp:paragraph -->
<!-- wp:list -->
<ul class=](https://static.tutorialandexample.com/cpp/std-transform-inclusive-scan-in-cpp1.png)
- The iterator for the output is squares.begin().
- For summing, add_squares defines the binary operation.
- The unary operation for squaring is defined by square.
- For the total, an alternative starting value of 0 is offered.
Key Points:
- std::transform_inclusive_scan directly alters the range of output. Make sure there is sufficient room in the output range to hold the findings.
- Either the forward iterator or the output iterator must be readable.
- For the prefix sum computation to be accurate, the binary operation (binary_op) has to be commutative and associative.
- For straightforward addition operations, think about utilizing std::plus<> as the binary operator.
Common Use Cases:
Several use cases of the std::transform_inclusive_scan method in C++ are as follows:
- Calculating Cumulative Sums: It is the most common scenario where std::transform_inclusive_scan shines. By providing std::plus<> as the binary operation and an identity element (e.g., 0 for addition) as the initial value, we can efficiently compute the cumulative sum of elements after applying a transformation.
- Partial Sums Up to a Certain Index: By modifying the loop within std::transform_inclusive_scan (implementation detail), we can calculate partial sums up to a specific index in the input range. It can be useful for windowed calculations or range queries.
- Custom Transformations with Prefix Operations: The std::transform_inclusive_scan allows for more transformations that are intricate by combining unary operations and binary operations. For instance, we can calculate the running minimum or maximum of absolute differences from a certain baseline for each element.