c++ - tag - ¿Cómo escribo una tubería de rango que utiliza contenedores temporales?

instalar google tag manager

Question

Tengo una función de terceros con esta firma:

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

También tengo un rango potencialmente infinito existente ( del tipo range-v3 ) de T llamado src . Quiero crear una tubería que asigne f a todos los elementos de ese rango y aplana todos los vectores en un solo rango con todos sus elementos.

Instintivamente, escribiría lo siguiente.

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

Sin embargo, esto no funcionará, porque no podemos crear vistas de contenedores temporales.

¿Cómo soporta range-v3 una canalización de este tipo?

Answer 1

El problema aquí, por supuesto, es la idea completa de una vista: un evaluador perezoso en capas sin almacenamiento. Para mantenerse al día con este contrato, las vistas tienen que pasar referencias a elementos de rango y, en general, pueden manejar referencias de valor y valor.

Desafortunadamente, en este caso específico view::transform solo puede proporcionar una referencia de valor de r ya que su función f(T t) devuelve un contenedor por valor, y view::join espera un valor de l cuando intenta enlazar vistas ( view::all ) a Contenedores interiores.

Las posibles soluciones introducirán algún tipo de almacenamiento temporal en algún lugar de la tubería. Estas son las opciones que se me ocurrieron:

• Cree una versión de view::all que pueda almacenar internamente un contenedor pasado por una referencia rvalue (como lo sugiere Barry). Desde mi punto de vista, esto viola la concepción de "vista de no almacenamiento" y también requiere una codificación de plantilla dolorosa, por lo que sugeriría en contra de esta opción.

• Utilice un contenedor temporal para todo el estado intermedio después del paso view::transform . Se puede hacer a mano:

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

  O usando action::join . Esto daría como resultado una "evaluación prematura", no funcionará con src infinito, desperdiciará algo de memoria y, en general, tiene una semántica completamente diferente de su intención original, por lo que difícilmente es una solución, pero al menos cumple con la clase de vista contratos

• Envuelva un almacenamiento temporal alrededor de la función que pasa a view::transform . El ejemplo más simple es

  const std::vector<T>& f_store(const T& t)
  {
    static std::vector<T> temp;
    temp = f(t);
    return temp;
  }

  y luego pasa f_store a la view::transform . Como f_store devuelve una referencia f_store , view::join no se quejará ahora.

  Esto, por supuesto, es algo así como un truco y solo funcionará si luego optimiza todo el rango en un sumidero, como un contenedor de salida. Creo que resistirá algunas transformaciones sencillas, como view::replace o more view::transform s, pero cualquier cosa más compleja puede intentar acceder a este almacenamiento temp en un orden no directo.

  En ese caso, se pueden usar otros tipos de almacenamiento, por ejemplo, std::map solucionará ese problema y aún permitirá una evaluación src infinita y diferida a expensas de algo de memoria:

  const std::vector<T>& fc(const T& t)
  {
      static std::map<T, vector<T>> smap;
      smap[t] = f(t);
      return smap[t];
  }

  Si su función f no tiene estado, este std::map también se puede usar para potencialmente guardar algunas llamadas. Este enfoque posiblemente pueda mejorarse aún más si hay una manera de garantizar que un elemento ya no sea necesario y eliminarlo del std::map para conservar la memoria. Sin embargo, esto depende de otros pasos de la tubería y la evaluación.

Como estas 3 soluciones cubren prácticamente todos los lugares para introducir almacenamiento temporal entre view::transform y view::join , creo que estas son todas las opciones que tiene. Sugeriría ir con el # 3, ya que le permitirá mantener intacta la semántica general y es bastante simple de implementar.

Answer 2

Esta es otra solución que no requiere mucho pirateo sofisticado. Viene a costa de una llamada a std::make_shared en cada llamada a f . Pero de todos modos está asignando y poblando un contenedor en f , por lo que tal vez este sea un costo aceptable.

#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 3

Sospecho que simplemente no puede. Ninguna de las view tiene maquinaria para almacenar temporarios en ningún lugar, lo que explícitamente va en contra del concepto de vista de los docs :

Una vista es un contenedor ligero que presenta una vista de una secuencia subyacente de elementos de alguna manera personalizada sin mutarla o copiarla. Las vistas son baratas de crear y copiar, y tienen una semántica de referencia no propietaria .

Entonces, para que esa join funcione y sobreviva a la expresión, algo en algún lugar tiene que aferrarse a esos temporales. Ese algo podría ser una action . Esto funcionaría ( demo ):

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

excepto que obviamente no es porque src sea ​​infinito, e incluso para src finito probablemente agrega demasiada sobrecarga para que usted quiera usar de todos modos.

Probablemente tendría que copiar / reescribir view::join para utilizar en su lugar una versión de view::all sutilmente modificada ( view::all (requerida here ) que en lugar de requerir un contenedor lvalue (y devolver un par iterador), permitió un contenedor rvalue que se almacenaría internamente (y devolvería un par de iteradores en esa versión almacenada). Pero eso equivale a copiar cientos de líneas de código, por lo que parece bastante insatisfactorio, incluso si eso funciona.

Answer 4

range-v3 prohíbe vistas sobre contenedores temporales para ayudarnos a evitar la creación de iteradores colgantes. Su ejemplo demuestra exactamente por qué esta regla es necesaria en las composiciones de vista:

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

Si view::join fuera a almacenar los iteradores de begin y end del vector temporal devuelto por f , quedarían invalidados antes de ser utilizados.

"Eso es genial, Casey, pero ¿por qué las vistas de rango v3 no almacenan rangos temporales como este internamente?"

Porque el rendimiento. Al igual que el rendimiento de los algoritmos STL se basa en el requisito de que las operaciones de iterador sean O (1), el rendimiento de las composiciones de vista se basa en el requisito de que las operaciones de vista sean O (1). Si las vistas almacenaran rangos temporales en contenedores internos "a sus espaldas", entonces la complejidad de las operaciones de vista, y por lo tanto las composiciones, se volverían impredecibles.

"Ok, bien. Dado que entiendo todo este maravilloso diseño, ¿cómo hago ESTE TRABAJO?"

Dado que la composición de la vista no almacenará los rangos temporales para usted, debe volcarlos en algún tipo de almacenamiento usted mismo, por ejemplo:

#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 << '','';
    }
}

Tenga en cuenta que la corrección de este enfoque depende del hecho de que view::join es un rango de entrada y, por lo tanto, de un solo paso.

"Esto no es amigable para los novatos. Demonios, no es amigable para los expertos. ¿Por qué no hay algún tipo de soporte para ''materialización de almacenamiento temporal'' en el rango-v3?"

Debido a que no lo hemos logrado, los parches son bienvenidos;)

Answer 5

Editado

Aparentemente, el siguiente código viola la regla de que las vistas no pueden poseer los datos a los que se refieren. (Sin embargo, no sé si está estrictamente prohibido escribir algo como esto).

Yo uso ranges::view_facade para crear una vista personalizada. Contiene un vector devuelto por f (uno a la vez), cambiándolo a un rango. Esto hace posible usar view::join en un rango de tales rangos. Ciertamente, no podemos tener un acceso aleatorio o bidireccional a los elementos (pero view::join sí degrada el rango a un rango de entrada), ni podemos asignarlos a ellos.

Copié struct MyRange del struct MyRange de Eric Niebler modificándolo ligeramente.

#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 

Compilado con gcc 5.3.0.