It's high time to continue the big STL algorithm tutorial, and in this next part we are going to talk about 4 operations that are part of the <numeric>
header:
iota
inner_product
partial_sum
adjacent_difference
iota
std::iota
was added to the <numeric>
header with the first modern version of C++; C++11. Ever since then it hasn't changed much. The only modification is that since C++20 it is constexpr
.
But what does it do, after all? The name doesn't help much - at least not me.
It iterates over a range that is denoted by two iterators (beginning and end) and also takes a value. It fills the first item with the passed in value and then for each iteration it increases it's value by (++value
).
Here is an example:
#include <iostream>
#include <numeric>
#include <vector>
int main(){
std::vector myInt(10, 0);
std::iota(myInt.begin(), myInt.end(), 42);
for (auto i : myInt) {
std::cout << i << ' ';
}
std::cout << '\n';
}
/*
42 43 44 45 46 47 48 49 50 51
*/
As cryptic its name, as simple its behaviour is.
inner_product
std::inner_product
is a bit more complex function.
It has two overloads, and since C++20, both are constexpr
.
In its simpler form, it takes 4 values. The first three are iterators and they denote two ranges. The first is identified by its beginning and its end and the second one is only by its beginning. It's up to the caller to ensure that it has as many elements as the second one.
The fourth parameter is a value is an initial value for the accumulation of the products.
Let's see a simple example:
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
int main(){
std::vector v1 {1, 2, 3};
std::vector v2 {1, 2, 3};
auto product = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
std::cout << product << '\n';
std::reverse(v2.begin(), v2.end());
auto product2 = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
std::cout << product2 << '\n';
}
/*
14
10
*/
inner_product
takes the elements in the same positions of both ranges, takes their products and accumulate them.
Hence, when we call inner_product
on two vectors with the same elements (1, 2, 3 in our example), it basically sums up the squares of elements => 1 * 1 + 2 * 2 + 3 * 3 = 14.
When we reverse the second range, we calculate 1 * 3 + 2 * 2 + 3 * 1 and we end up with 10 as a result.
There are other overloads where as the fifth and sixth parameters you can pass in two binary operations. The first one replaces the summing part and the second one replaces the multiplication.
This piece of code performs the very same thing as the previous example:
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <functional>
int main(){
std::vector v1 {1, 2, 3};
std::vector v2 {1, 2, 3};
auto product = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0, std::plus<>(), std::multiplies<>());
std::cout << product << '\n';
std::reverse(v2.begin(), v2.end());
auto product2 = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0, std::plus<>(), std::multiplies<>());
std::cout << product2 << '\n';
}
/*
14
10
*/
partial_sum
std::partial_sum
is an interesting algorithm. What do you think it means without reading forward? Partially summing up a range doesn't make much sense as it's the caller who decides from when till then a sum (std::accumulate
) should go.
partial_sum
does something different. It starts summing up the elements from the left to the right and after each step, it writes the - running - result to an output range. As a first element, it doesn't output the sum of the first two elements, but simply the first element of the input range. As such, it ensures that the output range will have the same number of elements as the input. Otherwise, it would have n-1
elements, where n
is the size of the input range.
#include <numeric>
#include <iostream>
#include <vector>
int main() {
std::vector v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> partial_sums{};
partial_sums.reserve(v.size());
std::partial_sum(v.begin(), v.end(), std::back_inserter(partial_sums));
for (auto ps: partial_sums) {
std::cout << ps << " ";;
}
std::cout << std::endl;
}
/*
1 3 6 10 15 21 28 36 45 55
*/
In this example, we have a vector of numbers from 1 to 10 and in the output, first, we have 1, then 3 (1+2), then 6 (1+2+3), etc.
We also have the possibility to pass in a binary operation as the fourth parameter. We could replace our previous call, with std::partial_sum(v.begin(), v.end(), std::back_inserter(partial_sums), std::plus<int>());
taking std::plus<int>()
from the <functional>
header and we'd get the same results, but of course, with the help of the custom binary operation we could change the behaviour.
adjacent_difference
std::adjacent_difference
is moving from item to item and saves the difference between the current and the previous item into the output range. In order that the output size matches the input size, the first item is copied to the output.
By default, adjacent_difference
takes 3 iterators as inputs. The first two iterators denote the beginning and the end of the range to work on and the third iterator is the beginning of the output rage which must be able to accommodate as many elements as the original input range.
#include <numeric>
#include <iostream>
#include <vector>
int main() {
std::vector v{1, 3, 6, 10, 15, 21, 28, 36, 45, 55};
std::vector<int> diffs{};
diffs.reserve(v.size());
std::adjacent_difference(v.begin(), v.end(), std::back_inserter(diffs));
for (auto diff: diffs) {
std::cout << diff << " ";;
}
std::cout << std::endl;
}
/*
1 2 3 4 5 6 7 8 9 10
*/
In this example, we took the output of the previous partial_sum
example, and we called adjacent_difference
on them. With that, we got back the original input of the partial_sum
example. 1 is simply copied, then 3-1=>2, 6-3=>3, and so on.
Once again, we have the possibility to customize the binary operation, which is std::minus
by default:
#include <functional>
#include <numeric>
#include <iostream>
#include <vector>
int main() {
std::vector v{1, 3, 6, 10, 15, 21, 28, 36, 45, 55};
std::vector<int> diffs{};
diffs.reserve(v.size());
std::adjacent_difference(v.begin(), v.end(), std::back_inserter(diffs), std::minus<>());
for (auto diff: diffs) {
std::cout << diff << " ";;
}
std::cout << std::endl;
}
Conclusion
This time, we continued to explore the <numeric>
header and learnt about 4 algorithms; iota
, inner_product
, partial_sum
and adjacent_difference
. There are still 4 algorithms in this header that we have not discussed yet, all of them ending with *_scan
. We'll explore them next time.
Stay tuned!
Connect deeper
If you liked this article, please
- hit on the like button,
- subscribe to my newsletter
- and let's connect on Twitter!
Top comments (3)
I was forced to search the reason of such a lame name 😁
From cppreference:
⍳
is not a glitch. It's a special character, callediota
: en.wikipedia.org/wiki/Latin_iotaFrom Wikipedia:
Also from Wikipedia :
Thanks, I know that it's a Greek letter, but to be fair, even with all this information I don't find it a descriptive name at all :D
I added the link to the latin iota in my previous message, but it seems to be the greek iota indeed. See en.wikipedia.org/wiki/Iota:
You don't find it descriptive because (I believe) it was not meant to be descriptive but consice...