Ami Tavory Ami Tavory - 2 months ago 6
C++ Question

How does range-v3's `partial_sum` not contradict non-owning reference semantics?

Consider How do I write a range pipeline that uses temporary containers?. The question is how to build a view transforming each element

T
using some given function

std::vector<T> f(T t);


while complying with the restriction (borrowing from the top answer there) that


A view is a lightweight wrapper that presents a view of an underlying sequence of elements in some custom way without mutating or copying it. Views are cheap to create and copy, and have non-owning reference semantics.


Basically, all answers there seem to agree that, due to this restriction, it can't be done via a view.




I don't understand how this fits in with the library supporting
partial_sum
.

Consider the following glorified integer:

#include <vector>
#include <iostream>
#include <memory>
#include <range/v3/all.hpp>

using namespace ranges;

struct glorified_int {
explicit glorified_int(int i) : m_i{std::make_shared<int>(i)} {}
operator int() const { return *m_i; }
std::shared_ptr<int> m_i;
};

glorified_int operator+(const glorified_int &lhs, const glorified_int &rhs) {
glorified_int ret{(int)lhs + (int)rhs};
return ret;
}


It basically just wraps up an
int
in a class storing it in an
std::shared_ptr
, allowing to initialize, extract, and add. W.r.t. non-owning reference semantics, I can't see the fundamental difference between it and a container such as
std::vector
.

Range doesn't seem to have a problem applying
partial_sum
to this, though:

int main() {
std::vector<glorified_int> vi{ glorified_int{1}, glorified_int{2} };
for(const auto &ps: vi | view::partial_sum())
std::cout << ps << std::endl;


Prints out

$ ./a.out
1
3


Isn't (the glorified integer of) 3 a temporary here? It's certainly not part of the original sequence. Also, a partial sum is a stateful transformation, obviously, so how can range guarantee that


Views are cheap to create and copy, and have non-owning reference semantics.


The view is as expensive to copy as the accumulation object.

Note that there's also no problem to chain this further (i.e., it is not an action):

vi | view::partial_sum() | view::take(10);


What is the difference, then?




Full Code

#include <vector>
#include <iostream>
#include <memory>
#include <range/v3/all.hpp>

using namespace ranges;

struct glorified_int {
explicit glorified_int(int i) : m_i{std::make_shared<int>(i)} {}
operator int() const { return *m_i; }
std::shared_ptr<int> m_i;
};

glorified_int operator+(const glorified_int &lhs, const glorified_int &rhs) {
glorified_int ret{(int)lhs + (int)rhs};
return ret;
}

int main() {
std::vector<glorified_int> vi{ glorified_int{1}, glorified_int{2} };
for(const auto &ps: vi | view::partial_sum())
std::cout << ps << std::endl;
vi | view::partial_sum() | view::take(10);
}

Answer

What makes a view a view is that it doesn't take or require ownership of, copy, or modify any of the elements of the input range. But a view isn't required to have no state whatsoever. Even take() or filter() have some state (a counter and a predicate, respectively).

In this specific case, partial_sum doesn't have to own any of the elements of the input range. That's the input range's job. It also doesn't need to copy or modify them. It merely needs to keep track of its own state - the running sum (an optional<glorified_int>) and the binary function doing the summing (a plus). It owns one of its own objects, but that object exists outside of the input range entirely. That still makes it a view, just a stateful one.

You write:

The view is as expensive to copy as the accumulation object.

This is true. But that's also true of many views. transform() is as expensive to copy as the function we're using to transform the view, maybe you have an enormous stateful, expensive, memory-allocating monstrosity.

When Eric writes about cheap to create and copy, I believe he means in the context of creating and copying the entire input range to produce a new range. While partial_sum() needs to keep the running sum, which in your case isn't cheap since that element needs allocation, that's still far cheaper than writing an action-based partial_sum:

// cheap version
for(const auto &ps: vi | view::partial_sum()) { ... }

// expensive version
std::vector<glorified_int> partial_sums;
if (!vi.empty()) {
    auto it = vi.begin();
    partial_sums.emplace_back(*it++);
    for (; it != vi.end(); ++it) {
        partial_sums.emplace_back(*it + partial_sums.back());
    }
}
for (const auto &ps : partial_sums) { ... }

We obviously don't need the entire partial_sums vector to do what we want (if we did need it, well, no way around that). The view offers us a cheap way to, well, view the partial sums.

Comments