0

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)?

Improve this question

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

That was super helpful Thanks You noticed my C background too. Occupational hazard of working with legacy C app Your point regarding concepts is probably spot on. I am quite ignorant of ranges & concepts (on my list, getting there) Your reply made me consider using transform_inclusive_scan as so auto transform_score = [] (score_card card) {return card.score; }; std::transform_inclusive_scan(data.begin(), data.end(), std::back_inserter(data_partial_sum), std::plus{}, transform_score); And thanks to point out back_inserter. I was concerned about this in my post didnt know this existed.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.