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

Question

У меня есть сторонняя функция с этой подписью:

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

У меня также есть существующий потенциально бесконечный диапазон ( типа range-v3) T названный src, Я хочу создать конвейер, который отображает f ко всем элементам этого диапазона и сводит все векторы в один диапазон со всеми их элементами.

Инстинктивно я бы написал следующее.

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

Однако это не сработает, потому что мы не можем создавать представления временных контейнеров.

Как range-v3 поддерживает такой конвейер диапазона?

Answer 1

Похоже, что теперь в библиотеке range-v3 есть тестовые примеры, которые показывают, как это правильно делать.

https://github.com/ericniebler/range-v3/pull/1354/commits/9bbe4e7d064f84c45450219920b50a2070e68460

В конвейер необходимо добавить оператор 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 а также 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?"

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

Answer 3

Я подозреваю, что это просто невозможно. Ни один из view У нас есть механизм для хранения временных файлов в любом месте - это явно противоречит концепции представления из документов:

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

Итак, для этого join чтобы работать и пережить выражение, что-то должно удерживать эти временные. Это что-то может быть action, Это будет работать ( демо):

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

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

Вам, вероятно, придется скопировать / переписать view::join вместо этого использовать слегка измененную версию view::all (требуется здесь), что вместо того, чтобы требовать контейнер lvalue (и возвращать в него пару итераторов), допускается контейнер rvalue, который он будет хранить внутри (и возвращать пару итераторов в эту сохраненную версию). Но копирование кода стоит несколько сотен строк, поэтому кажется довольно неудовлетворительным, даже если это работает.

Answer 4

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

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

я использую 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.

Answer 5

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

Answer 6

Проблема здесь, конечно, заключается в идее представления - не хранящемся в памяти многоуровневом ленивом оценщике. Чтобы не отставать от этого контракта, представления должны передавать ссылки на элементы диапазона, и в целом они могут обрабатывать ссылки как на 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, так как он позволит вам сохранить общую семантику без изменений, и это довольно просто реализовать.