C++ generic numeric algorithms in header <numeric>

The C++ Standard Library header <numeric> contains several generic numeric algorithms. In this post we take a look at how they can be used for solving real world examples.

Accumulating values

Problem: Given the monthly sales values compute the total sales during a year.

Solution: This is a simple sum that can be computed by iterating over the sales and summing them.

There is an algorithm for that called accumulate. It computes the sum in a given range and the provided initial value. So for our problem this can be put as:

Problem: Given the monthly inflation rates compute the total inflation during a year.

Solution: If the inflation was 10% in January and 20% in February, the inflation at the end of February is not 30% but 32%. The monthly inflation rates must be multiplied. An overloaded accumulate allows to specify a binary operation to be used for accumulating values, instead of operator+. So the solution to our problem could look like this:

Partial accumulations

Problem: Given the monthly sales values compute the accumulated total sales per whole year at the end of each month. In other words show the sales for January, January to February, January to March, … January to December.

Solution: This is again a simple summing operation where in each loop you have a partial sum. s[0] = v[0], s[1] = v[0] + v[1], s[2] = v[0] + v[1] + v[2], etc.

There is an algorithm called partial_sum that does exactly that: it computes the partial sums of the elements in the given range and writes them in a destination range. There are two overloads of it, one using operator+ and one that allows to specify a binary operation.

The content of acc_sales will be {1000, 2500, 4500, 6000, 8000, 9000, 12000, 13500, 14700, 16500, 18700, 20700}.

Sum of products

Problem: Given the values of daily sales in USD compute the total sales in EUR.

Solution: Computing the total sales in USD and then multiplying with the USD/EUR exchange rate is not a correct solution because the exchange rate varies every day. We must compute the daily sales in EUR and then sum those values. That means we need a sum of products.

Another algorithm in the <numeric> header called inner_product does exactly that. It takes two ranges and an initial value and uses operator* to compute the product and operator+ to sum the products.

Problem: Given the monthly budgets and the actual sales over an year count how many times the budget was met or exceeded.

Solution: To count how many times the sales where equal or greater than the budget we have to compare the values in each month and increment a value each time the condition was true.

Instead of coding this explicitly we could use an overload of the inner_product algorithm that takes two additional parameters, both binary operations, for the sum operation and the product operation. For the sum we can use std::plus() and for comparison std::greater_equal() (need to include header <functional>).

The result of the count for the input data is 6.

Adjacent differences

Problem: Given the monthly sales for an year compute the variations (in percentage) between the current and previous monthly sales. If sales in January were 1000 and in February were 1500, then the sales variation for February is 50%.

Solution: We have to iterate through the monthly value and compute (current - prev) / prev for each month. This is an operation applied to adjacent values.

An algorithm called adjacent_difference computes difference between adjacent values in a given ranges and writes them in a destination range. The first element of the input range is copied unmodified to the beginning of the destination range. An overload allows to specify a binary operation to be used instead of operator-.

To solve the proposed problem we call this algorithm on the sales and then remove the first element from the destination range (since it’s just a copy of the sales for the first month). We use a lambda for the binary operation and it simply returns (current - prev) / prev.

The result for the given range (shown with 4 decimals) is {0.5000, 0.3333, -0.2500, 0.3333, -0.5000, 2.0000, -0.5000, -0.2000, 0.5000, 0.2222, -0.0909}.

6 thoughts on “C++ generic numeric algorithms in header <numeric>

  1. sehe

    I would consider the budget comparison _abuse_ of std::inner_product.

    I think it’s way more accurate to make it a count (or an accumulate) after a binary transform (http://coliru.stacked-crooked.com/a/a1b8fdba8022d65c).

    At the **very least** remove the dependence on shady implicit conversion of bool -> int by spelling that out (e.g. using c++1y: http://coliru.stacked-crooked.com/a/d9022c8b2400d632)

    It’s nice to write witty code with STL algorithms, but it’s a lot nicer to have scrutable code that actually tells you what’s going on.

    $0.02

    Reply
  2. l0calh05t

    Although I do agree with the previous poster that the budget comparison isn’t a good example, I don’t think using a ternary operator makes it any cleaner or nicer (or that bool->int conversion is “shady”). And the transform+count is highly inefficient due to the completely unneccessary temporary vector (and vector itself!). In any case, I was even more bothered about the last example as erasing the first element of a vector is just about the worst thing you can do…

    Reply
  3. Andy Prowl

    Just one minor thing: in the last example, “double const & v2″ should probably be just “double const v2″ – unless taking by reference is intended, in which case I would like an explanation :)
    Thank you for the article!

    Reply
    1. Marius Bancila Post author

      Sorry if that was misleading to you, but the explanation in the paragraph and the values in the code sample are not related. In the code sample the values are 1%, 2%, etc. It was easier to explain with larger amounts.

      Reply

Leave a Reply