How to write a range pipeline that uses temporary containers?

Question

I have a third-party function with this signature:

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

I also have a potentially infinite range ( range-v3 sorting ) of T named src . I want to create a pipeline that displays f to all elements of this range and aligns all vectors to the same range with all their elements.

Instinctively, I would write the following.

  auto rng = src | view::transform(f) | view::join; 

However, this will not work because we cannot create representations of temporary containers.

How does v3 range support such a range pipeline?

Answer 1

I suspect I just can't. None of the view have equipment to store temporary files anywhere, which clearly contradicts the concept of the view from docs :

A view is a lightweight shell, which is a representation of the basic sequence of elements on some ordinary path without modification or copying. Views are cheap to create and copy and have non-owning link semantics.

So, in order for join work and survive this expression, something must be held somewhere in these time series. It could be an action . This will work ( demo ):

 auto rng = src | view::transform(f) | action::join; 

except, obviously, not for src infinity, and even for the final src , it probably adds too much overhead for you to use anyway.

You will probably have to copy / rewrite view::join to use a small modified version of view::all instead (required here ), which instead requires an lvalue container (and returning a pair of iterators to it) is allowed for the rvalue container, which it will store inside (and return a couple of iterators to this saved version). But this is a few copies of the code on several hundred lines, so it seems pretty unsatisfactory, even if it works.

Answer 2

Edited

Apparently, the code below violates the rule that views cannot own the data to which they refer. (However, I do not know if it was strictly forbidden to write something like this.)

I use ranges::view_facade to create a custom view. It contains the vector returned by f (one at a time), changing it to a range. This allows the use of view::join in the range of such ranges. Of course, we cannot have random or bi-directional access to elements (but view::join itself decomposes the range into an input range), and we cannot assign them.

I copied the struct MyRange from the Eric Niebler repository , modifying it slightly.

 #include <iostream> #include <range/v3/all.hpp> using namespace ranges; std::vector<int> f(int i) { return std::vector<int>(static_cast<size_t>(i), i); } template<typename T> struct MyRange: ranges::view_facade<MyRange<T>> { private: friend struct ranges::range_access; std::vector<T> data; struct cursor { private: typename std::vector<T>::const_iterator iter; public: cursor() = default; cursor(typename std::vector<T>::const_iterator it) : iter(it) {} T const & get() const { return *iter; } bool equal(cursor const &that) const { return iter == that.iter; } void next() { ++iter; } // Don't need those for an InputRange: // void prev() { --iter; } // std::ptrdiff_t distance_to(cursor const &that) const { return that.iter - iter; } // void advance(std::ptrdiff_t n) { iter += n; } }; cursor begin_cursor() const { return {data.begin()}; } cursor end_cursor() const { return {data.end()}; } public: MyRange() = default; explicit MyRange(const std::vector<T>& v) : data(v) {} explicit MyRange(std::vector<T>&& v) noexcept : data (std::move(v)) {} }; template <typename T> MyRange<T> to_MyRange(std::vector<T> && v) { return MyRange<T>(std::forward<std::vector<T>>(v)); } int main() { auto src = view::ints(1); // infinite list auto rng = src | view::transform(f) | view::transform(to_MyRange<int>) | view::join; for_each(rng | view::take(42), [](int i) { std::cout << i << ' '; }); } // Output: // 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 

Compiled with gcc 5.3.0.

Answer 3

range-v3 prohibits viewing temporary containers to help us avoid creating spruce. Your example shows exactly why this rule is necessary for compositions:

 auto rng = src | view::transform(f) | view::join; 

If view::join were to store the begin and end iterators of the temporary vector returned by f , they would be invalidated before they were used.

"That's all great, Casey, but why not choose v3 ranges, keep time ranges like this inside?"

Because performance. Just as the performance of STL algorithms is based on the requirement that iterator operations be O (1), the performance of composition compositions is based on the requirement that view operations be O (1). If the views displayed time ranges in the internal containers "behind", then the complexity of the viewing operations and, therefore, the compositions would become unpredictable.

"Good, great. Given that I understand all this wonderful design, how do I get this to work ?!"

Since the composition of the view will not save the time ranges for you, you need to dump them yourself into some kind of storage, for example:

 #include <iostream> #include <vector> #include <range/v3/range_for.hpp> #include <range/v3/utility/functional.hpp> #include <range/v3/view/iota.hpp> #include <range/v3/view/join.hpp> #include <range/v3/view/transform.hpp> using T = int; std::vector<T> f(T t) { return std::vector<T>(2, t); } int main() { std::vector<T> buffer; auto store = [&buffer](std::vector<T> data) -> std::vector<T>& { return buffer = std::move(data); }; auto rng = ranges::view::ints | ranges::view::transform(ranges::compose(store, f)) | ranges::view::join; unsigned count = 0; RANGES_FOR(auto&& i, rng) { if (count) std::cout << ' '; else std::cout << '\n'; count = (count + 1) % 8; std::cout << i << ','; } } 

Note that the correctness of this approach depends on the fact that view::join is an input range and, therefore, single-pass.

"This is not newbie friendly. Damn, this is not useful for experts. Why is there no support for" materializing temporary storage "in the -3 range?

Because we did not get to it - patches are welcome;)

Answer 4

This is another solution that does not require much hacking. This is due to a call to std::make_shared with every call to f . But you still distribute and fill the container in f , so maybe this is an acceptable cost.

 #include <range/v3/core.hpp> #include <range/v3/view/iota.hpp> #include <range/v3/view/transform.hpp> #include <range/v3/view/join.hpp> #include <vector> #include <iostream> #include <memory> std::vector<int> f(int i) { return std::vector<int>(3u, i); } template <class Container> struct shared_view : ranges::view_interface<shared_view<Container>> { private: std::shared_ptr<Container const> ptr_; public: shared_view() = default; explicit shared_view(Container &&c) : ptr_(std::make_shared<Container const>(std::move(c))) {} ranges::range_iterator_t<Container const> begin() const { return ranges::begin(*ptr_); } ranges::range_iterator_t<Container const> end() const { return ranges::end(*ptr_); } }; struct make_shared_view_fn { template <class Container, CONCEPT_REQUIRES_(ranges::BoundedRange<Container>())> shared_view<std::decay_t<Container>> operator()(Container &&c) const { return shared_view<std::decay_t<Container>>{std::forward<Container>(c)}; } }; constexpr make_shared_view_fn make_shared_view{}; int main() { using namespace ranges; auto rng = view::ints | view::transform(compose(make_shared_view, f)) | view::join; RANGES_FOR( int i, rng ) { std::cout << i << '\n'; } } 

Answer 5

The problem here, of course, is that the whole idea of ​​the presentation is a non-cumulative multi-layered lazy evaluator. In order to keep up with this contract, views must pass references to range elements, and in general they can handle both rvalue and lvalue references.

Unfortunately, in this particular case, view::transform can only provide an rvalue link, since your f(T t) function returns a container by value, and view::join expects an lvalue when trying to bind views ( view::all ) to internal containers.

Possible solutions would include some kind of temporary storage somewhere in the pipeline. Here are the options I came up with:

• Create a version of view::all that can internally store the container passed by the rvalue reference (as suggested by Barry). From my point of view, this violates the “no storage” concept, and also requires some painful template, so I would suggest against this option.

• Use a temporary container for the entire intermediate state after the view::transform step. Can be done manually:

   auto rng1 = src | view::transform(f) vector<vector<T>> temp = rng1; auto rng = temp | view::join; 

  Or using action::join . This will lead to a “premature evaluation”, will not work with infinite src , discard some memory, and generally have completely different semantics from your original intention, so this is hardly a solution, but at least it corresponds to looking at class contracts.

• Wrap the temporary storage around the function you pass to view::transform . The simplest example:

   const std::vector<T>& f_store(const T& t) { static std::vector<T> temp; temp = f(t); return temp; } 

  and then pass f_store to view::transform . Since f_store returns an lvalue reference, view::join will no longer complain.

  This, of course, is somewhat hacky and will work only if you arrange the entire range in some receiver, for example, on the output container. I believe that it will withstand some simple conversions, such as view::replace or more view::transform s, but something more complex might try to access this temp repository in a difficult order.

  In this case, other types of storage can be used, for example. std::map will fix this problem and will still allow infinite src and lazy estimation due to some memory:

   const std::vector<T>& fc(const T& t) { static std::map<T, vector<T>> smap; smap[t] = f(t); return smap[t]; } 

  If your function f has no state, this std::map can also be used to potentially save some calls. This approach can be further improved if there is a way to ensure that the item is no longer needed, and remove it from std::map to save memory. However, this depends on the further steps of the pipeline and the assessment.

Since these 3 solutions pretty much cover all the places to put in temporary storage between view::transform and view::join , I think these are all the options you have. I would suggest going with No. 3, as this will allow you to keep the whole semantics intact, and it is quite simple to implement.