Comment écrire un pipeline de gamme qui utilise des conteneurs temporaires ?

Question

J'ai une fonction de tiers avec cette signature :

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

Je dispose également d'une gamme potentiellement infinie ( de la gamme-v3 ) de T nommée src . Je souhaite créer un pipeline qui met en correspondance f à tous les éléments de cette plage et aplatit tous les vecteurs en une seule plage avec tous leurs éléments.

Instinctivement, j'écrirais ce qui suit.

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

Toutefois, cette ne fonctionne pas n'avait pas l'habitude de travailler, parce que nous ne peut pas n'a pas pu créer de vues sur les conteneurs temporaires.

MISE À JOUR : ce problème a été corrigé. par cet engagement .

Comment range-v3 prend-il en charge un tel pipeline ?

Answer 1

Range-v3 interdit les vues sur les conteneurs temporaires pour nous aider à éviter la création d'itérateurs en suspens. Votre exemple démontre exactement pourquoi cette règle est nécessaire dans les compositions de vues :

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

Si view::join devaient stocker les begin y end itérateurs du vecteur temporaire renvoyé par f ils seraient invalidés avant même d'être utilisés.

"C'est très bien, Casey, mais pourquoi les vues range-v3 ne stockent-elles pas des plages temporaires comme celle-ci en interne ?

Parce que la performance. Tout comme la performance des algorithmes STL repose sur l'exigence que les opérations sur les itérateurs soient O(1), la performance des compositions de vues repose sur l'exigence que les opérations sur les vues soient O(1). Si les vues devaient stocker des plages temporaires dans des conteneurs internes "derrière votre dos", la complexité des opérations de vue - et donc des compositions - deviendrait imprévisible.

"D'accord, très bien. Étant donné que je comprends toute cette merveilleuse conception, comment puis-je faire en sorte que cela fonctionne ?!??"

Puisque la composition de la vue ne stocke pas les plages temporaires pour vous, vous devez les placer vous-même dans une sorte de stockage, par exemple :

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

Notez que l'exactitude de cette approche dépend du fait que view::join est une plage d'entrée et donc un passage unique.

"Ce n'est pas facile pour les novices. En fait, ce n'est pas adapté aux experts. Pourquoi n'y a-t-il pas une sorte de prise en charge du 'stockage temporaire materialization™' dans range-v3 ?"

Parce que nous n'avons pas encore eu le temps de le faire - les correctifs sont les bienvenus ;)

Answer 2

Je pense que ce n'est pas possible. Aucune des view ne disposent d'aucune machine pour stocker des temporaires où que ce soit - cela va explicitement à l'encontre du concept de vue du documents :

Une vue est une enveloppe légère qui présente une vue d'une séquence sous-jacente d'éléments d'une manière personnalisée sans la modifier ni la copier. Les vues sont peu coûteuses à créer et à copier. non propriétaire sémantique de référence.

Ainsi, pour que cette join Pour que l'expression fonctionne et survive à l'expression, il faut que quelque chose quelque part retienne ces temporaires. Ce quelque chose pourrait être un action . Cela fonctionnerait ( démo ) :

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

mais évidemment pas pour src étant infinie, et même pour des src ajoute probablement trop de frais généraux pour que vous souhaitiez l'utiliser de toute façon.

Vous devrez probablement copier/réécrire view::join pour utiliser à la place une version subtilement modifiée de view::all (requis aquí ) qui, au lieu de nécessiter un conteneur lvalue (et de renvoyer une paire d'itérateurs dans ce conteneur), autorise un conteneur rvalue qu'il stocke en interne (et renvoie une paire d'itérateurs dans cette version stockée). Mais cela représente plusieurs centaines de lignes de code à copier, ce qui semble peu satisfaisant, même si cela fonctionne.

Answer 3

Édité

Apparemment, le code ci-dessous viole la règle selon laquelle les vues ne peuvent pas posséder les données auxquelles elles se réfèrent. (Toutefois, je ne sais pas s'il est strictement interdit d'écrire quelque chose comme cela).

Utilizo ranges::view_facade pour créer une vue personnalisée. Il contient un vecteur retourné par f (un à la fois), en le transformant en plage. Cela permet d'utiliser view::join sur une série de séries de ce type. Il est certain que nous ne pouvons pas avoir un accès aléatoire ou bidirectionnel aux éléments (mais view::join elle-même dégrade une plage en plage d'entrée), et nous ne pouvons pas non plus leur attribuer.

J'ai copié struct MyRange de Eric Niebler dépôt en le modifiant légèrement.

#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 

Compilé avec gcc 5.3.0.

Answer 4

Le problème réside bien sûr dans l'idée même d'une vue - un évaluateur paresseux en couches sans stockage. Pour respecter ce contrat, les vues doivent transmettre des références à des éléments de plage et, en général, elles peuvent gérer à la fois des références de type rvalue et lvalue.

Malheureusement, dans ce cas précis view::transform ne peut fournir qu'une référence rvalue comme votre fonction f(T t) renvoie un conteneur par valeur, et view::join attend une valeur l lorsqu'il essaie de lier les vues ( view::all ) aux conteneurs intérieurs.

Les solutions possibles introduiront toutes une sorte de stockage temporaire quelque part dans le pipeline. Voici les options que j'ai trouvées :

• Créer une version de view::all qui peut stocker en interne un conteneur passé par une référence rvalue (comme suggéré par Barry). De mon point de vue, cela enfreint la règle du la conception de "vue non stockante" et nécessite également un codage de gabarit de codage de gabarits douloureux, donc je suggère de ne pas utiliser cette option.

• Utiliser un conteneur temporaire pour l'ensemble de l'état intermédiaire après l'exécution de la fonction view::transform pas. Elle peut être réalisée à la main :

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

  Ou en utilisant action::join . Il en résulterait une "évaluation prématurée", qui ne fonctionnerait pas avec des valeurs infinies. src La solution est donc loin d'être une solution, mais au moins elle est conforme aux contrats de classe de vue.

• Enveloppez un stockage temporaire autour de la fonction que vous passez dans view::transform . L'exemple le plus simple est

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

  et passer ensuite f_store à la view::transform . Comme f_store renvoie une référence lvalue, view::join ne se plaindra pas maintenant.

  Il s'agit bien sûr d'une sorte de piratage et cela ne fonctionnera que si vous rationalisez l'ensemble de la gamme dans une sorte de puits, comme un conteneur de sortie. Je pense qu'elle résistera à certaines transformations simples, comme view::replace ou plus view::transform mais tout ce qui est plus complexe peut essayer d'accéder à cette temp dans un ordre non direct.

  Dans ce cas, d'autres types de stockage peuvent être utilisés, par exemple std::map corrigera ce problème et permettra toujours d'avoir un nombre infini d'heures de travail. src et l'évaluation paresseuse au détriment de la mémoire :

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

  Si votre f est sans état, cette fonction std::map peut également être utilisé pour économiser certains appels. Cette approche peut éventuellement être améliorée s'il existe un moyen de garantir qu'un élément ne sera plus nécessaire et de le supprimer de la liste des éléments de la liste des éléments. std::map pour conserver la mémoire. Cela dépend toutefois des étapes suivantes du pipeline et de l'évaluation.

Ces trois solutions couvrent à peu près tous les endroits où il est possible d'introduire un stockage temporaire entre view::transform y view::join Je pense que ce sont là toutes les possibilités qui s'offrent à vous. Je suggérerais d'opter pour le numéro 3, car il vous permettra de conserver la sémantique globale intacte et il est assez simple à mettre en œuvre.

Answer 5

MISE À JOUR

La gamme-v3 a maintenant views::cache1 , une vue qui met en cache l'élément le plus récent dans l'objet de vue lui-même, et renvoie une référence à cet objet. C'est ainsi que ce problème est résolu de manière propre et efficace aujourd'hui, comme le souligne l'utilisateur @bradgonesurfing dans sa réponse.

Réponse ancienne et périmée ci-dessous, conservée à titre de curiosité historique.

---

Il s'agit d'une autre solution qui ne nécessite pas de piratage sophistiqué. Elle se fait au prix d'un appel à std::make_shared à chaque appel à f . Mais vous allouez et remplissez un conteneur en f de toute façon, il s'agit donc peut-être d'un coût acceptable.

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