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

Question

我有一个带有这个签名的第三方函数：

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

我也有一个名为的现有潜在无限范围（范围-v3 排序）。我想创建一个映射到该范围内所有元素的管道，并将所有向量扁平化为一个包含所有元素的范围。Tsrcf

本能地，我会写以下内容。

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

但是，这行不通，因为我们无法创建临时容器的视图。

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

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

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

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

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

“这一切都很好，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 中没有对‘临时存储实现™’的某种支持？”

因为我们还没有解决它 - 欢迎使用补丁 ;)

Answer 3

我怀疑它只是不能。没有一个views 有任何机制来在任何地方存储临时文件 - 这明显违反了文档中的视图概念：

视图是一个轻量级的包装器，它以某种自定义方式呈现底层元素序列的视图，而无需对其进行变异或复制。视图的创建和复制成本很低，并且具有非拥有引用语义。

因此，为了join让它发挥作用并比表达方式更持久，必须在某个地方抓住那些临时的东西。那东西可能是一个action. 这会起作用（演示）：

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

除了显然不是src无限的，即使是有限的src也可能会增加太多的开销，让你无论如何都不想使用。

您可能不得不复制/重写view::join以使用view::all（此处需要）的一些巧妙修改的版本，而不是需要一个左值容器（并将迭代器对返回到其中），而是允许使用它将在内部存储的右值容器（并返回到该存储版本的迭代器对）。但那是几百行代码的复制量，所以看起来很不令人满意，即使这样可行。

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

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

不幸的是，在这种特定情况下view::transform，您的函数只能提供一个右值引用，因为您的函数f(T t)按值返回一个容器，并且view::join在尝试将视图 ( view::all) 绑定到内部容器时需要一个左值。

可能的解决方案都将在管道中的某处引入某种临时存储。以下是我想出的选项：

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

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

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

  或使用action::join. 这将导致“过早评估”，无法使用无限src，会浪费一些内存，并且总体上与您的初衷具有完全不同的语义，因此这根本不是一个解决方案，但至少它符合视图类合同.

• 在传入的函数周围包裹一个临时存储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现在不会抱怨。

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

  在这种情况下，可以使用其他类型的存储，例如，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以节省内存，则此方法可能会进一步改进。然而，这取决于管道和评估的进一步步骤。

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

Answer 6

更新

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

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

---

这是另一个不需要太多花哨的黑客攻击的解决方案。std::make_shared这是以每次调用 to为代价的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';
    }
}