Contrainte sur les itérateurs.

Le
Mickaël Wolff
Bonjour,

Est-ce une erreur que de croire que la différence entre deux
itérateurs, avec l'opérateur -, fait sens ?

Je pose la question parce que je suis tombé sur un itérateur,
Gtk::TextBuffer::iterator, qui ne fournissait pas cet opérateur, ce qui
fait que l'itérateur se castait en bool (ce qui est ballot).

Finalement j'utilises std::difference. Mais c'est surprenant quand on
a l'habitude d'utiliser l'arithmétique des pointeurs, et que les
itérateurs (qui peuvent être confondus avec des pointeurs) ne le
supporte pas totalement.

Merci pour vos avis !
--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Jean-Marc Bourguet
Le #16484961
Mickaël Wolff
Est-ce une erreur que de croire que la différence entre deux itérateurs,
avec l'opérateur -, fait sens ?



Finalement j'utilises std::difference.



Les iterateurs sont une classification plus fine, certains (ceux a acces
aleatoire) fournissent -; pour d'autres std::difference fonctionne avec un
cout proportionnel a la valeur retournee (je ne me souviens plus si
std::difference a un cout constant pour les iterateurs a acces aleatoire ou
pas); pour les derniers (ostream_iterator par exemple), std::difference n'a
meme pas de sens.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Michael DOUBEZ
Le #16484951
Jean-Marc Bourguet a écrit :
Mickaël Wolff
Est-ce une erreur que de croire que la différence entre deux itérateurs,
avec l'opérateur -, fait sens ?





L'opérateur - n'est requis que pour les random_iterator.

Ça fait sens puisse la différence de pointeurs n'a d'intérêt que pour
une zone de mémoire contigüe.


Finalement j'utilises std::difference.





Vous devez parler de std::distance().


Les iterateurs sont une classification plus fine, certains (ceux a acces
aleatoire) fournissent -; pour d'autres std::difference fonctionne avec un
cout proportionnel a la valeur retournee



(je ne me souviens plus si
std::difference a un cout constant pour les iterateurs a acces aleatoire ou
pas);



Ça ne doit pas être garanti par le standard mais en pratique ça
m'étonnerais que ce ne soit pas le cas.

pour les derniers (ostream_iterator par exemple), std::difference n'a
meme pas de sens.



C'est surtout qu'il est impossible de comparer deux output_iterator. Par
contre, distance() fonctionne avec un istream_iterator par exemple
(l'intérêt doit quand même être limité)..


Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu
l'utilises ?


--
Michael
Jean-Marc Bourguet
Le #16484941
Michael DOUBEZ
Jean-Marc Bourguet a écrit :
> Mickaël Wolff >
>> Est-ce une erreur que de croire que la différence entre deux itérateurs,
>> avec l'opérateur -, fait sens ?

L'opérateur - n'est requis que pour les random_iterator.

Ça fait sens puisse la différence de pointeurs n'a d'intérêt que pour une
zone de mémoire contigüe.

>
>> Finalement j'utilises std::difference.

Vous devez parler de std::distance().



C'est bien ce a quoi je pensais, mais j'ai recopie ce qu'a ecrit Mickael.

Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu
l'utilises ?



Moi, aucun. J'ai du l'utiliser une fois pour l'essayer, ce qui explique
la confusion ci-dessus.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Michael DOUBEZ
Le #16484921
Jean-Marc Bourguet a écrit :
Michael DOUBEZ
Je n'ai jamais eu besoin d'utiliser distance(). Dans quel cas tu
l'utilises ?



Moi, aucun. J'ai du l'utiliser une fois pour l'essayer, ce qui explique
la confusion ci-dessus.



J'ai trouvé un exemple sur Google ou une personne avait besoin de
connaitre l'index d'un iterator. Et après réflexion, std::distance()
peut être utilisé pour connaitre le nombre d'éléments entre deux valeurs
dans un conteneur trié.

Un intérêt arrivera peut être dans certains cas (voir article ci-après).

L'argument sur size() est intéressant. Est ce que C++0x garanti
std::list::size() en O(1) ?

- - - - -
http://blog.emmanueldeloget.com/index.php/2008/03/25/124-le-futur-standard-c-nouvelle-version-du-draft
* STL Singly Linked Lists (N2543)* Par Matt Austern

Elles ont mis du temps à venir, mais elles sont enfin là : les listes
chainées simples font leur entrée dans la librairie standard du C++.
Accueillons la nouvelle venue avec le respect qui lui est du.

Concrètement, cet ajout prend la forme d'un nouveau conteneur nommé
std::forward_list (anciennement std::slist). La proposition de Matt
Austern fait certains choix particuliers qui sont rendus explicite par
l'interface de la classe. Ainsi, l'opération d'insertion est différente
de cette d'une std::list : le nouvel élément est inséré après le noeud
courant plutôt qu'avant. Ce choix est illustré par le nom de la fonction
d'insertion, qui devient std::forward_list::insert_after(). De même,
erase() disparait au profit de std::forward_list::erase_after(). Cela
peut poser des problèmes si les conteneurs sont manipulés par des
fonctions template.

Autre choix important : std::forward_list ne contient pas de méthode
size(). Pour trouver la taille d'une liste, il faudra utiliser
l'algorithme std::distance() (un algorithme d'une complexité linéaire).
L'auteur explique ce choix en deux phases :
1. avoir une méthode size() qui fonctionnerait en O(N) serait
contre-intuitif.
2. ajouter dans la classe une variable pour stocker la taille
courante (et transformer size() en une méthode de complexité constante)
implique de ne pas respecter l'un des principes d'architecture du
langage C++ (you pay for what you use) puisque les opérations de
maintenance de cette variable ainsi que sa présence même représentent
des coûts cachés pour le programmeur utilisateur.

--
Michael
James Kanze
Le #16484911
On Aug 6, 8:28 am, Mickaël Wolff
Est-ce une erreur que de croire que la différence entre deux
itérateurs, avec l'opérateur -, fait sens ?



Oui. Un itérateur itère. Logiquement, c'est tout ce qu'il doit
supporter. (Dans le cas de la STL, on y a ajouté d'autres
choses, et certains itérateurs STL supportent la soustraction.
Mais pas tous.)

Je pose la question parce que je suis tombé sur un itérateur,
Gtk::TextBuffer::iterator, qui ne fournissait pas cet
opérateur, ce qui fait que l'itérateur se castait en bool (ce
qui est ballot).



Un itérateur qui se convertit implicitement en bool me semble
assez louche aussi.

Fondamentalement, un itérateur supporte trois opérations :
accès à l'élement courant (éventuellement indirectement),
passage à l'élément suivant, et la détermination si on a fini ou
non. Trois fonctions, donc : element(), next() et isDone().
Puisqu'aucune de ces fonctions ne correspond réelement à une
opération définie sur les types de bases, tout surcharge
d'opérateur est un peu un abus. (Note bien que « abus » est
rélatif ; l'utilisation de ++ pour next() n'est certainement
pas si abusive que l'utilisation de + unaire pour isDone() --
que j'ai réelement vu conseillé. Tout est rélatif.)

Finalement j'utilises std::difference. Mais c'est surprenant
quand on a l'habitude d'utiliser l'arithmétique des pointeurs,
et que les itérateurs (qui peuvent être confondus avec des
pointeurs) ne le supporte pas totalement.



Oui. C'est le genre de problème qui arrive quand on surcharge
abusivement.

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Mickaël Wolff
Le #16485721
Michael DOUBEZ a écrit :

Finalement j'utilises std::difference.





Vous devez parler de std::distance().



Évidemment, mais le fait de devoir utiliser le type
iterator::difference_type pour recevoir le retour std::distance couplé
au manque de sommeil fait des ravages ;)

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Mickaël Wolff
Le #16485711
James Kanze a écrit :

Oui. Un itérateur itère.



C'est pourtant évident. Mais à force d'utiliser les outils pour autre
chose que ce qu'ils sont, on oublie leur utilité première.


Un itérateur qui se convertit implicitement en bool me semble
assez louche aussi.



Enjoy ;)



Oui. C'est le genre de problème qui arrive quand on surcharge
abusivement.



Ça m'apprendra.

Merci à tous pour vos réponses.

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Jean-Marc Bourguet
Le #16485961
Michael DOUBEZ
L'argument sur size() est intéressant. Est ce que C++0x garanti
std::list::size() en O(1) ?



Non. En fait, c'est incompatible avec la contrainte sur la complexite de
splice.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Michael DOUBEZ
Le #16486321
Jean-Marc Bourguet a écrit :
Michael DOUBEZ
L'argument sur size() est intéressant. Est ce que C++0x garanti
std::list::size() en O(1) ?



Non. En fait, c'est incompatible avec la contrainte sur la complexite de
splice.



Je suis d'accord mais le cout peut être amorti, par exemple en
maintenant une taille de liste et en l'invalidant en cas de splice; le
premier appel à size() calcule la taille de la liste en o(n) et mets à
jour le membre.

Il est rare d'avoir besoin d'une taille de liste et de splice en même
temps (ou même l'un ou l'autre).

--
Michael
Fabien LE LEZ
Le #16486311
On 06 Aug 2008 10:19:36 +0200, Jean-Marc Bourguet
L'argument sur size() est intéressant. Est ce que C++0x garanti
std::list::size() en O(1) ?



Non. En fait, c'est incompatible avec la contrainte sur la complexite de
splice.



Effectivement.

Apparemment certains implémenteurs ignorent cette contrainte, et
obtiennent ainsi un temps constant pour size(). Microsoft par exemple.
Publicité
Poster une réponse
Anonyme