如何编写使用临时容器的范围pipe道？

我有这个签名的第三方function： 

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

我也有一个名为src的T潜在无限范围（ 范围v3 ）。 我想创build一个pipe道，将f映射到该范围内的所有元素，并将所有向量与所有元素一起展平成一个范围。

本能地，我会写下面的。 

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

但是，这不起作用，因为我们不能创build临时容器的视图。

range-v3如何支持这样的范围pipe道？

我怀疑它不能。 这些view都没有任何机制来存储临时的任何地方 – 这是明确反对从文档的观点的概念：

一个视图是一个轻量级的包装器，以某种自定义的方式呈现元素的底层序列的视图，而不会改变或复制它。 视图创build和复制很便宜，并且拥有非拥有的引用语义。

所以为了让这个join起作用，使得这个expression活跃起来，某个地方必须要有那些临时的东西。 这可能是一个action 。 这将工作（ 演示 ）： 

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

除了显然不是src是无限的，甚至对于有限的src可能会增加太多的开销，你想要使用反正。

你可能需要复制/重写view::join ，而不是使用一个左值容器（并且返回一个迭代器对），而是使用一些经过微妙修改的view::all （ 这里是required）的版本，允许一个右值容器它将在内部存储（并将迭代器对返回到该存储的版本）。 但是，这是几百行代码复制，所以看起来相当不满意，即使这样做。

编辑

显然，下面的代码违反了视图不能拥有它们引用的数据的规则。 （但是，我不知道是否严禁写这样的东西。）

我使用ranges::view_facade创build一个自定义视图。 它拥有一个由f （一次一个）返回的向量，将其更改为一个范围。 这使得可以在一定范围内使用view::join 。 当然，我们不能对元素进行随机或双向访问（但是view::join本身会将范围降低到一个Input范围），我们也不能分配给它们。

我从Eric Niebler的存储库复制了struct MyRange稍微修改它。 

 #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

用gcc编译5.3.0。

range-v3禁止临时容器的视图，以帮助我们避免创build悬空迭代器。 你的例子certificate了为什么这个规则在视图组合中是必须的： 

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

如果view::join存储由f返回的临时向量的begin和end迭代器，它们在被使用之前将被无效化。

“凯西，这真是太好了，但是为什么范围-v3视图在内部存储这样的临时范围呢？

因为performance。 就像STLalgorithm的性能如何在迭代器操作为O（1）的条件下所预测的一样，视图合成的性能是以视图操作为O（1）的要求为基础的。 如果意见是将内部容器中的临时范围存储在“背后”，那么视图操作的复杂性以及组合将变得不可预测。

“好吧，好吧，既然我明白了这个美妙的devise，我该怎么做这个工作？！”

由于视图组合不会为您存储临时范围，因此您需要将它们转储到某种存储器中，例如： 

 #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 << ','; } }

请注意，这种方法的正确性取决于view::join是一个input范围，因此是单通。

“这不是新手友好的，哎呀，这不是专家级的，为什么在range-v3中没有对”临时存储物化“的支持？

因为我们没有得到它 – 修补程序的欢迎;）

这是另一个不需要太多花哨的解决scheme。 它的代价是每次调用f调用std::make_shared 。 但是，你正在分配和填充一个容器，所以也许这是一个可以接受的成本。 

 #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'; } }

这里的问题当然是一个视图的整个概念 – 一个非存储分层的懒惰评估器。 为了跟上这个契约，视图必须传递对范围元素的引用，通常它们可以处理右值和左值引用。

不幸的是，在这个特定的情况下， view::transform只能提供一个右值引用，因为你的函数f(T t)通过值返回一个容器，而view::join试图绑定views（ view::all ）内部容器。

可能的解决scheme都将在pipe道的某处引入某种临时存储。 以下是我提出的选项：

  • 创build一个view::all可以在内部存储由右值引用传递的容器的版本（如Barry所build议的）。 从我的angular度来看，这违反了“非存储视图”的概念，也需要一些痛苦的模板编码，所以我build议不要这样做。

  • 在view::transform步骤之后，为整个中间状态使用一个临时容器。 可以手工完成： 

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

    或者使用action::join 。 这会导致“过早评估”，不能用于无限src ，会浪费一些内存，总体上与你的初衷有着完全不同的语义，所以这根本就不是一个解决scheme，但至less它符合视图类合同。

  • 在你传递给view::transform的函数周围包装临时存储。 最简单的例子是 

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

    然后将f_store传递给view::transform 。 当f_store返回一个左值引用时， view::join现在不会抱怨。

    这当然是有点破解的，只有将整个范围简化为一个接收器，如输出容器，才能起作用。 我相信它可以承受一些直接的转换，比如view::replace或者更多的view::transform s，但是任何更复杂的东西都可以尝试以非直接的顺序访问这个temp存储。

    在这种情况下，可以使用其他types的存储，例如std::map将解决这个问题，并且仍然允许无限的src和懒惰的评估，代价是一些内存： 

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

    如果你的f函数是无状态的，这个std::map也可以用来保存一些调用。 如果有办法保证不再需要一个元素并将其从std::map移除以节省内存，则可以进一步改进此方法。 然而，这取决于pipe道和评估的进一步步骤。

由于这3个解决scheme几乎涵盖了在view::transform和view::join之间引入临时存储的所有地方，我认为这些都是您拥有的选项。 我会build议去＃3，因为它可以让你保持整体的语义完整，这是很容易实现。

Interesting Posts