Un type rev_wrap pour faciliter le parcours inversé d'une séquence bidirectionnelle

Une discussion par twitter avec le sympathique Ólafur Waage en 2017 m'a permis de savoir que ce dernier se cherchait un truc simple pour rendre le parcours inversé d'une séquence bidirectionnelle aussi aisé que le parcours en ordre « normal » de la même séquence.

En effet, examinons les cas suivants :

 

Parcours en ordre « normal »

Parcours en ordre inverse

Supposons, pour les fins de l'exemple, un « bête » vecteur d'entiers

 
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main() {
   vector<int> v{ 2,3,5,7,11 };
 
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main() {
   vector<int> v{ 2,3,5,7,11 };

Le parcours classique avec une boucle for à compteurs est triviale dans un sens, et relativement simple (quoique délicate, le type vector<T>::size_type étant un entier non-signé) dans l'autre.

 
   for(vector<int>::size_type i = 0; i != v.size(); ++i)
      cout << v[i] << ' ';
   cout << endl;
 
   for(vector<int>::size_type i = v.size(); i-- != 0;)
      cout << v[i] << ' ';
   cout << endl;

Avec des itérateurs, l'existence de std::reverse_iterator<It> et des méthodes rbegin() et rend() dans bien des conteneurs permet d'écrire un parcours inverse presque aussi simplement qu'un parcours régulier.

 
   for(auto p = begin(v); p != end(v); ++p)
      cout << *p << ' ';
   cout << endl;
 
   for(auto p = rbegin(v); p != rend(v); ++p)
      cout << *p << ' ';
   cout << endl;

Le même constat s'applique avec des algorithmes standards.

 
   for_each(begin(v), end(v), [](int n) {
      cout << n << ' ';
   });
   cout << endl;
 
   for_each(rbegin(v), rend(v), [](int n) {
      cout << n << ' ';
   });
   cout << endl;

Ce qui irritait l'ami Ólafur Waage était que la forme la plus concise, celle des répétitives for sur des intervalles, ne profite pas de l'option de parcours inverse, se limitant au parcours « régulier ».

 
   for(auto n : v)
      cout << n << ' ';
   cout << endl;
}
 
   // ...?
}

Plusieurs avenues existent pour écrire un petit décorateur de conteneur capable de transformer les services begin() et end() en recours à des reverse_iterator sur les itérateurs du conteneur sous-jacent, mais il n'était pas satisfait du code résultant (un peu trop d'écrire dans le code client pour que ce soit vraiment confortable).

Cependant, depuis C++ 17, il est possible de faire quelque chose de franchement charmant à l'aide de CTAD.

Tout d'abord, l'idée est d'avoir une solution très légère et très simple. En pratique, la seule dépendance de la classe rev_wrap ci-dessous est sur l'en-tête <iterator>; les autres inclusions ci-dessus tiennent au code de test, plus bas.

La classe rev_wrap, ma petite proposition d'outil, accepte une référence sur un conteneur de type T, et crée des reverse_iterator sur celui-ci lorsqu'on appelle ses méthodes begin() et end(). Ce sont celles-ci qui seront sollicitées par la boucle for en fin de compte.

Notez que, du fait que les références sur un tableau brut préservent la connaissance de la taille de ce dernier, il est possible d'utiliser un rev_wrap même dans ce cas.

Traditionnellement, les deux manières les plus simples de créer un rev_wrap<T>, où T est vector<int>, étaient d'utiliser une fonction de fabrication :

// fonction de fabrication
template <class T> auto make_rev_wrap(T &conteneur) {
   return { conteneur };
}
// utilisation...
vector<int> v{ 2,3,5,7,11 };
for(auto n : make_rev_wrap(v)) {
   // ... utiliser n
}

... ou encore d'instancier directement le rev_wrap, ce qui implique d'expliciter le type T auquel il s'applique (ceci peut être quelque peu déplaisant en pratique) :

// utilisation directe
vector<int> v{ 2,3,5,7,11 };
for(auto n : rev_wrap<vector<int>>{ v }) {
   // ... utiliser n
}

Ces deux techniques fonctionnent, mais n'ont pas les qualités syntaxiques recherchées.

 
#include <iostream>
#include <array>
#include <vector>
#include <iterator>

template <class T>
   class rev_wrap {
      T &obj;
   public:
      rev_wrap(T &obj) noexcept : obj{ obj } {
      }
      auto begin() {
         return std::rbegin(ob));
      }
      auto begin() const {
         return std::crbegin(obj);
      }
      auto end() {
         return std::rend(obj);
      }
      auto end() const {
         return std::crend(obj);
      }
   };

La magie qui rend rev_wrap simple à utiliser est CTAD, que C++ 17 nous a apportés. Ce mécanisme permet de déduire les paramètres d'un template a partir des paramètres passés au constructeur. Dans notre cas, la déduction est implicitement correcte, mais il existe un mécanisme (les guides de déduction) pour expliciter les règles de déduction à appliquer quand la déduction implicite ne fonctionne pas.

L'extrait de code à droite montre comment un guide de déduction explicite aurait pu être écrit : cette écriture toute simple indique au compilateur que, lorsqu'il constate un appel à rev_wrap(T&) pour un type T donné, il doit remplacer cet appel de constructeur en apparence non-générique par un appel au constructeur d'un rev_wrap<T> et lui relayer les paramètres (dans ce cas, il n'y en a qu'un seul).

Ainsi, on peut remplacer rev_wrap<vector<int>>{v} par rev_wrap(v) ou par rev_wrap{v} (au choix), tout simplement.

 
// si nous devions l'exprimer de manière explicite,
// voici ce dont ça aurait l'air
template <class T> rev_wrap(T&) -> rev_wrap<T>;

Le code de test proposé à droite montre qu'il est, somme tout, aussi simple d'itérer dans l'ordre inverse que dans l'ordre « régulier » une fois ces outils mis en place.

 
int main() {
   using namespace std;
   array<int,5> vals{ 2,3,5,7,11 };
   for(auto n : vals) cout << n << ' ';
   cout << '\n';
   for(auto n : rev_wrap{ vals }) cout << n << ' ';
   cout << '\n';
}

Pour le code détaillé, voir ci-dessous.

#include <iostream>
#include <array>
#include <vector>
#include <iterator>
template <class T>
   class rev_wrap {
      T &obj;
   public:
      rev_wrap(T &obj) noexcept : obj{ obj } {
      }
      auto begin() { return std::rbegin(obj); }
      auto begin() const { return std::crbegin(obj); }
      auto end() { return std::rend(obj); }
      auto end() const { return std::crend(obj); }
   };

int main() {
   using namespace std;
   array<int,5> vals{ 2,3,5,7,11 }; // ou int[], ou vector<int>, ou...
   for(auto n : vals) cout << n << ' ';
   cout << '\n';
   for(auto n : rev_wrap{ vals }) cout << n << ' ';
   cout << '\n';
}

Pas mal, non?

Valid XHTML 1.0 Transitional

CSS Valide !