Conteneur séquentiel et transformation

On Aug 10, 6:55 am, Gabriel Dos Reis <g...@cse.tamu.edu> wrote:

es...@lain.home (Marc Espie) writes:

[...]

> Si tu imposes a l'implementation qu'on peut retrouver le
> conteneur a partir de l'iterateur, ca augmente fortement la
> taille de l'iterateur.

Surtout que cela me semble donner lieu à du code spaghetti.

Surtout qu'imposer un tel contraint à l'interface rendrait de
nombreux itérateurs intéressants impossibles. Un itérateur n'est
pas (forcement) lié à une collection concrête ; on connaît les
itérateurs [io]stream_iterator, mais on pout aussi concevoir des
itérateurs qui réfèrent à plusieurs collections, ou à une partie
d'une collection. (Dans la practique, au moins. Formellement,
les itérateurs sont surspécifiés, avec des contraints qui
rendent beaucoup d'itérateurs intéressants non-conformes. Mais
dans la mesure qu'ils fonctionnent en practique, y compris avec
des implémentations les plus contraignantes, comme g++...)

--
James Kanze

James Kanze <james.kanze@gmail.com> writes:

| On Aug 10, 6:55 am, Gabriel Dos Reis <g...@cse.tamu.edu> wrote:
| > es...@lain.home (Marc Espie) writes:
|
| > [...]
|
| > > Si tu imposes a l'implementation qu'on peut retrouver le
| > > conteneur a partir de l'iterateur, ca augmente fortement la
| > > taille de l'iterateur.
|
| > Surtout que cela me semble donner lieu à du code spaghetti.
|
| Surtout qu'imposer un tel contraint à l'interface rendrait de
| nombreux itérateurs intéressants impossibles. Un itérateur n'est
| pas (forcement) lié à une collection concrête ; on conna ît les
| itérateurs [io]stream_iterator,

Je suppose que dans ce cas, l'iterateur retournerait ce sur quoi il
itère -- le flux.
Ce qui n'est pas un problème pour les [io]stream_iterator,
ni conceptuellement, ni pratiquement.


Le code spaghetti vient du fait que si je passe un iterateur à une
fonction, je devrais au minimum m'attendre à ce que cette fonction
prennent des actions *globales* sur ce conteneur -- remettre le
conteneur à zero, potentiellement invalider des itérateurs exista nts,
etc. Cela devient du n'importe quoi. Un itétrateur est une abstracti on
locale ; en faire une abstraction globale donnerait lieu à du code o ù on
n'a très peu de garanties sur la moindre fonction qui utilise un
itérateur selon l'interface abstraite. Imagine du code où on a d es
destructeurs et des goto, des setjmp/longjmp un peu n'importe où.

| mais on pout aussi concevoir des
| itérateurs qui réfèrent à plusieurs collections, ou à une partie
| d'une collection.

Exact.

| (Dans la practique, au moins. Formellement,
| les itérateurs sont surspécifiés, avec des contraints qui
| rendent beaucoup d'itérateurs intéressants non-conformes. Mais
| dans la mesure qu'ils fonctionnent en practique, y compris avec
| des implémentations les plus contraignantes, comme g++...)

En effet.

-- Gaby

Bonjour,

Merci à tous pour vos conseils et vos éclaircissements.

J'aimerais juste résumer pour être sûr d'avoir une meilleure approche
des itérateurs, et d'avoir pleinement conscience de leur nature profonde:
- un conteneur standard ne traque pas ces itérateurs
- un itérateur ne peut pas connaître sa validité (puisqu'il n'est pas
traqué, un conteneur ne peut pas invalider l'itérateur, à l'instar du
pointeur qui ne peut pas être invalidé après que l'objet pointé est
supprimé)
- un itérateur ne sait rien du conteneur, il connait juste les
éléments itérés et comment les accéder les uns par rapport aux autres
- les itérateurs sont conçus pour être éphémères et utilisés
immédiatement, donc il faut éviter au maximum le trafic d'itérateurs.

Une dernière question : pourquoi les algorithmes ne prennent pas des
paires d'itérateurs ?

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org

On Aug 13, 6:35 am, Mickaël Wolff <mickael.wo...@laposte.net> wrote:

J'aimerais juste résumer pour être sûr d'avoir une meilleure app roche
des itérateurs, et d'avoir pleinement conscience de leur nature profond e:
- un conteneur standard ne traque pas ces itérateurs
- un itérateur ne peut pas connaître sa validité (puisqu'il n'es t pas
traqué, un conteneur ne peut pas invalider l'itérateur, à l'instar du
pointeur qui ne peut pas être invalidé après que l'objet pointé e st
supprimé)
- un itérateur ne sait rien du conteneur, il connait juste les
éléments itérés et comment les accéder les uns par rapport aux autres

Selon la norme. Dans la pratique, elle ne interdit rien de tout
ça non plus ; la plupart des implémentations aujourd'hui ont
deux modes, et dans la mode debug, la collection traque bien les
itérateurs, etc., afin de pouvoir détecter les cas de
comportement indéfini, et de le définir.

- les itérateurs sont conçus pour être éphémères et utilis és
immédiatement, donc il faut éviter au maximum le trafic d'itérateur s.

Une dernière question : pourquoi les algorithmes ne prennent pas des
paires d'itérateurs ?

La vraie question, c'est pourquoi il en faut deux. Ça rend
beaucoup de choses intéressantes (comme des itérateurs
filtrants) nettement plus compliquées.

--
James Kanze

Mickaël Wolff <mickael.wolff@laposte.net> writes:

| Bonjour,
|
| Merci à tous pour vos conseils et vos éclaircissements.
|
| J'aimerais juste résumer pour être sûr d'avoir une meill eure
| approche des itérateurs, et d'avoir pleinement conscience de leur
| nature profonde:
| - un conteneur standard ne traque pas ces itérateurs

En pratique, non, mais ce n'est pas interdit par la norme.
Certaines implémentations en mode debug traquent certains itérate urs.
Mais ce n'est pas une garantie de la norme -- c'est une question de
« qualité d'implémentation »

| - un itérateur ne peut pas connaître sa validité (puisqu 'il n'est
| pas traqué, un conteneur ne peut pas invalider l'itérateur, à   l'instar
| du pointeur qui ne peut pas être invalidé après que l'obje t pointé est
| supprimé)

Ce n'est pas exactement vrai. Il y a bien la notion de « singular
iterator » Ce qui est vrai, par contre, c'est que la norme ne fournit
pas de fonction générale pour tester la validité d'un ità ©rateur.

| - un itérateur ne sait rien du conteneur, il connait juste les
| éléments itérés et comment les accéder les uns p ar rapport aux autres

Ce n'est pas vrai en général. Par contre la norme ne te fournit p as de
fonction pour récupérer le conteneur parcouru par l'itérateu r.

| - les itérateurs sont conçus pour être éphém ères et utilisés
| immédiatement, donc il faut éviter au maximum le trafic d'ità ©rateurs.

utiliser « localement »

| Une dernière question : pourquoi les algorithmes ne prennent pas d es
| paires d'itérateurs ?

ou un conteneur. C'es une bonne question.
La réponse traditionnelle est le manque de propostion dans ce sens.
Certaines personnes diront qu'il y a certains idiomes qui ne sont pas
possible avec les paires d'itérateurs. Ma réponse est « et alors ? »
On ne peut pas faire de la choucroute avec ls itérateurs non plus.

-- Gaby

James Kanze <james.kanze@gmail.com> writes:

[...]

| > - les itérateurs sont conçus pour être éphé mères et utilisés
| > immédiatement, donc il faut éviter au maximum le trafic d'it érateurs.
|
| > Une dernière question : pourquoi les algorithmes ne prennent pa s des
| > paires d'itérateurs ?
|
| La vraie question, c'est pourquoi il en faut deux. Ça rend
| beaucoup de choses intéressantes (comme des itérateurs
| filtrants) nettement plus compliquées.

Dans ce cas la réponse est simple : ne pas utiliser les paires
d'itérateurs si on veut faire des choses compliquées. Faire de la
choucroute avec les itérateurs est nettement plus compliqués qu'a vec les
ingrédients habituels.

-- Gaby

Le 13/08/2010 08:56, James Kanze a écrit :

- un itérateur ne sait rien du conteneur, il connait juste les
éléments itérés et comment les accéder les uns par rapport aux autres

Selon la norme. Dans la pratique, elle ne interdit rien de tout
ça non plus ; la plupart des implémentations aujourd'hui ont
deux modes, et dans la mode debug, la collection traque bien les
itérateurs, etc., afin de pouvoir détecter les cas de
comportement indéfini, et de le définir.

Donc en fait, fournir une couche supplémentaire par dessus la STL qui
fourniraient des itérateurs « intelligents » n'est pas absurde. Ce qui
serait absurde ce serait de l'imposer via la STL. C'st bien l'idée ?

Une dernière question : pourquoi les algorithmes ne prennent pas des
paires d'itérateurs ?

La vraie question, c'est pourquoi il en faut deux. Ça rend
beaucoup de choses intéressantes (comme des itérateurs
filtrants) nettement plus compliquées.

Ce que tu entends par itérateurs filtrant, ce serait par exemple un
itérateur qui parcours la collection selon un prédicat ?

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org

Mickaël Wolff <mickael.wolff@laposte.net> writes:

| Le 13/08/2010 18:16, Gabriel Dos Reis a écrit :
|
| > | - un itérateur ne peut pas connaître sa validité (pu isqu'il n'est
| > | pas traqué, un conteneur ne peut pas invalider l'itérateur, à l'instar
| > | du pointeur qui ne peut pas être invalidé après que l' objet pointé est
| > | supprimé)
| >
| > Ce n'est pas exactement vrai. Il y a bien la notion de « singular
| > iterator » Ce qui est vrai, par contre, c'est que la norme ne fou rnit
| > pas de fonction générale pour tester la validité d'un it érateur.
|
| Là encore, c'est l'équivalent du pointeur nul.

Non. Un itrateeur singulier est encore plus singulier qu'un pointeur
nul -- on peut quand même faire pas mal de choses avec un pointeur nul.

| La seule chose qu'on
| peut faire c'est comparer avec l'équivalent du pointeur null.

Ou le convertir à un autre pointeur nul, ou vers un booléen.

| On ne peut pas demander bool(it) comme on le ferait avec un smart pointer.

Je ne comprends pas ce que tu dis.

|
| > | - les itérateurs sont conçus pour être éphà ©mères et utilisés
| > | immédiatement, donc il faut éviter au maximum le trafic d'i térateurs.
| >
| > utiliser « localement »
|
| C'est ce que je voulais dire ;)
|
| > | Une dernière question : pourquoi les algorithmes ne prennent p as des
| > | paires d'itérateurs ?
| >
| > ou un conteneur. C'es une bonne question.
| > La réponse traditionnelle est le manque de propostion dans ce sens.
| > Certaines personnes diront qu'il y a certains idiomes qui ne sont pas
| > possible avec les paires d'itérateurs. Ma réponse est « et alors ? »
| > On ne peut pas faire de la choucroute avec ls itérateurs non plus.
|
| Par curiosité, quels idiomes sont impossibles avec la paire
| d'itérateurs ?

Voir l'autre branche de cette conversation.

-- Gaby

Mickaël Wolff <mickael.wolff@laposte.net> writes:

| Le 13/08/2010 08:56, James Kanze a écrit :
|
| >> - un itérateur ne sait rien du conteneur, il connait juste les
| >> éléments itérés et comment les accéder les un s par rapport aux autres
| >
| > Selon la norme. Dans la pratique, elle ne interdit rien de tout
| > ça non plus ; la plupart des implémentations aujourd'hui ont
| > deux modes, et dans la mode debug, la collection traque bien les
| > itérateurs, etc., afin de pouvoir détecter les cas de
| > comportement indéfini, et de le définir.
|
| Donc en fait, fournir une couche supplémentaire par dessus la STL
| qui fourniraient des itérateurs « intelligents » n'est pas absurde.

Exact. Il faut bien se rendre compte que les itérateurs de la STL, c'e st
quand même une sorte d'abstraction de bas niveau -- plus haut niveau q ue
les pointeurs brutes etc, mais quand même bas niveau.

L'un des apports fondamentaux de la STL, c'est le découplage des
conteneurs des algorithmes, via la notion d'itérateur et leur
classification en termes de complexité d'opérations basiques.

-- Gaby

On Aug 14, 9:55 pm, Mickaël Wolff <mickael.wo...@laposte.net> wrote:

Le 13/08/2010 18:16, Gabriel Dos Reis a écrit :

> > - un itérateur ne peut pas connaître sa validité
> > (puisqu'il n'est pas traqué, un conteneur ne peut pas
> > invalider l'itérateur, à l'instar du pointeur qui ne
> > peut pas être invalidé après que l'objet pointé est
> > supprimé)

> Ce n'est pas exactement vrai. Il y a bien la notion de
> « singular iterator » Ce qui est vrai, par contre, c'est
> que la norme ne fournit pas de fonction générale pour tester
> la validité d'un itérateur.

Là encore, c'est l'équivalent du pointeur nul. La seule chose
qu'on peut faire c'est comparer avec l'équivalent du pointeur
null. On ne peut pas demander bool(it) comme on le ferait avec
un smart pointer.

Ce n'est pas ce que la norme entend par « singular iterator ».

Grosso modo, il y a quatre catégories de pointeurs : pointeurs
à un objet, pointeurs « one past the end », pointeurs nuls, et
pointeurs invalides. Quand la norme parle des singular
iterators, c'est l'équivalent d'un pointeur invalide, non d'un
pointeur nul. Et qu'il n'y a pas d'équivalent d'un pointeur nul
chez les itérateurs.

> > Une dernière question : pourquoi les algorithmes ne
> > prennent pas des paires d'itérateurs ?

> ou un conteneur. C'es une bonne question.
> La réponse traditionnelle est le manque de propostion dans ce sens.
> Certaines personnes diront qu'il y a certains idiomes qui ne sont pas
> possible avec les paires d'itérateurs. Ma réponse est « et alors ? »
> On ne peut pas faire de la choucroute avec ls itérateurs non plus.

Par curiosité, quels idiomes sont impossibles avec la paire
d'itérateurs ?

Les idioms qui n'exigent qu'un seul itérateur ? Comment définir
un back_insertion_iterator s'il faut une paire d'itérateurs. (En
fait, c'est possible, de la même façon que istream_iterator est
possible même dans les cas où on a besoin de deux itérateurs :
on définit un itérateur « factice » dont la comparaison fait ce
qu'on veut. Mais c'est pas commode.)

--
James Kanze