How to use partial_sum with an output container of a different type?

I am looking into partial_sum in <numeric> & <algorithm> in C++ (C++20). According to documentation here it is possible to have an output iterator OutputIt of a type different from the input one InputIt.

Let me give an example. Lets say we have a class defined as

typedef struct score_card {
    std::string name;
    int score;

} score_card;

I want to accumilate the int score of a vector<score_card> into a vector<int> The documentation hints that an output iterator can be different from the input iterator in the declaration below (C++20)

template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,
                                BinaryOperation op );

If I try to implement it as so:

void partial_sum_score()
{
    std::vector<score_card> data{
        {"Bob", 2},
        {"Mallory", 1},
        {"Alice", 2},
        {"carol", 0}
    };

    std::vector<int> data_partial_sum{
        0, 0, 0, 0
    };

    auto accumilate_scores = [](score_card first, score_card second) {return first.score + second.score; };

    std::partial_sum(data.begin(), data.end(), data_partial_sum.begin(), accumilate_scores);
}

That would throw this error (on Microsoft VS 2022)

Error   C2440   '=': cannot convert from 'score_card' to 'int'  ******* C:\Program Files\Microsoft Visual Studio\2022\Enterprise\VC\Tools\MSVC\14.30.30705\include\numeric  253 
Error   C2679   binary '=': no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion) ******  C:\Program Files\Microsoft Visual Studio\2022\Enterprise\VC\Tools\MSVC\14.30.30705\include\numeric  260

That makes some sense, as the first output element is an int and the first input element is score_card. But the implementation of the function doesnt seem to reference the _OutIt type anywhere: (from numeric header):

template <class _InIt, class _OutIt, class _BinOp>
_CONSTEXPR20 _OutIt partial_sum(const _InIt _First, const _InIt _Last, _OutIt _Dest, _BinOp _Reduce_op) {
    // compute partial noncommutative and nonassociative reductions into _Dest, using _Reduce_op
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    auto _UDest       = _Get_unwrapped_n(_Dest, _Idl_distance<_InIt>(_UFirst, _ULast));

    if (_UFirst != _ULast) {
        _Iter_value_t<_InIt> _Val(*_UFirst);
        for (;;) {
            *_UDest = _Val;
            ++_UDest;
            ++_UFirst;
            if (_UFirst == _ULast) {
                break;
            }
#if _HAS_CXX20
            _Val = _Reduce_op(_STD move(_Val), *_UFirst);
#else // ^^^ _HAS_CXX20 ^^^ // vvv !_HAS_CXX20 vvv
            _Val      = _Reduce_op(_Val, *_UFirst);
#endif // _HAS_CXX20
        }
    }

    _Seek_wrapped(_Dest, _UDest);
    return _Dest;
}

What am I missing? And is this even possible? If not, why is output iterator different from input iterator? (optionally) how is the output destination size mismatch handled (if data_partial_sum is of size 1 for example)?

Solution

The output iterator can be a different type from the input iterator, but the constraint is that the input iterator's value type has to be writeable into the output iterator.

That is, if the input iterator is I and the output iterator is O, then in C++20 terms, this is the concept:

template <typename I, typename O>
concept writable_into = input_iterator<I>
    && requires (iter_value_t<I> value, O out) {
           *out = value;
       };

Or, alternatively, O has to satisfy std::output_iterator<std::iter_value_t<I>>.

Or, alternatively alternatively, the underlying types here can't change. partial_sum takes a range of T and writes a range of T. It can't take a range of T and write a range of U.

What you're trying to do is take a range of score_card (side-note, why is this a typedef? Just struct score_card { ... }; please, this isn't C) and produce a range of int. You can't do that with partial_sum because you can't change the type, you can only change which binary operation is invoked on the type (i.e. you can change from + to * to any other binary function, but it still has to operate on score_card).

Instead, you just want to operate on the scores. Which is:

auto scores = data | std::views::transform(&score_card::score);
std::partial_sum(scores.begin(), scores.end(), data_partial_sum.begin());

Now these are all the same type. Ideally this would eventually become:

std::ranges::partial_sum(scores, data_partial_sum.begin());

But we don't have a range version of this algorithm yet.

It's also a bit scary to use data_partial_sum.begin() as the output iterator, since if you don't size the vector correct up-front, you're just writing off the back in a way that you have no control over. So std::back_inserter(data_partial_sum) is usually better.