c++pointerspositionrecurrence

partial_sum() position of previous


Using partial_sum(), I am trying to get the position from previous during the recurrence. I don't understand the result. I was expecting to get :

recurrence i=0
recurrence i=1
...

As the recurrence unfolds. But I am getting :

recurrence i=-48115006
recurrence i=-48115006
...

What am doing wrong ?

#include <vector>
#include <algorithm>
#include <numeric>
#include <stdio.h>
using namespace std;

int main()
{
        const int n=15;
        vector<vector<int> > vv(n+1);
        vv[0]={42};

        auto next=[&](const vector<int>& previous, const vector<int>&){
                const int i = &previous - &vv[0];
                printf("recurrence i=%d\n", i);
                fflush(stdout);
                vector<int> v;
                return v;
        };

        partial_sum(vv.begin(), vv.end(), vv.begin(), next);
}

Solution

  • The implementation for partial_sum that you are using is probably similar to the one described in cppreference, Possible implementation, Second version:

    template<class InputIt, class OutputIt, class BinaryOperation>
    constexpr // since C++20
    OutputIt partial_sum(InputIt first, InputIt last, 
                         OutputIt d_first, BinaryOperation op)
    {
        if (first == last)
            return d_first;
     
        typename std::iterator_traits<InputIt>::value_type sum = *first;
        *d_first = sum;
     
        while (++first != last)
        {
            sum = op(std::move(sum), *first); // std::move since C++20
            *++d_first = sum;
        }
     
        return ++d_first;
    }
    

    That being the case, the first argument that partial_sum passes to op (the binary operation, next in your code) is fix: it's a reference to an accumulator. It is the second argument the one that varies: it's a reference to the current element in each iteration (starting at the second element). But, in your example, you don't use this second argument to set i. Instead, you always use &vv[0], which is also a fix value (unless vv changes in size, which is not the case). So it's expected that you are always printing the same value: the difference of two fix addresses.

    You can see it working here with some more debugging output.