Comment puis-je écrire un pipeline de plage qui utilise des conteneurs temporaires?

J’ai une fonction tierce avec cette signature:

std::vector f(T t); 

J’ai aussi une plage potentiellement infinie existante ( du type range-v3 ) de T nommée src . Je veux créer un pipeline qui mappe f à tous les éléments de cette plage et aplatit tous les vecteurs dans une seule plage avec tous leurs éléments.

Instinctivement, j’écrirais ce qui suit.

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

Cependant, cela ne fonctionnera pas, car nous ne pouvons pas créer de vues de conteneurs temporaires.

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

Je pense que c’est impossible. Aucune des view dispose de machines pour stocker des données temporaires, ce qui est explicitement contraire au concept de vue des documents :

Une vue est un wrapper léger qui présente de manière personnalisée une vue d’une séquence d’éléments sous-jacente sans la muter ou la copier. Les vues sont peu coûteuses à créer et à copier et possèdent une sémantique de référence non propriétaire .

Donc, pour que cette join fonctionne et survivre à l’expression, quelque chose doit s’accrocher quelque part à ces temporaires. Ce quelque chose pourrait être une action . Cela fonctionnerait ( démo ):

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

sauf évidemment pas pour src étant infini, et même pour finis src ajoute probablement trop de frais généraux pour que vous souhaitiez 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 (obligatoire ici ) qui, au lieu de nécessiter un conteneur lvalue (et d’y renvoyer une paire d’iterators), autorise un conteneur rvalue qu’il stockerait en interne (et renverrait une paire d’iterators dans cette version stockée). Mais cela fait plusieurs centaines de lignes de code de copie, cela semble donc plutôt insatisfaisant, même si cela fonctionne.

range-v3 interdit les vues sur des conteneurs temporaires pour nous aider à éviter la création d’iterators ininterrompus. Votre exemple montre exactement pourquoi cette règle est nécessaire dans les compositions de vue:

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

Si view::join devait stocker les iterators de begin et de end 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 d’iterator soient O (1), les performances des compositions de vue reposent sur l’exigence que les opérations de vue soient O (1). Si les vues stockaient des plages temporaires dans des conteneurs internes “derrière votre dos”, la complexité des opérations d’affichage – et donc des compositions – deviendrait imprévisible.

“Ok, bien. Étant donné que je comprends tout ce merveilleux design, comment puis-je faire ce travail?! ??”

Comme la composition de la vue ne stocke pas les plages temporaires pour vous, vous devez les stocker dans une sorte de stockage, par exemple:

 #include  #include  #include  #include  #include  #include  #include  using T = int; std::vector f(T t) { return std::vector(2, t); } int main() { std::vector buffer; auto store = [&buffer](std::vector data) -> std::vector& { 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 une seule passe.

"Ce n’est pas adapté aux débutants. Heck, ce n’est pas adapté aux experts. Pourquoi n’y at-il pas une sorte de prise en charge de la" matérialisation du stockage temporaire "dans la gamme v3?"

Parce que nous n'y sums pas parvenus - les correctifs sont les bienvenus;)

Édité

Apparemment, le code ci-dessous viole la règle selon laquelle les vues ne peuvent pas posséder les données auxquelles elles font référence. (Cependant, je ne sais pas s’il est ssortingctement interdit d’écrire quelque chose comme ça.)

J’utilise ranges::view_facade pour créer une vue personnalisée. Il contient un vecteur renvoyé par f (un à la fois), le changeant en une plage. Cela permet d’utiliser view::join sur une plage de ces plages. Certes, nous ne pouvons pas avoir un access aléatoire ou bidirectionnel aux éléments (mais view::join lui-même dégrade une plage en une plage d’entrée), et nous ne pouvons pas non plus leur atsortingbuer.

J’ai copié struct MyRange partir du référentiel d’Eric Niebler en le modifiant légèrement.

 #include  #include  using namespace ranges; std::vector f(int i) { return std::vector(static_cast(i), i); } template struct MyRange: ranges::view_facade> { private: friend struct ranges::range_access; std::vector data; struct cursor { private: typename std::vector::const_iterator iter; public: cursor() = default; cursor(typename std::vector::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& v) : data(v) {} explicit MyRange(std::vector&& v) noexcept : data (std::move(v)) {} }; template  MyRange to_MyRange(std::vector && v) { return MyRange(std::forward>(v)); } int main() { auto src = view::ints(1); // infinite list auto rng = src | view::transform(f) | view::transform(to_MyRange) | 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.

Ceci est une autre solution qui ne nécessite pas beaucoup de piratage sophistiqué. Cela se fait au prix d’un appel à std::make_shared à chaque appel à f . Mais vous allouez et remplissez un conteneur dans f toute façon, alors peut-être que c’est un coût acceptable.

 #include  #include  #include  #include  #include  #include  #include  std::vector f(int i) { return std::vector(3u, i); } template  struct shared_view : ranges::view_interface> { private: std::shared_ptr ptr_; public: shared_view() = default; explicit shared_view(Container &&c) : ptr_(std::make_shared(std::move(c))) {} ranges::range_iterator_t begin() const { return ranges::begin(*ptr_); } ranges::range_iterator_t end() const { return ranges::end(*ptr_); } }; struct make_shared_view_fn { template ())> shared_view> operator()(Container &&c) const { return shared_view>{std::forward(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'; } } 

Le problème ici est bien sûr l’idée d’une vue – un évaluateur paresseux en couches qui ne stocke pas. Pour suivre ce contrat, les vues doivent faire passer des références à des éléments de plage et, en général, elles peuvent gérer à la fois les références rvalue et lvalue.

Malheureusement, dans ce cas précis, view::transform ne peut fournir qu’une référence à la valeur, car votre fonction f(T t) renvoie un conteneur par valeur et view::join attend une lvalue en essayant de lier des vues ( view::all ) à conteneurs intérieurs.

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

  • Créez 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 sharepoint vue, cela va à l’encontre de la conception de la «vue non stockée» et nécessite également un codage douloureux des gabarits.
  • Utilisez un conteneur temporaire pour tout l’état intermédiaire après l’étape view::transform . Peut être fait à la main:

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

    Ou en utilisant action::join . Cela se traduirait par une “évaluation prématurée”, ne fonctionnerait pas avec une src infinie, gaspillerait de la mémoire, et aurait une sémantique complètement différente de votre intention initiale, ce qui est loin d’être une solution, mais au moins elle est conforme à la classe view contrats.

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

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

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

    Ceci est bien sûr un peu un hack et ne fonctionnera que si vous rationalisez ensuite toute la gamme dans un évier, comme un conteneur de sortie. Je crois qu’il résiste à certaines transformations simples, telles que view::replace ou more view::transform s, mais tout ce qui est plus complexe peut tenter d’accéder à ce stockage temp dans un ordre non simple.

    Dans ce cas, d’autres types de stockage peuvent être utilisés, par exemple std::map corrigera ce problème et permettra toujours une évaluation src et paresseuse infinie aux dépens de la mémoire:

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

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

Comme ces trois solutions couvrent à peu près tous les endroits où introduire le stockage temporaire entre view::transform et view::join , je pense que ce sont toutes les options que vous avez. Je suggérerais d’aller avec # 3 car cela vous permettra de garder intacte la sémantique globale et c’est assez simple à mettre en œuvre.