Design: iterators et reverse_iterators

**Iradrille** · 26/03/2013, 12h36

Hello !

Je suis en train de coder une classe Vector pour un exo (les profs ont vraiment l'air de l'aimer cet exo, il revient souvent

),
et je bloque sur le design des iterators

Actuellement j'ai quelques chose du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
template <class T>
class Vector {
   ...
public:
   ...
   class const_iterator { ... };
   class iterator: public const_iterator { ... }
};

Ca me semble correct, bien que j'avais lu (sur StackOverflow il me semble, mais je retrouve plus le lien) que cet héritage n'avait pas lieu d'être et que c'était un hack. Ainsi que c'est le design utilisé dans la STL de Microsoft, mais pas dans celle de GCC.
J'ai essayé de regarder les sources pour vérifier, mais on s'y perd facilement.

Vous en pensez quoi de cet héritage ? Correct ? Peut être remplacé par quelques chose de mieux ?

Ensuite arrivent les reverse_iterator, ma première idée était de faire un héritage en diamant :

(Enfin plutot "carré", vu que d'un point de vu logique, les reverse_iterator et leurs équivalents dans l'autre sens sont "au même niveau".)

Mais la doc indique clairement que ce n'est pas la chose à faire (lien ici):

Envoyé par doc c++

template <class Iterator> class reverse_iterator;

Mais la... pour implémenter cette classe je bloque complétement. Il me faut une spécialisation par conteneur (enfin 2, const et non const) ?
Car il y a bien à différencier les 2 à un moment

L'héritage en diamant est-il vraiment à éviter ? ou est-ce une solution valable ?

L'idéal serait de n'avoir à fournir que 2 spécialisions (const et non const) et que ça marche avec tous les itérators, mais je me perd dans la syntaxe, c'est possible quelques chose du genre ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
template <class I>
class reverse_iterator { };
 
template <class I>
class reverse_iterator<I::iterator> {
	...
};

**Flob90** · 26/03/2013, 20h49

Bonsoir,

L'héritage n'est pas utile ici à mon avis.

Demandes toi ce qui va varier dans ton implémentation entre un un iterator et un const_iterator ? Tu devrais te rendre compte qu'il s'agit de variation dans les types. Tu devrais donc pouvoir écrire une classe template avec des paramètres représentant ces différentes variation dans les types : tu as ton iterator et ton const_iterator.

Comme te le suggère la bibliothèque standard, on peut implémenter les versions reverses à partir des versions normales : reverse_const_iterator à partir de const_iterator et reverse_iterator à partir de iterator (modulo le fait qu'iterator doive être bidirectionnel).

A nouveau l'analyse des variations des besoins de l'implémentation va te montrer que les types sont liés, tu peux donc utiliser les typedefs (ou mieux : les traits d'itérateur) pour définir les typedefs. Elle va aussi te montrer que les fonctions d'itération sont liées (croisées), tu peux donc, avec en donnée membre du type de l'itérateur dans le bon sens, utiliser ++ pour implémenter --. Note au passage que la norme te donne aussi l’existence de données membres du type de l'itérateur dans le premier sens.

La norme t'indique aussi une autre technique : utiliser l'héritage avec un classe iterator (défini dans le standard) pour implémenter l'ensemble de typedef minimal requis (*). Le point auquel tu dois faire attention est l'écriture du constructeur de reverse_iterator : tu dois pouvoir construire un reverse<const_iterator> depuis un reverse<iterator>.

(*) Si c'est une implémentation libre totalement isolée de la bibliothèque standard, tu peux prendre des libertés selon ce qui doit ou ne doit pas être en membres au profit de versions extérieurs, aussi bien pour certaines fonctions du conteneur proprement dit, qui pour les typedefs au profit de spécialisations de traits uniquement.

**koala01** · 26/03/2013, 21h27

Salut,

De manière générale, tu devrais peut etre un peu regarder du coté du fichier vector de ton compilateur et des fichiers qu'il inclus.

Sous gcc, les fichiers intéressant sont:

bits/stl_vector.h
bits/stl_iterator.h et
bits/stl_iterrator_base_types.h

(je ne suis pas sur que tous les compilateurs respectent cet arrangement, à toi de voir à quoi correspondent les différents fichiers sur le tien

Lorsqu'on les étudie attentivement, on se rend compte que tout part (peu ou prou) de deux strucutres vides (donc de taille 0

) : input_iterator_tag et output_iterator_tag.

ensuite, il y a une série de tag qui héritent de input_iterator_tag dans l'ordre
random_access_iterator_tag -> bidirectional_iterator_tag->forward_iterator_tag->input_iterator_tag

Puis vient la structure iterator, qui prend cinq paramètre template

Category (sera l'un des *iterator_tag)
Type (le type de donnée utilisé)
Distance (qui vaut par défaut la ptrdiff_t) qui représente la distance "par défaut" séparant deux éléments
Pointer (qui vaut par défaut type * ) qui représente un pointeur sur l'élément
Reference(qui vaut par déaut type &) qui représente une référence sur l'élément.

et qui défini un typedef pour chacun de ces paramètre template sous la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
template <typename Category, typename Type, typename Distance, 
          typename Pointer, typename Reference>
struct iterator
{
      typedef Category iterator_category;
      typedef Type        value_type;
      typedef Distance  difference_type;
      typedef Pointer   pointer;
      typedef Reference reference;
}

Suivent les "iterator_traits" en version constante et non constante, pour les instances, les pointeurs et les références, qui fournissent des typedefs pour ces cinq typedef en fonction de ce que tu donneras en paramètre, sous une forme qui correpspond pour les pointeurs à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
template<typename Tp>
    struct iterator_traits<Tp*>
    {
      typedef random_access_iterator_tag iterator_category;
      typedef Tp                         value_type;
      typedef ptrdiff_t                   difference_type;
      typedef Tp*                        pointer;
      typedef Tp&                        reference;
    };

Ca, c'est ce qu'on trouve dans bits/stl_iterrator_base_types.h

Dans stl_iterators.h, on trouve la définition de reverse_iterator, qui hérite de iterator

Enfin, on se rend compte que chaque classe qui manipule iterator (vector, pour l'exemple que j'ai donné) se contente d'un typedef iterator <pointer> pour définir son propre iterateur et d'un typedef iterator<constpointer> (voir du coté des iterator_traits

) pour son const_iterator et qu'il fait pareil pour ses reverse_iterator.

Du coup, on se rend compte que la logique est beaucoup plus simple et "parallèle":

(collection)::reverse_iterator -> (collection)::iterator (correspond à iterator<pointer>)
(collection)::const_reverse_iterator ->(collection)::const_iterator (correspond à iterator<const_pointer>)

Bref, iterator<const_pointer> n'ayant rien à voir avec iterator<pointer>, ce sont bel et bien deux hiérarchies différentes

**Emmanuel Deloget** · 26/03/2013, 23h35

Je rejoins mes deux coforumeurs - l'héritage, ici, me parait superfétatoire. Il est peut être mieux de ne pas le proposer, parce que tu vas rencontrer pas mal de problèmes à l'utilisation (même si la librairie standard de Dimkunware est basée sur cette approche ; je ne dis pas que, en soi, l'approche est mauvaise. Juste qu'elle requiert plus d'attention que l'approche non basée sur un héritage).

Est-ce que ton code à besoin d'être fidèle au standard C++98 ou non ? Si ce n'est pas le cas, alors tu n'auras peut-être pas besoin de te frotter aux tags et aux traits. Si c'est le cas, et bien, désolé. Non, en fait, pas trop : les itérateurs ne sont tout de même pas une bête horrible, et leurs requirements sont tout de même assez simples

**Iradrille** · 27/03/2013, 01h40

Envoyé par Flob90

Demandes toi ce qui va varier dans ton implémentation entre un un iterator et un const_iterator ? Tu devrais te rendre compte qu'il s'agit de variation dans les types. Tu devrais donc pouvoir écrire une classe template avec des paramètres représentant ces différentes variation dans les types : tu as ton iterator et ton const_iterator.

Justement, un iterator possède toutes les fonctions d'un const_iterator + les versions non const (d'ou l'héritage). Par exemple pour l'operator *, const_iterator ne fourni qu'une version const, iterator rajoute une version non const; c'est là que j'ai du mal à voir une autre alternative que l'héritage. (Ou double spécialisation de template ?)

Envoyé par Flob90

(*) Si c'est une implémentation libre totalement isolée de la bibliothèque standard, tu peux prendre des libertés selon ce qui doit ou ne doit pas être en membres au profit de versions extérieurs, aussi bien pour certaines fonctions du conteneur proprement dit, qui pour les typedefs au profit de spécialisations de traits uniquement.

Envoyé par Emmanuel Deloget

Est-ce que ton code à besoin d'être fidèle au standard C++98 ou non ? Si ce n'est pas le cas, alors tu n'auras peut-être pas besoin de te frotter aux tags et aux traits. Si c'est le cas, et bien, désolé. Non, en fait, pas trop : les itérateurs ne sont tout de même pas une bête horrible, et leurs requirements sont tout de même assez simples

Mon code n'a pas besoin de respecter à la lettre les standards (dans le sujet on me propose d'émuler un iterator par un simple typedef sur value_type*), mais j'aimerai vraiment faire quelque chose qui respecte les standards pour bien comprendre comment c'est fait.

(Pareil, j'ai rajouté une notion d'allocator pour coller à la STL, mais ça c'est beaucoup plus simple, sauf fuite mémoire qui m'a échapé.)

Envoyé par koala01

(je ne suis pas sur que tous les compilateurs respectent cet arrangement, à toi de voir à quoi correspondent les différents fichiers sur le tien

)

Lorsqu'on les étudie attentivement, on se rend compte que tout part (peu ou prou) de deux strucutres vides (donc de taille 0

) : input_iterator_tag et output_iterator_tag.

ensuite, il y a une série de tag qui héritent de input_iterator_tag dans l'ordre
random_access_iterator_tag -> bidirectional_iterator_tag->forward_iterator_tag->input_iterator_tag

Puis vient la structure iterator, qui prend cinq paramètre template

Category (sera l'un des *iterator_tag)
Type (le type de donnée utilisé)
Distance (qui vaut par défaut la ptrdiff_t) qui représente la distance "par défaut" séparant deux éléments
Pointer (qui vaut par défaut type * ) qui représente un pointeur sur l'élément
Reference(qui vaut par déaut type &) qui représente une référence sur l'élément.

et qui défini un typedef pour chacun de ces paramètre template sous la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
template <typename Category, typename Type, typename Distance, 
          typename Pointer, typename Reference>
struct iterator
{
      typedef Category iterator_category;
      typedef Type        value_type;
      typedef Distance  difference_type;
      typedef Pointer   pointer;
      typedef Reference reference;
}

Les fichiers sont différents sur VS (vector -> xmemory -> xmemory0 -> xutility) mais la hierarchie de classe est la même.

Mais malgré ça, j'ai vraiment du mal à voir comment (et pourquoi) un iterator ne devrait pas hériter de const_iterator. (Ya des #define partout, pas facile à lire

)

Un iterator est bien un const_iterator fournissant des fonctions supplémentaires ?! (Et je ne vois vraiment pas comment extraire ça pour en faire un template).

Envoyé par koala01

De manière générale, tu devrais peut etre un peu regarder du coté du fichier vector de ton compilateur et des fichiers qu'il inclus.

Sans savoir exactement ce que l'on cherche, c'est un peu comme chercher une eguille dans une botte de foin

Exemple pour retrouver les 5 parametres templates dont tu parles (en un seul bloc pour pas décourager la lecture ^^"):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// file: vector
iterator begin() _NOEXCEPT
		{	// return iterator for beginning of mutable sequence
		return (iterator(this->_Myfirst, this));
		}
 
// file: vector
template<class _Ty,
	class _Alloc = allocator<_Ty> >
	class vector
		: public _Vector_alloc<!is_empty<_Alloc>::value,
			_Vec_base_types<_Ty, _Alloc> >
	{	// varying size array of values
public:
	...
	typedef _Vector_alloc<!is_empty<_Alloc>::value,
		_Vec_base_types<_Ty, _Alloc> > _Mybase;
	...
	typedef typename _Mybase::iterator iterator;
 
// file: vector
		// TEMPLATE CLASS _Vector_alloc
template<bool _Al_has_storage,
	class _Alloc_types>
	class _Vector_alloc
		: public _Vector_val<typename _Alloc_types::_Val_types>
	{	// base class for vector to hold allocator with storage
	...
	} // rien d'interresant ici -> classe mère
 
// file: vector
		// TEMPLATE CLASS _Vector_val
template<class _Val_types>
	class _Vector_val
		: public _Container_base
	{	// base class for vector to hold data
public:
	typedef _Vector_val<_Val_types> _Myt;
 
	typedef typename _Val_types::value_type value_type;
	typedef typename _Val_types::size_type size_type;
	typedef typename _Val_types::difference_type difference_type;
	typedef typename _Val_types::pointer pointer;
	typedef typename _Val_types::const_pointer const_pointer;
	typedef typename _Val_types::reference reference;
	typedef typename _Val_types::const_reference const_reference;
 
	typedef _Vector_iterator<_Myt> iterator;
	typedef _Vector_const_iterator<_Myt> const_iterator;
// On retrouve les typdefs dont tu parlais :) !
 
// file: vector
		// TEMPLATE CLASS _Vector_iterator
template<class _Myvec>
	class _Vector_iterator
		: public _Vector_const_iterator<_Myvec>
	{	// iterator for mutable vector
public:
	typedef _Vector_iterator<_Myvec> _Myiter;
	typedef _Vector_const_iterator<_Myvec> _Mybase;
	typedef random_access_iterator_tag iterator_category;

Les dernières lignes de ce (long) bloc de code montrent l'héritage iterator -> const_iterator au sein de la STL (du coté de VS en tout cas), puis le début de la hiérarchie dont tu parlais, qui est ensuite définie dans d'autres fichiers.

Mais j'avoue avoir encore beaucoup de mal à décoder tout ça (retrouver des typedefs c'est simple, mais je vois pas vraiment comment un itérator ne pourrait être autre chose qu'un const_iterator (+ des fonctions non const).

**Flob90** · 27/03/2013, 03h28

La norme ne définit pas les fonctions que doit avoir un iterator et un const_iterator, elle définit uniquement un ensemble d'expression qui doit être valide selon la catégorie de l'itérateur. Je ne vois pas trop où est le besoin de deux versions. Et, j'ai pas vérifié, mais dans le cas de vector (grâce à la continuité en mémoire) T* et const T* doivent constituer des types d'itérateur tout à fait valables.

Détaillons un peu les besoins des types d'itérateurs dans le cas de vector (je simplifie un peu) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
//Iterator
T o;
Iterator<T> r,a,b; //T est le même que dans vector<T>
diffrence_type<Iterator<T>> n;
*r               ; //return T&
++r             ; //return Iterator<T>&
r++             ; //return const Iterator<T>&
r+=n            ; //return Iterator<T>&
r+n              ; //return Iterator<T> symétrique
b-a              ; //return difference_type
*r=o            ;
 
//ConstIterator
Iterator<T> r,a,b; //T est le même que dans vector<T>
diffrence_type<ConstIterator<T>> n;
*r               ; //return const T&
++r             ; //return ConstIterator<T>&
r++             ; //convertible const ConstIterator<T>&
r+=n            ; //return ConstIterator<T>&
r+n              ; //return ConstIterator<T> symétrique
b-a              ; //return difference_type

Dans les deux cas, le type d'itérateur doit être constructible par défaut, copiable et affectable.

Il existe aussi des conditions sur les opérateurs de comparaisons et les versions --/-/-= (c'est antisymétrique par rapport à ++/+/+=), je les omets ici pour simplifier. On remarque que la différence itérateur constant ou non se joue sur les types de certaines expressions et la validité de l'expression *r=o; ce qui est relié : si *r retourne un const T&, alors la syntaxe concernée ne peut être valide, si *r retourne un T&, alors la syntaxe est valide si T est affectable (ce qui est en générale le cas pour les éléments stockés dans un conteneur).

On peut déjà remarquer qu'en effet T* et const T* remplissent bien le rôle dans le cas de vector. Le retour des versions post-fixées est un temporaire dans ce cas, ce qui est bien "convertible" (bind) vers T* const / const T* const (le temporaire étant de type T* / const T*).

Dans le cas où l'on code, identifions ce qui modifie et ce qui ne modifie pas l'itérateur (c'est différent de l'objet) :
Modifie, donc nécessairement non-const : ++/+=/--/-=
Ne modifie pas : */+/- de plus leur retour ne peut affecter l'état de l'itérateur (le seul cas où la question se pose est *, mais le retour permet de modifier l'objet "pointé" par l'itérateur, pas l'itérateur en lui-même), ils peuvent donc être const dans tout les cas : aucune raison de faire plusieurs versions.

Tu dois donc pouvoir écrire une classe VectorIterateur de cette manière (juste l'interface) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
template<class T>
struct VectorIterator
{
  VectorIterator();
  VectorIterator(const VectorIterator&);
 
  VectorIterator& operator=(const VectorIterator&);
  //ou
  VectorIterator& operator=(VectorIterator);
  //idiomatique (copy n swap)
 
  T& operator*() const;
  VectorIterator& operator++();
 
  VectorIterator operator++(int);
  //ou
  const VectorIterator& operator++(int);
 
  VectorIterator& operator+=(size_t); //size_t à discuté
};
 
template<class T>
VectorIterator<T> operator+(const VectorIterator<T>&,size_t);
//ou
template<class T>
VectorIterator<T> operator+(VectorIterator<T>,size_t);
//idiomatique (appel à +=)
 
template<class T>
VectorIterator<T> operator+(size_t,const VectorIterator<T>&);
//ou
template<class T>
VectorIterator<T> operator+(size_t,VectorIterator<T>);
//idiomatique (symétrie)

Puis ensuite :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
template<class T>
struct Vector
{
  typedef VectorIterator<T> iterator;
  typedef VectorIterator<const T> const_iterator;
};

Il y a un point supplémentaire qui vient modifier cette interface (reste valide pour T* / const T*) : on doit pouvoir construire un const_iterator à partir d'un iterator. On peut faire ça en ajoutant (il faut conserver le second, sauf cas particulier) un constructeur de copie généralisé dans la classe d'itérateur (idem pour l'affectation) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template<class T>
struct VectorIterator
{
  //...
 
  template<class U>
  VectorIterator(const VectorIterator<U>&);
 
  template<class U>
  VectorIterator& operator=(const VectorIterator<U>&)
 
  //...
};

Selon les types sous-jasent tu devras jouer ou non avec du cast away constness. Dans les cas simple (typiquement T* et const T*) c'est inutile.

Avec ça tu devrais t'en sortir. Tu peux ensuite mener le même genre de raisonnement pour reverse_iterator, surtout que dans ce cas la norme te donne même l'interface exacte à avoir.

PS1: Ensuite il existe des typedef au sein des itérateurs, si c'est une implémentation libre de ces concepts j'aurais tendance à les mettre uniquement de manière externe dans des traits. Sinon une solution est de factoriser au sein d'une classe templateles typedef pour les ramener simplement dans les classes en ayant besoin, c'est ce que fait la classe iterator de la bibliothèque standard.

PS2: Il faut aussi réfléchir à comment construire l'itérateur, ce n'est pas nécessairement une question complexe, mais elle demande quand même réflexion et plusieurs solutions restent envisageable (l'objectif étant d'introduire le moins de dépendance et d'exposition).

**koala01** · 27/03/2013, 03h38

Envoyé par Iradrille

Justement, un iterator possède toutes les fonctions d'un const_iterator + les versions non const (d'ou l'héritage). Par exemple pour l'operator *, const_iterator ne fourni qu'une version const, iterator rajoute une version non const; c'est là que j'ai du mal à voir une autre alternative que l'héritage. (Ou double spécialisation de template ?)

Parce que iterator n'a pas de fonction constante, peut etre

En fait, un iterateur a strictement les mêmes fonctions qu'un iterateur constant, à la seule différence près de la (non) constance des valeurs renvoyées et des fonctions.

C'est là que l'intérêt des type_traits apparait

Les fichiers sont différents sur VS (vector -> xmemory -> xmemory0 -> xutility) mais la hierarchie de classe est la même.

Et pour cause : iterator, type_traits et **iterator_flag sont autant de classes / structures définies dans la norme

Il n'y a que les classes et structures préfixées par un _ qui soient propres au compilo

Un iterator est bien un const_iterator fournissant des fonctions supplémentaires ?! (Et je ne vois vraiment pas comment extraire ça pour en faire un template).

non, c'est un système tout à fait différent du fait de la constante des fonctions et des valeurs renvoyées, pour lequel on admet juste une conversion non constant ==> constant.

Sans savoir exactement ce que l'on cherche, c'est un peu comme chercher une eguille dans une botte de foin

là, je ne peux qu'être d'accord

Exemple pour retrouver les 5 parametres templates dont tu parles (en un seul bloc pour pas décourager la lecture ^^"):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// file: vector
iterator begin() _NOEXCEPT
		{	// return iterator for beginning of mutable sequence
		return (iterator(this->_Myfirst, this));
		}
 
// file: vector
template<class _Ty,
	class _Alloc = allocator<_Ty> >
	class vector
		: public _Vector_alloc<!is_empty<_Alloc>::value,
			_Vec_base_types<_Ty, _Alloc> >
	{	// varying size array of values
public:
	...
	typedef _Vector_alloc<!is_empty<_Alloc>::value,
		_Vec_base_types<_Ty, _Alloc> > _Mybase;
	...
	typedef typename _Mybase::iterator iterator;
 
// file: vector
		// TEMPLATE CLASS _Vector_alloc
template<bool _Al_has_storage,
	class _Alloc_types>
	class _Vector_alloc
		: public _Vector_val<typename _Alloc_types::_Val_types>
	{	// base class for vector to hold allocator with storage
	...
	} // rien d'interresant ici -> classe mère
 
// file: vector
		// TEMPLATE CLASS _Vector_val
template<class _Val_types>
	class _Vector_val
		: public _Container_base
	{	// base class for vector to hold data
public:
	typedef _Vector_val<_Val_types> _Myt;
 
	typedef typename _Val_types::value_type value_type;
	typedef typename _Val_types::size_type size_type;
	typedef typename _Val_types::difference_type difference_type;
	typedef typename _Val_types::pointer pointer;
	typedef typename _Val_types::const_pointer const_pointer;
	typedef typename _Val_types::reference reference;
	typedef typename _Val_types::const_reference const_reference;
 
	typedef _Vector_iterator<_Myt> iterator;
	typedef _Vector_const_iterator<_Myt> const_iterator;
// On retrouve les typdefs dont tu parlais :) !
 
// file: vector
		// TEMPLATE CLASS _Vector_iterator
template<class _Myvec>
	class _Vector_iterator
		: public _Vector_const_iterator<_Myvec>
	{	// iterator for mutable vector
public:
	typedef _Vector_iterator<_Myvec> _Myiter;
	typedef _Vector_const_iterator<_Myvec> _Mybase;
	typedef random_access_iterator_tag iterator_category;

Les dernières lignes de ce (long) bloc de code montrent l'héritage iterator -> const_iterator au sein de la STL (du coté de VS en tout cas), puis le début de la hiérarchie dont tu parlais, qui est ensuite définie dans d'autres fichiers.

En fait, la class _Vector_iterator (qui hérite effectivement de _Vector_const_iterator) n'est là que pour donner des alias de type, mais, sans doute parce que _Vector_const_iterator <Type> fournit par ailleurs un typedef (ou une structure) équivalent à iterator et un autre équivalent à const_iterator.

C'est en fait une classe "intermédiaire" qui permet de relier les itérateur à la collection manipulée

.

Mais j'avoue avoir encore beaucoup de mal à décoder tout ça (retrouver des typedefs c'est simple, mais je vois pas vraiment comment un itérator ne pourrait être autre chose qu'un const_iterator (+ des fonctions non const).

Parce que, "quelque part", tu as une classe partiellement spécialisée qui fournit des fonction non constante quand on a un objet non constant et des fonctions constantes quand on a un objet constant

Après, tout le reste ne sert qu'à "passer" l'objet (le vecteur

) sous une forme constante ou non à cette classe

**Iradrille** · 27/03/2013, 04h03

Merci pour les explications, je commence à y voir plus clair, je bosserai dessus demain à tête reposée, je rouvrirais le thread si je reste bloqué.

**Iradrille** · 31/03/2013, 06h35

Bon, je réouvre le topic, car j'ai beau regarder les sources de la STL (Microsoft, j'ai que celles la sous la main pour le moment) et les différentes "actions" que doivent implémenter les différents types d'iterators (ici) je reste bloqué

J'ai envie de coller aux specs, du coup j'ai défini les 5 tags, ainsi que 5 interfaces pour les tags. (J'ai omis output_iterator_tag car je voyais vraiment pas en quoi il était différent de input_iterator_tag au niveau des fonctions qu'il est sensé fournir. (De plus la doc MS est en désaccord avec les sources ...)
La spec (MS, comme les autres) dit que forward_iterator_tag hérite seulement d'input_iterator_tag, alors que les sources disent le contraire...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct forward_iterator_tag
	: public input_iterator_tag, output_iterator_tag
	{	// identifying tag for forward iterators
	};

Du coup, je vois pas trop le rôle de ce type d'itérateur (les autres sont plutôt clair

).

Mon code actuel pour mes itérateurs est le suivant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// tag
struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
 
// iterators
template <class Diff, class T, class Ptr, class Ref, class Cat>
struct iterator {
	typedef Diff difference_type;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef Cat iterator_category;
 
	iterator(pointer p = nullptr): m_ptr(p) { }
	template <class U, class UCat>
	iterator(const iterator<Diff, U, U*, U&, UCat>& it): iterator(it.ptr()) { }
 
	value_type operator*() const { return *ptr() };
	value_type operator->() const { return *ptr() };
	template <class U, class UCat>
	bool operator==(iterator<Diff, U, U*, U&, UCat> it) { return ptr() == it->ptr(); }
	template <class U, class UCat>
	bool operator!=(iterator<Diff, U, U*, U&, UCat> it) { return !it == *this; }
 
protected:
	virtual ~iterator() { }
 
	pointer& ptr() { return m_ptr; };
	pointer ptr() const { return m_ptr; };
 
private:
	pointer m_ptr;
};
 
template <class Diff, class T, class Ptr, class Ref, class Cat, class Iter>
struct input_iterator: public iterator<Diff, T, Ptr, Ref, Cat> {
	input_iterator(pointer p = nullptr): iterator(p) { }
	template <class U, class UCat, class Iter2> // TODO virer UCat ?
	input_iterator(const input_iterator<Diff, U, U*, U&, UCat, Iter2>& it): input_iterator(it.ptr()) { }
 
	Iter& operator++() { inc(); return *ptr(); };
	void operator++(int) { inc(); };
 
protected:
	virtual ~input_iterator() { }
 
	virtual void inc() = 0;
};
 
// TODO output_iterator
 
template <class Diff, class T, class Ptr, class Ref, class Cat, class Iter>
struct forward_iterator: public input_iterator<Diff, T, Ptr, Ref, Cat, Iter> {
	forward_iterator(pointer p = nullptr): input_iterator(p) { }
	template <class U, class UCat, class Iter2> // TODO virer UCat ?
	forward_iterator(const forward_iterator<Diff, U, U*, U&, UCat, Iter2>& it): forward_iterator(it.ptr()) { }
 
	Iter operator++(int) { Iter it(*this); inc(); return it; };
 
protected:
	virtual ~forward_iterator() { }
};
 
template <class Diff, class T, class Ptr, class Ref, class Cat, class Iter>
struct bidirectional_iterator: public forward_iterator<Diff, T, Ptr, Ref, Cat, Iter> {
	bidirectional_iterator(pointer p = nullptr): forward_iterator(p) { }
	template <class U, class UCat, class Iter2> // TODO virer UCat ?
	bidirectional_iterator(const bidirectional_iterator<Diff, U, U*, U&, UCat, Iter2>& it): 
                               bidirectional_iterator(it.ptr()) { }
 
	Iter& operator--() { dec(); return *ptr(); };
	Iter operator--(int) { Iter it(*this); dec(); return it; };
 
protected:
	virtual ~bidirectional_iterator() { }
 
	virtual void dec() = 0;
};
 
template <class Diff, class T, class Ptr, class Ref, class Cat, class Iter>
struct random_access_iterator: public bidirectional_iterator<Diff, T, Ptr, Ref, Cat, Iter> {
	random_access_iterator(pointer p = nullptr): bidirectional_iterator(p) { }
	template <class U, class UCat, class Iter2> // TODO virer UCat ?
	random_access_iterator(const random_access_iterator<Diff, U, U*, U&, UCat, Iter2>& it):
                               random_access_iterator(it.ptr()) { }
 
	Iter& operator+=(difference_type n) { add(n); return *this; }
	Iter& operator-=(difference_type n) { sub(n); return *this; }
	Iter operator+(difference_type n) const { Iter it(*this); it.add(n); return it; }
	friend Iter operator+(difference_type n, Iter it) { return it + n; }
	Iter operator-(difference_type n) const { Iter it(*this); it.sub(n); return it; }
	friend Iter operator-(difference_type n, Iter it) { return it - n; }
	difference_type operator+(Iter it) const { return static_cast<difference_type>(ptr() + it.ptr()); } // TODO extract method
	difference_type operator-(Iter it) const { return static_cast<difference_type>(ptr() - it.ptr()); }
	reference operator[](difference_type n) const { return *((*this) + n); }
 
protected:
	virtual ~random_access_iterator() { }
 
	virtual void add(difference_type) = 0;
	virtual void sub(difference_type) = 0;
};

Puis mes iterateurs de vectors :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// vector_iterator
template <class T>
struct vector_iterator: public random_access_iterator<ptrdiff_t, T, T*, T&,
                                                      random_access_iterator_tag, 
                                                      vector_iterator<T>> {
	vector_iterator(pointer p = nullptr): random_access_iterator(p) { }
	template <class U>
	vector_iterator(const vector_iterator<U>& it): vector_iterator(it.ptr()) { }
 
	~vector_iterator() { }
 
protected:
	virtual void add(difference_type n) { ptr() += n; }
	virtual void sub(difference_type n) { ptr() -= n; }
	virtual void dec() { --ptr(); }
	virtual void inc() { ++ptr(); }
};
 
template <class T>
class Vector
	...
public:
	typedef vector_iterator<T> iterator;
	typedef vector_iterator<const T> const_iterator;
	...
};

Mon code n'est pas fini, mais j'aimerai savoir si je suis sur la bonne voie ? (Il me manque l'opérateur = à définir dans iterator, ainsi qu'a rendre le code compilable

).

Par contre je comprend pas vraiment les constructeurs par copie template (si les types d'itérateurs sont compatibles, pas besoins d'ajouter un paramètre template ?)

Une autre question, a priori la STL n'utilise pas de fonctions virtuelles pour les itérateurs, si c'est possible je pense que je vais me satisfaire de cette solution, au moins le temps de la comprendre complètement, mais est-ce une solution viable ? (sans forcément être la meilleure solution).

Bon ensuite il faudra surement que je "joue" avec les spécialisations pour qu'un Vector<const Type>::const_iterator n'ai pas 2 const d'affilé lors de l'expansion des templates...

**koala01** · 31/03/2013, 08h07

Envoyé par Iradrille

Une autre question, a priori la STL n'utilise pas de fonctions virtuelles pour les itérateurs, si c'est possible je pense que je vais me satisfaire de cette solution, au moins le temps de la comprendre complètement, mais est-ce une solution viable ? (sans forcément être la meilleure solution).

En fait, c'est normal:

Pour ce qui est des collections, en tout cas, le choix de l'itérateur "qui va bien" et des fonctions qui y sont associées est résolu grâce aux template à la compilation et que, bien qu'il y ait compatibilité entre les itérateurs, elle se fait à un niveau qui ne nécessite aucune fonction virtuelle (au niveau des iterato_tags

)

Il faut cependant noter que, comme tout est de toutes façons géré en interne sous forme de pointeur, et que la taille d'un pointeur est clairement définie, on peut s'éviter malgré tout d'avoir à recompiler l'ensemble à chaque fois que l'on utilise une collection d'un type différent

Ce n'est, par contre, pas le cas pour les classes dérivées de basic_(i)(o)stream, qui elles, présentent quelques fonctions virtuelles pour pouvoir s'adapter au type de flux envisagé (par contre, je ne sais plus lesquelles de mémoire

)

**Médinoc** · 01/04/2013, 14h34

Envoyé par koala01

Ce n'est, par contre, pas le cas pour les classes dérivées de basic_(i)(o)stream, qui elles, présentent quelques fonctions virtuelles pour pouvoir s'adapter au type de flux envisagé (par contre, je ne sais plus lesquelles de mémoire

)

Il me semble que ces classes délèguent toute notion de virtualité à un objet interne dérivé de basic_streambuf.

**Iradrille** · 02/04/2013, 10h41

Envoyé par koala01

Pour ce qui est des collections, en tout cas, le choix de l'itérateur "qui va bien" et des fonctions qui y sont associées est résolu grâce aux template à la compilation et que, bien qu'il y ait compatibilité entre les itérateurs, elle se fait à un niveau qui ne nécessite aucune fonction virtuelle (au niveau des iterato_tags

)

Oui, en fait je comptais implémenter les différents opérateurs des itérateurs dans des classes abstraites, avec ces opérateurs qui utilisent des fonctions virtuelles pures. Comme ça l'écriture d'itérateurs derrière est très simple : il suffit d'implémenter 4 ou 5 fonctions, et les opérateurs sont déjà fournis. (cf 2ème diagramme)
Je pense que si la STL ne fait pas comme ça (du moins pour les conteneurs) c'est pour une question de performance, les fonctions virtuelles ne peuvent pas être inline (

), il y à un surcoût (non négligeable du fait de la simplicité des fonctions des itérateurs). Du coup ils préfèrent avoir du code copié / collé dans tous leurs itérateurs.

Actuellement j'ai quelques chose de plus simple cf 1er diagramme (qui doit, je pense être ce que fait la STL, en gros), et ça marche

Je pense quand même changer ça pour coller au 2eme diagramme (car ici les performances ne sont pas à prendre en compte).

base_iterator fourni simplement des typedefs.
Les classes abstraites iterator (fournie les opérations d'un itérateur trivial), et les autres jusque forward_iterator fournissent les opérateurs requis en dépendant de quelques fonctions virtuelles pures, qui sont donc à implémenter dans les classes vector_iterator, list_iterator, map_iterator etc...

Bref, merci de vos réponses qui m'ont permis de comprendre les bases pour voir comment tout ça s'organisais.

(Un peu honte quand même d'avoir bloqué aussi longtemps sur un problème aussi simple, mais bon...

)

(Oui le grand absent ici est output_iterator_tag, mais il ne me semble pas utile pour les conteneurs, seulement pour les flux.

Design: iterators et reverse_iterators

Langage C++

Discussions similaires

Partager

Partager