Как написать конвейер диапазона, который использует временные контейнеры?

range-v3 запрещает просмотр временных контейнеров, чтобы помочь нам избежать создания висячих итераторов. Ваш пример демонстрирует, почему именно это правило необходимо при просмотре композиций:

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

Если view::join должны были хранить begin а также end итераторы временного вектора, возвращаемого fони будут признаны недействительными до того, как их будут использовать.

«Это все замечательно, Кейси, но почему бы представлениям 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?»

Потому что мы не дошли до этого — патчи приветствуются;)

отредактированный

Очевидно, что приведенный ниже код нарушает правило, согласно которому представления не могут владеть данными, на которые они ссылаются. (Однако я не знаю, строго ли запрещено писать что-то подобное.)

я использую ranges::view_facade создать собственный вид. Он содержит вектор, возвращенный f (по одному), меняя его на диапазон. Это позволяет использовать view::join на целый ряд таких диапазонов. Конечно, мы не можем иметь случайный или двунаправленный доступ к элементам (но view::join само по себе ухудшает диапазон до диапазона ввода), и мы не можем назначить их.

Я скопировал 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.

Проблема здесь, конечно, заключается в идее представления — не хранящемся в памяти многоуровневом ленивом оценщике. Чтобы не отставать от этого контракта, представления должны передавать ссылки на элементы диапазона, и в целом они могут обрабатывать ссылки как на rvalue, так и на lvalue.

К сожалению, в этом конкретном случае view::transform может предоставить только ссылку на rvalue в качестве вашей функции f(T t) возвращает контейнер по значению, и view::join ожидает lvalue при попытке связать представления (view::all) к внутренним контейнерам.

Все возможные решения будут вводить какое-то временное хранилище где-то в трубопровод. Вот варианты, которые я придумал:

• Создать версию view::all это может внутренне хранить контейнер, переданный ссылкой rvalue (как предложено Барри). С моей точки зрения, это нарушает
  концепция «без сохранения вида», а также требует некоторого болезненного шаблона
  кодирование, поэтому я хотел бы предложить против этого варианта.

• Используйте временный контейнер для всего промежуточного состояния после 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 возвращает ссылку на lvalue, view::join не буду жаловаться сейчас.

  Это, конечно, отчасти хак и будет работать, только если вы затем упорядочите весь диапазон в какой-то приемник, например, в выходной контейнер. Я верю, что он выдержит некоторые прямые преобразования, такие как view::replace или больше view::transformс, но что-нибудь более сложное может попытаться получить доступ к этому 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, так как он позволит вам сохранить общую семантику без изменений, и это довольно просто реализовать.

Это еще одно решение, которое не требует особого взлома. Это происходит за счет звонка 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';
}
}