如何编写使用临时容器的范围管道?

我具有带有此签名的第三方功能:

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

我也有一个现有的潜在无限范围(范围-v3类)T,名称为src。我想创建一个管道,将f映射到该范围的所有元素,并将所有向量及其所有元素展平为一个范围。

本能地,我将写以下内容。

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

但是,这将不起作用,因为我们无法创建临时容器的视图。

range-v3如何支持这样的范围管道?

R. Martinho Fernandes asked 2019-11-19T00:49:29Z
5个解决方案
10 votes

我怀疑那是不可能的。 view::join中没有一个可以在任何地方存储临时文件的机制-这显然与文档的视图概念背道而驰:

视图是一种轻量级的包装器,它以某种自定义方式呈现元素的基础序列的视图,而无需对其进行更改或复制。 视图的创建和复制很便宜,并且具有非所有的引用语义。

因此,为了使view::join工作并使表达式失效,必须在某些地方保留这些临时变量。 可能是view::all。这可以正常工作(演示):

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

除了显然不是view::join是无限的,甚至对于有限的view::all可能也增加了太多开销,您无论如何都想使用它。

您可能必须复制/重写view::join才能改用view::all(在此处需要)的某些修改版本,而不是需要左值容器(并向其中返回一个迭代器对),而允许在内部存储一个右值容器( 并将迭代器对返回到该存储版本)。 但是,这相当于复制几百行代码,因此即使令人满意,也似乎不能令人满意。

Barry answered 2019-11-19T00:50:09Z
9 votes

range-v3禁止查看临时容器,以帮助我们避免创建悬空的迭代器。 您的示例确切说明了为什么在视图组合中必须使用此规则:

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

如果view::join将存储f返回的临时向量的beginend迭代器,则在使用之前将使它们无效。

“很好,Casey,但是为什么range-v3视图不在内部存储这样的临时范围?”

因为性能。 就像STL算法的性能是基于迭代器操作为O(1)的要求一样,视图组合的性能也取决于视图操作为O(1)的要求。 如果视图将临时范围存储在“背后”的内部容器中,则视图操作的复杂性-以及合成的复杂性将变得不可预测。

“好吧,好的。鉴于我了解所有这些出色的设计,我该如何进行这项工作?!??”

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

#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是输入范围,因此是单次通过。

“这对新手不友好。哎呀,对专家也不友好。为什么在range-v3中没有对'临时存储实现™的某种支持?”

因为我们还没有解决问题,所以欢迎添加补丁;)

Casey answered 2019-11-19T00:51:28Z
5 votes

编辑

显然,以下代码违反了视图不能拥有其引用的数据的规则。 (但是,我不知道是否严格禁止这样写。)

我使用ranges::view_facade创建自定义视图。 它拥有f(一次一个)返回的向量,并将其更改为一个范围。 这使得可以在这样的范围内使用view::join。 当然,我们不能对元素进行随机或双向访问(但是view::join本身会将范围降级为“输入”范围),也不能将其分配给它们。

我从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一起编译。

ptrj answered 2019-11-19T00:52:16Z
4 votes

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

不幸的是,在这种特定情况下,view::transform只能提供右值引用,因为您的函数view::join按值返回了一个容器,而std::map希望有一个左值,因为它试图将视图(view::join)绑定到内部容器。

可能的解决方案都会在管道中的某处引入某种临时存储。 这是我想到的选项:

  • 创建一个view::transform的版本,该版本可以在内部存储通过右值引用传递的容器(如Barry所建议)。 从我的角度来看,这违反了“非存储视图”的概念,并且还需要一些痛苦的模板编码,所以我建议不要使用此选项。
  • view::transform步骤之后,为整个中间状态使用临时容器。 可以手动完成:

    view::transform

    或使用view::transform。这将导致“过早评估”,无法与无限view::join配合使用,浪费一些内存,并且总体上与您的初衷完全不同,因此,这几乎不是解决方案,但至少可以 遵守View类合同。

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

    view::transform

    然后将view::transform传递给view::join。由于std::map返回左值引用,因此view::join现在不会抱怨。

    当然,这有点麻烦,并且只有在将整个范围简化到某个接收器(如输出容器)后才能起作用。 我相信它可以承受一些直接的转换,例如view::transform或更多view::joins,但是任何更复杂的方法都可以尝试以非直接的顺序访问此std::map存储。

    在那种情况下,可以使用其他类型的存储,例如。 view::transform将解决该问题,并且仍将允许无限view::join和惰性求值,但会消耗一些内存:

    view::transform

    如果您的view::transform函数是无状态的,则该view::join也可用于潜在地保存一些呼叫。 如果有一种方法可以保证不再需要某个元素并将其从std::map中删除以节省内存,则可以进一步改进此方法。 但是,这取决于流水线的进一步步骤和评估。

由于这3个解决方案几乎覆盖了在view::transformview::join之间引入临时存储的所有地方,所以我认为这些都是您的选择。 我建议使用#3,因为它将使您保持整体语义完整,并且实现起来非常简单。

Ap31 answered 2019-11-19T00:54:08Z
2 votes

这是另一种不需要太多花哨的黑客解决方案。 每次调用f都需要付出一次致电std::make_shared的费用。但是无论如何,您都是在f中分配和填充一个容器,因此这也许是可以接受的成本。

#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';
    }
}
Eric Niebler answered 2019-11-19T00:54:37Z
translate from https://stackoverflow.com:/questions/36820639/how-do-i-write-a-range-pipeline-that-uses-temporary-containers