Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1186 connectés 

  FORUM HardWare.fr
  Programmation
  C++

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

 
 

Sujet(s) à lire :
    - [C++] Sujets utiles
 

 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

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

n°967373
Taz
bisounours-codeur
Posté le 31-01-2005 à 21:55:28  profilanswer
 

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
mood
Publicité
Posté le 31-01-2005 à 21:55:28  profilanswer
 

n°967376
Chronoklaz​m
Posté le 31-01-2005 à 21:58:39  profilanswer
 

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

n°967385
Taz
bisounours-codeur
Posté le 31-01-2005 à 22:06:57  profilanswer
 

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

n°967396
Taz
bisounours-codeur
Posté le 31-01-2005 à 22:16:57  profilanswer
 

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

n°967545
haazheel
Posté le 31-01-2005 à 23:14:08  profilanswer
 

très instructif...
 
merci!

n°967548
Taz
bisounours-codeur
Posté le 31-01-2005 à 23:15:43  profilanswer
 

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

n°967587
chrisbk
-
Posté le 31-01-2005 à 23:27:18  profilanswer
 

Taz a écrit :

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


 
hfr enhance [:petrus75]

n°968171
Taz
bisounours-codeur
Posté le 01-02-2005 à 12:04:44  profilanswer
 

UP.
 
des questions ?

n°968217
++fab
victime du syndrome IH
Posté le 01-02-2005 à 13:24:30  profilanswer
 

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 ...

n°968466
haazheel
Posté le 01-02-2005 à 15:26:55  profilanswer
 

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

mood
Publicité
Posté le 01-02-2005 à 15:26:55  profilanswer
 

n°968508
++fab
victime du syndrome IH
Posté le 01-02-2005 à 15:39:04  profilanswer
 

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

n°968602
haazheel
Posté le 01-02-2005 à 17:02:26  profilanswer
 

++fab a écrit :

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


 
Ouch :sweat:

n°973311
Taz
bisounours-codeur
Posté le 06-02-2005 à 16:03:59  profilanswer
 

terminé

n°973356
Taz
bisounours-codeur
Posté le 06-02-2005 à 17:26:16  profilanswer
 

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

n°974972
Taz
bisounours-codeur
Posté le 08-02-2005 à 00:01:59  profilanswer
 

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

n°974974
chrisbk
-
Posté le 08-02-2005 à 00:02:40  profilanswer
 

bin on ecrit pas des iterator tous les jours

n°974979
Taz
bisounours-codeur
Posté le 08-02-2005 à 00:06:32  profilanswer
 

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

n°974991
++fab
victime du syndrome IH
Posté le 08-02-2005 à 00:28:23  profilanswer
 

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 !

n°975258
blackgodde​ss
vive le troll !
Posté le 08-02-2005 à 12:06:29  profilanswer
 

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


---------------
-( BlackGoddess )-
n°975340
Joel F
Real men use unique_ptr
Posté le 08-02-2005 à 13:35:53  profilanswer
 

chrisbk a écrit :

bin on ecrit pas des iterator tous les jours


 
on devrait :o

n°975345
Harkonnen
Modérateur
Un modo pour les bannir tous
Posté le 08-02-2005 à 13:40:48  profilanswer
 

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)
mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

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

 

Sujets relatifs
conception site multilingueQuestion de conception .... je peche
[Conception] Petit soucis de conception d'un soft de compta perso (MAJintroduction a l'algoithmique
Conception schéma Entity Relationship[ASPX][C#] Création d'un nouveau composant, pb de conception
[BDD] Probleme de conception[Java] Problème de conception d'une classe GraphMap
insertion dans une std::list à partir d'un reverse_iterator[Java] Thread, TableModel et conception
Plus de sujets relatifs à : <iterator> : conception d'iterator, introduction aux traits

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.137 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR