<iterator> : conception d'iterator, introduction aux traits

<iterator> : conception d'iterator, introduction aux traits - C++ - Programmation

Marsh Posté le 31-01-2005 à 21:55:28    

Pré-requis :
- savoir ce qu'est un iterator
- spécialisation partielle
- mot-clef typename

 

Et oui, vous ne le saviez pas, mais <iterator>, c'est un entête standard. Qu'est-ce qu'il y a dedans ?
- des définitions, classes et fonctions relatives aux iterators.
- des "traits" pour iterator.
 
Voici une petite description de ce contenu et j'en profite pour faire une introduction aux traits et quelques rappels sur comment bien faire un iterator.

 
 
Un iterator au sens STL, doit obéir à une certaine "interface". Celle-ci est simple :
 

Code :
  1. template<class Category, class Ty, class Diff = ptrdiff_t
  2.     class Pointer = Ty *, class Reference = Ty&>
  3.     struct iterator {
  4.     typedef Category iterator_category;
  5.     typedef Ty value_type;
  6.     typedef Diff difference_type;
  7.     typedef Pointer pointer;
  8.     typedef Reference reference;
  9.     };


     
Il s'agit tout simplement de 5 petits typedef bien utiles. Notez les valeurs par défaut. À propos de Category : il s'agit d'un type parmi std::{ input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag,  random_access_iterator_tag }. C'est la matérialisation des concepts souvent employés RandomAccessIterator, ForwardIterator, etc. Libre à vous définir vos propres catégories (en héritant de std::andom_access_iterator_tag par exemple).
 
Il vous reste donc une chose à faire : quand vous créez votre classe d'iterator, héritez publiquement de std::iterator<ce qui va bien>. Ça ne coûte rien :) (Voir plus bas pour un exemple.)
 
 
C'est quoi les traits
Les iterators sont une ~abstraction des pointeurs. En C++, ils servent à matérialiser le concept de séquence. Dans une application, on a souvent besoin de mélanger iterators et pointeurs classiques. Le problème, c'est que vous coder un algorithme générique, mais les petites différences entre pointeurs et iterators sont assez ennuyeuses à gérer. Et bien les traits sont une solution à ce genre de problème.
 
Think of a trait as a small object whose main purpose is to carry information used by another object or algorithm to determine "policy" or "implementation details". B.S.
 
Les traits sont des petits objets qui fournissent des informations à propos d'un autre objet (ou algorithme) pour déterminer la marche à suivre ou des détails d'implémentation. Dans notre cas, nous avons donc besoin d'une classe iterator_traits pour faire la jointure entre pointeur et iterator. Techniquement, les traits se présentent comme une cartographie de type : on fournit un argument template T, et le traits va nous renseigner grâce à une série de typedef.
 
 
Description de std::iterator_traits<>
 
Rien de très compliqué, on veut juste unifier iterators, pointeurs et const-pointeurs. On fournit 5 typedefs, c'est la projection des typedefs de std::iterator.
 
Notez bien les différences sur "pointer" et "reference".
 

Code :
  1. template<typename _Iterator>
  2. struct iterator_traits
  3. {
  4.   typedef typename _Iterator::iterator_category iterator_category;
  5.   typedef typename _Iterator::value_type        value_type;
  6.   typedef typename _Iterator::difference_type   difference_type;
  7.   typedef typename _Iterator::pointer           pointer;
  8.   typedef typename _Iterator::reference         reference;
  9. };
  11. template<typename _Tp>
  12. struct iterator_traits<_Tp*>
  13. {
  14.   typedef random_access_iterator_tag iterator_category;
  15.   typedef _Tp                         value_type;
  16.   typedef ptrdiff_t                   difference_type;
  17.   typedef _Tp*                        pointer;
  18.   typedef _Tp&                        reference;
  19. };
  21. template<typename _Tp>
  22. struct iterator_traits<const _Tp*>
  23. {
  24.   typedef random_access_iterator_tag iterator_category;
  25.   typedef _Tp                         value_type;
  26.   typedef ptrdiff_t                   difference_type;
  27.   typedef const _Tp*                  pointer;
  28.   typedef const _Tp&                  reference;
  29. };


 
 
 
 
L'exemple
 
Objectifs :  
- définir une fonction distance(first, last) qui calcule la distance entre 2 itérateurs. Cette fonction est semblable à std:: distance définie dans <iterator>
- améliorer cette fonction si nécessaire.
 
 
Pour la première partie, c'est relativement facile. Une fois qu'on a passé les longs noms de types, c'est de la tarte. Pas de quoi s'affoler. Ici, on utilise les traits pour obtenir "automatiquement" le type de retour adéquate représentant une différence entre 2 iterator.
 
 

Code :
  1. namespace My
  2. {
  3.   template<typename InputIterator>
  4.   typename std::iterator_traits<InputIterator>::difference_type
  5.   distance(InputIterator first, InputIterator last)
  6.   {
  7.     typename std::iterator_traits<InputIterator>::difference_type n = 0;
  9.     while (first != last)
  10.       {
  11. ++first;
  12. ++n;
  13.       }
  15.     return n;
  16.   }
  17. }


 
Maintenant, bricolons-nous 2 classes d'iterator pour voir ce que ça donne :
- un ForwardIterator (typiquement un iterator de liste)
- un RandomAccessIterator (un iterator de vecteur)
sont 2 classes simples qui porte chacune une valeur.
 
NB : j'ai "tassé" tout le code dans définition pour faire au plus cours possible, et je n'ai défini que les fonctions membres nécessaires à l'exemple. Par exemple pour la classe Forward, il manque un operator++(int).
 
 

Code :
  1. namespace My
  2. {
  3.   template<typename T>
  4.   struct Forward
  5.     : std::iterator<std::forward_iterator_tag, T>
  6.   {
  7.     Forward(T v) : value(v)
  8.     { }
  10.     bool operator!=(const Forward &other) const
  11.     {
  12.       return this->value != other.value;
  13.     }
  15.     Forward& operator++()
  16.     {
  17.       std::cout << "++Forward\n";
  18.       this->value++;
  19.       return *this;
  20.     }
  22.     private:
  23.       T value;
  24.   };
  28.   template<typename T>
  29.   struct Random
  30.     : std::iterator<std::random_access_iterator_tag, T>
  31.   {
  32.     Random(T v) : value(v)
  33.     { }
  35.     bool operator!=(const Random &other) const
  36.     {
  37.       return this->value != other.value;
  38.     }
  40.     typename std::iterator<std::random_access_iterator_tag, T>::difference_type
  41.     operator-(const Random &other) const
  42.     {
  43.       return this->value - other.value;
  44.     }
  46.     Random& operator++()
  47.     {
  48.       std::cout << "++Random\n";
  49.       this->value++;
  50.       return *this;
  51.     }
  53.     private:
  54.       T value;
  55.   };
  56. }


 
 
Et voilà un main de test. On utilise des int comme argument pour Forward et Random.
 

Code :
  1. int main()
  2. {
  3.   typedef My::Forward<int> I;
  4.   typedef My::Random<int> R;
  7.   // complexité linéaire : normal
  8.   std::cout << "first <-> last\n"
  9.     << My::distance(I(0), I(3))
  10.     << "\n\n";
  13.   // complexité linéaire : aïe !
  14.   std::cout << "first <-> last\n"
  15.     << My::distance(R(0), R(3))
  16.     << "\n\n";
  17. }


 
 
Très bien ça marche. Maintenant, c'est un peu dommage que le calcul de distance entre 2 RandomAccessIterator soit en temps linéaire. Ça veut dire que si notre iterator est sur un conteneur à accès aléatoire en temps constant, et bien, on perdrait ce bénéfice : on se retrouve à faire le même traitement que si on avait une liste. On parcours élément par élément et on compte. C'est une perte de temps, et c'est bien compliqué. Nous sommes tous relativement habitués à l'arithmétique des pointeurs : c'est quand même plus pratique (et rapide) de pouvoir faire 'p += n' que 'n' fois '++'. Je rappelle qu'un RandomAccessOperator permet des opérations telles que += et -= donc par extension + et -. Il serait donc inutile de faire n iéerations pour obtenir la distance.
std::iterator_traits<> nous permet d'obtenir la catégorie d'un type d'iterator. On va donc exploiter cette information pour prendre une décision lors du calcul de distance.
 

Code :
  1. namespace
  2. {
  3.   template<typename InputIterator, typename Tag>
  4.   struct DistanceWorker
  5.   {
  6.     static typename std::iterator_traits<InputIterator>::difference_type
  7.     distance(InputIterator first, InputIterator last)
  8.     {
  9.       // on utilise la version générique
  10.       return My::distance(first, last);
  11.     }
  12.   };
  14.   template<typename InputIterator>
  15.   struct DistanceWorker<InputIterator, std::random_access_iterator_tag>
  16.   {
  17.     static typename std::iterator_traits<InputIterator>::difference_type
  18.     distance(InputIterator first, InputIterator last)
  19.     {
  20.       return last - first;
  21.     }
  22.   };
  23. }
  25. namespace My
  26. {
  27.   // et hop, un petit sucre syntaxique pour faire en sorte que la déduction de types
  28.   // fasse tout le travail
  29.   template<typename InputIterator>
  30.   typename std::iterator_traits<InputIterator>::difference_type
  31.   distance2(InputIterator first, InputIterator last)
  32.   {
  33.     typedef typename std::iterator_traits<InputIterator>::iterator_category Tag;
  35.     return DistanceWorker<InputIterator, Tag>::distance(first, last);
  36.   }
  37. }


 
C'est gagné !
 
 
Il va de soit qu'une fois que le compilateur est passé la dessus, à grand coup d'inlining, on tombe sur une expression simple. Par exemple, si R est un RandomAccessIterator,  My:: distance2(R(M), R(N)) sera réduit -- à la compilation -- à l'expression (M - N). Et oui, tout ça pour ça :) Si vous trouvez que ça ne vaut pas la peine, la version générique My:: distance vous satisfera. Remarquez juste que si un jour, vous décidez que changez d'algorithme dans un cas particulier (ici, passage d'une boucle à une sous-traction), une simple recompilation suffira.
 
 
----
 
 
Le programme complet
 

Code :
  1. #include <iterator>
  2. #include <cstddef>
  3. #include <iostream>
  5. namespace My
  6. {
  7.   template<typename InputIterator>
  8.   typename std::iterator_traits<InputIterator>::difference_type
  9.   distance(InputIterator first, InputIterator last)
  10.   {
  11.     typename std::iterator_traits<InputIterator>::difference_type n = 0;
  13.     while (first != last)
  14.       {
  15. ++first;
  16. ++n;
  17.       }
  19.     return n;
  20.   }
  23.   template<typename T>
  24.   struct Forward
  25.     : std::iterator<std::forward_iterator_tag, T>
  26.   {
  27.     Forward(T v) : value(v)
  28.     { }
  30.     bool operator!=(const Forward &other) const
  31.     {
  32.       return this->value != other.value;
  33.     }
  35.     Forward& operator++()
  36.     {
  37.       std::cout << "++Forward\n";
  38.       this->value++;
  39.       return *this;
  40.     }
  42.     private:
  43.       T value;
  44.   };
  48.   template<typename T>
  49.   struct Random
  50.     : std::iterator<std::random_access_iterator_tag, T>
  51.   {
  52.     Random(T v) : value(v)
  53.     { }
  55.     bool operator!=(const Random &other) const
  56.     {
  57.       return this->value != other.value;
  58.     }
  60.     typename std::iterator<std::random_access_iterator_tag, T>::difference_type
  61.     operator-(const Random &other) const
  62.     {
  63.       return this->value - other.value;
  64.     }
  66.     Random& operator++()
  67.     {
  68.       std::cout << "++Random\n";
  69.       this->value++;
  70.       return *this;
  71.     }
  73.     private:
  74.       T value;
  75.   };
  76. }
  79. namespace
  80. {
  81.   template<typename InputIterator, typename Tag>
  82.   struct DistanceWorker
  83.   {
  84.     static typename std::iterator_traits<InputIterator>::difference_type
  85.     distance(InputIterator first, InputIterator last)
  86.     {
  87.       return My::distance(first, last);
  88.     }
  89.   };
  91.   template<typename InputIterator>
  92.   struct DistanceWorker<InputIterator, std::random_access_iterator_tag>
  93.   {
  94.     static typename std::iterator_traits<InputIterator>::difference_type
  95.     distance(InputIterator first, InputIterator last)
  96.     {
  97.       return last - first;
  98.     }
  99.   };
  100. }
  102. namespace My
  103. {
  104.   template<typename InputIterator>
  105.   typename std::iterator_traits<InputIterator>::difference_type
  106.   distance2(InputIterator first, InputIterator last)
  107.   {
  108.     typedef typename std::iterator_traits<InputIterator>::iterator_category Tag;
  110.     return DistanceWorker<InputIterator, Tag>::distance(first, last);
  111.   }
  112. }
  116. int main()
  117. {
  118.   typedef My::Forward<int> I;
  119.   typedef My::Random<int> R;
  122.   // complexité linéaire : normal
  123.   std::cout << "first <-> last\n"
  124.     << My::distance(I(0), I(3))
  125.     << "\n\n";
  128.   // complexité linéaire : aïe !
  129.   std::cout << "first <-> last\n"
  130.     << My::distance(R(0), R(3))
  131.     << "\n\n";
  134.   // complexité linéaire : normal
  135.   std::cout << "first <-> last\n"
  136.     << My::distance2(I(0), I(3))
  137.     << "\n\n";
  140.   // complexité 1 !
  141.   std::cout << "first <-> last\n"
  142.     << My::distance2(R(0), R(3))
  143.     << "\n\n";
  144. }


Message édité par Taz le 06-02-2005 à 16:03:43
Reply

Marsh Posté le 31-01-2005 à 21:55:28   

Reply

Marsh Posté le 31-01-2005 à 21:58:39    

Ca a l'air fresh, mais ca sert a quoi ?

Reply

Marsh Posté le 31-01-2005 à 22:06:57    

à gueuler sur les débutants : "va lire tous les autres "Sujets utiles" C++"

Reply

Marsh Posté le 31-01-2005 à 22:16:57    

:o Joce, tu veux pas agrandir cette saleté de fenêtre d'édition, j'en chie grave

Reply

Marsh Posté le 31-01-2005 à 23:14:08    

très instructif...
 
merci!

Reply

Marsh Posté le 31-01-2005 à 23:15:43    

j'ai pas terminé, faudra que je pas que j'oublie de boucler ça

Reply

Marsh Posté le 31-01-2005 à 23:27:18    

Taz a écrit :

:o Joce, tu veux pas agrandir cette saleté de fenêtre d'édition, j'en chie grave


 
hfr enhance [:petrus75]

Reply

Marsh Posté le 01-02-2005 à 12:04:44    

UP.
 
des questions ?

Reply

Marsh Posté le 01-02-2005 à 13:24:30    

voui une question
 

Citation :

Il vous reste donc une chose à faire : quand vous créez votre classe d'iterator, héritez publiquement de std::iterator<ce qui va bien>. Ça ne coûte rien :) (Voir plus bas pour un exemple.)


 
meuh les héritages sont privés dans l'exemple ...

Reply

Marsh Posté le 01-02-2005 à 15:26:55    

Si je ne me trompe pas ils sont publics puisque ce sont des structures et pas des classes...

Reply

Marsh Posté le 01-02-2005 à 15:26:55   

Reply

Marsh Posté le 01-02-2005 à 15:39:04    

au temps pour moi, j'ignorai que le mot clé struct implicitait un héritage public par défaut. Allez je m'autoflagelle d'un coup de stroustrup sur le crane :o

Reply

Marsh Posté le 01-02-2005 à 17:02:26    

++fab a écrit :

Allez je m'autoflagelle d'un coup de stroustrup sur le crane :o


 
Ouch :sweat:

Reply

Marsh Posté le 06-02-2005 à 16:03:59    

terminé

Reply

Marsh Posté le 06-02-2005 à 17:26:16    

un autre exemple de traits dans la bibliothèque standard du C++ : <limits>

Reply

Marsh Posté le 08-02-2005 à 00:01:59    

ça intéresse personne ? c'est trop technique ? l'exemple n'est pas assez concret ? ou quoi ?

Reply

Marsh Posté le 08-02-2005 à 00:02:40    

bin on ecrit pas des iterator tous les jours

Reply

Marsh Posté le 08-02-2005 à 00:06:32    

D'accord, mais bon, c'est pour présenter un concept général. Et je trouves qu'on néglige un peu les iterators : j'ai déjà donné un exexemple d'insert_iterator pour réaliser des insertions dans un dictionnaire en appliquant un petit traitement : c'est un petit paradigme.
 
J'ai voulu faire un peu concret, en m'appuyant sur les iterators, parler crument des traits, ça aurait encore plus bidesque

Reply

Marsh Posté le 08-02-2005 à 00:28:23    

Taz a écrit :

ça intéresse personne ? c'est trop technique ? l'exemple n'est pas assez concret ? ou quoi ?


 
Si c'est intéressant, mais peut etre que tout les gens intéressés ont lu le BS, et l'exemple qui est à peu près le meme  :p  
En fait, je pense que c'est un peu trop concret. Ce qui serait intéressant, ce serait de généraliser la bonne utilisation des traits dans un contexte plus général. Dans quels circonstances réaliser une conception qui pourrait efficacement tirer profit de l'utilisation des traits ? Je sais pas si je suis clair ...
 

Citation :

J'ai voulu faire un peu concret, en m'appuyant sur les iterators, parler crument des traits, ça aurait encore plus bidesque


meuh non !

Reply

Marsh Posté le 08-02-2005 à 12:06:29    

ca m'interresse beaucoup aussi, jme plonge dedans ce soir
 
merci beaucoup :jap:


---------------
-( BlackGoddess )-
Reply

Marsh Posté le 08-02-2005 à 13:35:53    

chrisbk a écrit :

bin on ecrit pas des iterator tous les jours


 
on devrait :o

Reply

Marsh Posté le 08-02-2005 à 13:40:48    

Taz a écrit :

ça intéresse personne ? c'est trop technique ? l'exemple n'est pas assez concret ? ou quoi ?


t'inquiète pas, j'ai mis tous tes topics C++ en favoris, je m'y réfère souvent ! :jap:
(récemment j'ai relu ton topic sur la spécialisation des templates, j'espérais pouvoir l'utiliser pour mon plugin Winamp mais je me suis aperçu que c'était un coup de canon pour tuer une mouche :/


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed