std::partial_sum(3)

💖 std::partial_sum(3) — your C++ Standard Libary bestie 💖

okay so this is the std::partial_sum(3) page from the C++ Standard Libary manual (yes, that spelling is on the page, don’t come for me 🙈). It’s giving niche algorithm realness, and we’re gonna get through it together, bestie 💅.

---

🌸 NAME 🌸

std::partial_sum - std::partial_sum

That’s literally the whole NAME section. Minimalism ate. Periodt 💖.

---

✨ Synopsis ✨

Defined in header <numeric>.

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

• (1) — constexpr since C++20.

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

• (2) — constexpr since C++20.

---

🫶 What (1) does, step by step 🫶

• If [first, last) is empty, it does nothing.
• Otherwise, it performs the following operations in order:

1. Creates an accumulator acc, whose type is the value type of InputIt, and initializes it with *first.
2. Assigns acc to *d_first.
3. For each integer i in [1, std::distance(first, last)), performs the following operations in order:

a. Computes acc + *iter (until C++11) / std::move(acc) + *iter (since C++11), where iter is the next ith iterator of first.

b. Assigns the result to acc.

c. Assigns acc^[1] to *dest, where dest is the next ith iterator of d_first.

^[1] The actual value to be assigned is the result of the assignment in the previous step. We assume the assignment result is acc here.

💫 What (2) does 💫

Same as (1), but computes op(acc, *iter) (until C++11) / op(std::move(acc), *iter) (since C++11) instead.

---

Given binary_op as the actual binary operation:

• If any of the following conditions is satisfied, the program is ill-formed:
  • The value type of InputIt is not constructible from *first.
  • acc is not writable to d_first.
  • The result of binary_op(acc, *iter) (until C++11) / binary_op(std::move(acc), *iter) (since C++11) is not implicitly convertible to the value type of InputIt.
• Given d_last as the iterator to be returned, if any of the following conditions is satisfied, the behavior is undefined:
  • binary_op modifies any element of [first, last) or [d_first, d_last).
  • binary_op invalidates any iterator or subrange in [first, last] or [d_first, d_last].

---

🎀 Parameters 🎀

• first, last — the range of elements to sum.
• d_first — the beginning of the destination range; may be equal to first.
• op — binary operation function object that will be applied.

The signature of the function should be equivalent to the following:

Ret fun(const Type1 &a, const Type2 &b);

• The signature does not need to have const &.
• The type Type1 must be such that an object of type std::iterator_traits<InputIt>::value_type can be implicitly converted to Type1.
• The type Type2 must be such that an object of type InputIt can be dereferenced and then implicitly converted to Type2.
• The type Ret must be such that an object of type InputIt can be dereferenced and assigned a value of type Ret.

---

🦋 Type requirements 🦋

• InputIt must meet the requirements of LegacyInputIterator.
• OutputIt must meet the requirements of LegacyOutputIterator.

---

🌈 Return value 🌈

Iterator to the element past the last element written, or d_first if [first, last) is empty.

---

🔥 Complexity 🔥

Given (\scriptsize N)N as std::distance(first, last):

1. Exactly (\scriptsize N-1)N-1 applications of operator+.
2. Exactly (\scriptsize N-1)N-1 applications of the binary function op.

---

👑 Possible implementation 👑

bestie, here’s the exact juice 🧃:

partial_sum (1)

template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first)
{
    if (first == last)
        return d_first;

    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;

    while (++first != last)
    {
        sum = std::move(sum) + *first; // std::move since C++11
        *++d_first = sum;
    }

    return ++d_first;

    // or, since C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

partial_sum (2)

template<class InputIt, class OutputIt, class BinaryOp>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last,
                     OutputIt d_first, BinaryOp op)
{
    if (first == last)
        return d_first;

    typename std::iterator_traits<InputIt>::value_type acc = *first;
    *d_first = acc;

    while (++first != last)
    {
        acc = op(std::move(acc), *first); // std::move since C++11
        *++d_first = acc;
    }

    return ++d_first;
}

---

💜 Notes 💜

acc was introduced because of the resolution of LWG issue 539. The reason of using acc rather than directly summing up the results (i.e. *(d_first + 2) = (*first + *(first + 1)) + *(first + 2);) is because the semantic of the latter is confusing if the following types mismatch:

• the value type of InputIt
• the writable type(s) of OutputIt
• the types of the parameters of operator+ or op
• the return type of operator+ or op

acc serves as the intermediate object to store and provide the values for each step of the computation:

• its type is the value type of InputIt
• it is written to d_first
• its value is passed to operator+ or op
• it stores the return value of operator+ or op

enum not_int { x = 1, y = 2 };

char i_array[4] = {100, 100, 100, 100};
not_int e_array[4] = {x, x, y, y};
int  o_array[4];

// OK: uses operator+(char, char) and assigns char values to int array
std::partial_sum(i_array, i_array + 4, o_array);

// Error: cannot assign not_int values to int array
std::partial_sum(e_array, e_array + 4, o_array);

// OK: performs conversions when needed
// 1. creates “acc” of type char (the value type)
// 2. the char arguments are used for long multiplication (char ->
long)
// 3. the long product is assigned to “acc” (long -> char)
// 4. “acc” is assigned to an element of “o_array” (char -> int)
// 5. go back to step 2 to process the remaining elements in the input
range
std::partial_sum(i_array, i_array + 4, o_array,
std::multiplies<long>{});

---

🍓 Example 🍓

Run this code:

#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

int main()
{
    std::vector<int> v(10, 2); // v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

    std::cout << "The first " << v.size() << " even numbers are: ";
    // write the result to the cout stream
    std::partial_sum(v.cbegin(), v.cend(),
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';

    // write the result back to the vector v
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());

    std::cout << "The first " << v.size() << " powers of 2 are: ";
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

🌟 Output 🌟

The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024

---

🧚 Defect reports 🧚

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

• LWG 242 — applied to C++98. Behavior as published: op could not have side effects. Correct behavior: it cannot modify the ranges involved.
• LWG 539 — applied to C++98. Behavior as published: the type requirements needed for the result evaluations and assignments to be valid were missing. Correct behavior: added.
• LWG 2055 — applied to C++11. Behavior as published: acc was not moved while being accumulated. Correct behavior: it is moved (P0616R0).

---

💅 See also 💅

• adjacent_difference — computes the differences between adjacent elements in a range (function template).
• accumulate — sums up or folds a range of elements (function template).
• inclusive_scan (C++17) — similar to std::partial_sum, includes the i^th input element in the i^th sum (function template).
• exclusive_scan (C++17) — similar to std::partial_sum, excludes the i^th input element from the i^th sum (function template).

---

source/version: http://cppreference.com, 2024.06.10 — mwah 💋