DEV Community

Sandor Dargo
Sandor Dargo

Posted on • Originally published at sandordargo.com

The big STL Algorithms tutorial: more numeric algorithms

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 
*/
Enter fullscreen mode Exit fullscreen mode

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
*/
Enter fullscreen mode Exit fullscreen mode

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
*/
Enter fullscreen mode Exit fullscreen mode

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
*/
Enter fullscreen mode Exit fullscreen mode

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 
*/
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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

Discussion (3)

Collapse
pgradot profile image
Pierre Gradot • Edited on

The name doesn't help much - at least not me

I was forced to search the reason of such a lame name 😁

From cppreference:

The function is named after the integer function from the programming language APL

is not a glitch. It's a special character, called iota : en.wikipedia.org/wiki/Latin_iota

From Wikipedia:

[APL] uses a large range of special graphic symbols to represent most functions and operators, leading to very concise code

Also from Wikipedia :

The programming language APL is distinctive in being symbolic rather than lexical: its primitives are denoted by symbols, not words. These symbols were originally devised as a mathematical notation to describe algorithms.

Collapse
sandordargo profile image
Sandor Dargo Author

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

Collapse
pgradot profile image
Pierre Gradot

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:

In some programming languages (e.g., A+, APL, C++, Go), iota (either as the lowercase symbol or the identifier iota) is used to represent and generate an array of consecutive integers. For example, in APL ⍳4 gives 1 2 3 4.

You don't find it descriptive because (I believe) it was not meant to be descriptive but consice...