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

Question

我有这个签名的第三方功能:

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

我还有一个已命名的潜在无限范围(范围-v3排序).我想创建一个映射到该范围的所有元素的管道,并将所有向量展平为包含其所有元素的单个范围.Tsrcf

本能地,我会写下面的内容.

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

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

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

Answer 1

看起来range-v3 库中现在有测试用例显示如何正确执行此操作。有必要将views::cache1操作符添加到管道中：

auto rng = views::iota(0,4)
        | views::transform([](int i) {return std::string(i, char('a'+i));})
        | views::cache1
        | views::join('-');
check_equal(rng, {'-','b','-','c','c','-','d','d','d'});
CPP_assert(input_range<decltype(rng)>);
CPP_assert(!range<const decltype(rng)>);
CPP_assert(!forward_range<decltype(rng)>);
CPP_assert(!common_range<decltype(rng)>);

所以OP问题的解决方案是写

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

Answer 2

我怀疑它不能.没有view任何机器可以在任何地方存储临时工具 - 这明显违背了文档的观点概念:

视图是一个轻量级的包装器,它以某种自定义方式呈现元素的基础序列视图,而不会发生变异或复制.视图创建和复制起来很便宜,并且具有非拥有的引用语义.

因此,为了join让它能够工作并比表达更长久,某些地方必须要抓住那些临时工.那东西可能是一个action.这可以工作(演示):

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

除了显然不是src无限的,即使是有限的,src可能会增加太多的开销,无论如何都要使用.

您可能必须复制/重写view::join,而不是使用一些精巧修改的版本view::all(此处需要)而不需要左值容器(并将迭代器对返回到其中),允许它将在内部存储的rvalue容器(并返回迭代器对进入该存储的版本).但这是几百行的复制代码,所以看起来非常不令人满意,即使它有效.

Answer 3

range-v3禁止查看临时容器,以帮助我们避免创建悬空迭代器.您的示例演示了为什么在视图合成中需要此规则的原因:

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

如果view::join要存储返回的临时向量的迭代器begin和end迭代器f,它们将在被使用之前失效.

"这一切都很棒,凯西,但为什么范围-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输入范围的事实,因此是单通道.

"这不是新手友好的.哎呀,它不是专家友好的.为什么在范围-v3中没有某种'临时存储物化™'的支持？"

因为我们没有得到它 - 欢迎补丁;)

Answer 4

编辑

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

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

我struct MyRange从Eric Niebler的存储库中复制了一下,稍微修改了一下.

#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编译.

Answer 5

更新

range-v3 现在有views::cache1一个视图，它缓存视图对象本身中的最新元素，并返回对该对象的引用。正如用户@bradgonesurfing 在他的回答中指出的那样，这就是今天这个问题是如何干净有效地解决的。

下面是旧的、过时的答案，为历史好奇而保留。

这是另一种不需要太多花哨黑客攻击的解决方案。它的代价是std::make_shared每次调用 时都会调用f。但是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';
    }
}