find()

kanze

26/02/2004 à 14:22

Gabriel Dos Reis wrote in message
news:...

writes:

| Gabriel Dos Reis wrote in message
| news:...
| > writes:

| > | La norme parle des « past-the-end values ». Comment doit-on
| > | rendre cette expression en français ? La norme C parle des
| > | pointeurs « one past the last object » ; on pourrait poser la
| > | même question ici.

| > À mon grand regret (et aussi celui de BS), nombre de formulations
| > actuellemment présentes dans la norme sont des long listes de cas
| > particuliers. Dans la composante IPR de la charpente de
| > représentation de programmes C++ en C++ (The Pivot) que nous
| > développons ici,

| C'est quoi, la composante IPR ? (« independant program
| representation » ? Mais même alors, je ne suis pas bien avancé.)

IPR == Internal Program Representation
XPR == External Program Representation

Il y a deux ans ou trois, BS avait fait une présentation au comité
d'une bibliothèque appelée XTI. XTI a évolué depuis Novembre dernier
en « The Pivot ». Si tu as encore accès aux documents du comité, tu
devrais avoir les slides. Si tu es abonné à l'ACCU, tu devrais aussi
avoir accès aux slides de sa présentation à l'ACCU Spring Conference
2002.

Je n'ai pas actuellement accès. Ou au moins, qu'intermittamment. Mais
j'essaierai à trouver le document.

| Et c'est quoi, « The Pivot » ?

Un outil qu'on développe pour faire des choses avec des programmes que
les autres n'arrivent pas à faire ;-) (Sérieusement, voir ci-dessus
pour une description schématique)

| > nous utilisons naturellement la notion de suite au sens abstrait
| > du terme (et certainement proche de l'ingénieur en chef, mais
| > aussi matheux, Alex Stepanov). Je ne sais pas si je proposerais
| > une formulation équivalente pour adoption dans la norme, mais
| > voici ce que j'ai mis dans la documentation de IPR (traduction) :

| > 1.1.1 Suite

| > Une /suite/ est une application I --> T où le domaine I est un
| > sous-ensemble des entiers relatifs ZZ. Les suites considérées
| > dans IPR ont des domaines bornés. En conséquence, lorsque nous
| > parlons de suite, il est implicitement entendu que son domaine
| > est borné. Le cardinal du domaine d'une suite est appelée sa
| > /taille/ (notée /size/). Une suite Sigma : I --> T de taille
| > /n/ admet la décomposition canonique nu : I --> [0, n[ suivie
| > de [0, n[ --> T, où l'application nu (une indexation du domaine
| > I) est une application strictement croissante.

| Je ne vois pas a priori l'intérêt de passer par l'application I -->
| T. J'aurais probablement commencé directement par le [0 ; n[
| (élément de Z) --> T. Mais bon, je ne suis pas mathieux ; il y a
| probablement quelque chose qui m'a passé de côté.

Si tu commences directement par [0, n[ --> T, tu limites de manière
gratuite ce qui peut être considérée comme suite; et il va te devoir
faire des acrobaties -- à mon avis complètement gratuites -- lorsque
tu veux parler de sous-suites ou de suites adaptées.

En somme, donné la suite [0 ; n[, la sous-suite [5 ; n-5[ est aussi une
suite. Je comprends.

Voici une analogie, si tu as l'esprit un peu géomètre. [...]

Je ne l'ai pas, mais ça fait rien. Le mot sous-suite a fait le déclic.

| Une suite, en fait, c'est que ce qu'on appelle une séquence dans la
| norme, si j'ai bien compris.

Je crois que « sequence » se traduit aussi par « suite » en français
-- du moins, c'est ce que m'apprend mon éducation mathématique ;-)

C'est possible. Je connais la notion mathématique de suite en français.
Assez vaguement, parce que les seules maths que j'ai fait, c'est un
cours de Math générale A à la CNAM. Je ne sais pas comment on l'appelera
en anglais. Je connais la notion d'une séquence (sequence, en anglais)
dans la norme C++ -- là, c'est en anglais, évidemment. Curieusement, ça
ne m'était pas venu à l'ésprit à les rapprocher. Probablement parce que
mes maths sont tellement anciennes, et qu'elles ne se rapprochent en
rien, ou au moins, ne s'en rapprochaient en rien dans la passée, à ce
que je fais en informatique. Si je reconnais l'importance de la façon de
penser qui y était enseigné, jusqu'ici, il y a eu fort peu de
connaissances concrète qui m'ont servies.

| > 1.1.2 Itérateur

| > Un itérateur est un couple de suite et d'entier appelé
| > /position/. Un itérateur (s, i) est /valide pour indirection/
| > si sa position est dans les bornes de l'indexation du domaine
| > de s, i.e. si i est positif et strictement plus petit que la
| > taille de s. Les itérateurs particuliers (s, 0) et (s, size(s))
| > sont respectivement appelés les itérateurs /first/ et
| > /one-past-the-end/ de s.

| J'ai un problème tout de suite, mais vu que tu en parles par la suite...

Mais « sequence » en anglais se traduit par « suite » en français, tu
ne peux pas être perdu :-)

D'accord : I have a problem all of a sequence... (En allemand, il y a
une forme d'humeur qui consiste entièrement en ce genre de
translitérations. Je n'ai jamais vu l'équivalent en français. Peut-être
parce qu'il ne marche, évidemment, que si on a une bonne connaissance
des deux langues.)

| > Exprès, je n'ai pas traduit /first/ et /one-past-the-end/. Mais,
| > cela te donne au moins une idée de ce que /one-past-the-end/
| > représente de manière abstraite. À noter que cette formulation de
| > one-past-the-end s'applique même si la suite est de taille nulle.

| En effet. En fait, j'ai démandé la traduction, mais je suis bien
| d'accord qu'il faut commencer par bien définir la chose dans la
| langue d'origine.

| > Je prétends que pour tous les containers (au moins ceux de la
| > bibliothèque standard), cette définition s'applique et, de plus,
| > est générale.

| Pas de problème avec les itérateurs issus des collections standard.
| Si j'ai bien compris l'intérêt de la STL, en revanche, ce n'en sont
| qu'une petite partie.

Tout à fait, mais la définition que je donne s'applique aussi à
n'importe quel itérateur issu de n'importe quelle suite -- c'était le
but de l'exercice de définir d'abord une suite :-). Un itérateur ne
vient pas comme ça, pouf, de nulle part. En particulier, tu ne peux
pas parler de one-past-the-end si tu n'as pas déjà la notion de suite
(bornée).

Le problème que je vois, a priori, c'est que ta suite est par définition
bornée. Or que dans la pratique, il est fort utile d'avoir des
itérateurs dont on ne reconnaît la fin que quand on y arrive. Et qui
sont potentiellement infinis en théorie, à condition que dans la
pratique...

| > Je crois que seuls les std::istream_iterator<>
| > std::ostream_iterator<> résistent à cette définition, mais alors
| > il est aussi vrai qu'ils ne sont attachés à aucune suite au sens
| > propre du terme (comme défini au 1.1.1).

| C'est le problème que j'ai toujours eu avec les itérateurs standard
| (mais sur un plan plus pragmatique). Les itérateurs de flux n'en
| sont qu'un exemple -- comment définir un itérateur standard quand la
| taille (ou la fin) n'est pas connue d'avance. Même une chaîne de
| caractères de type C pose le problème -- qu'on résoud dans ce cas-là
| en cherchant la fin avec des moyens autre que les itérateurs STL.

Là, je ne te suis pas. Si tu as la notion de suite, alors la notion
d'itérateur vient tout seul : c'est l'association d'une suite avec un
entier (position d'un élément dans la suite). Tu n'as pas besoin que
la taille soit connue d'avance. La notion de taille ne devient
critique que lorsque tu veux définir la notion de «
one-past-the-end ». Il me semble aller de bon sens de parler d'un
élément au delà de la fin seulement si on peut parler de fin, non ?

En effet. C'est un des problèmes que j'ai avec les itérateurs STL. Comme
tu dis ci-dessus : « Les suites considérées dans IPR ont des domaines
bornés. » Or, dans la pratique, j'ai assez souvent besoin des suites qui
ne sont pas bornées, ou dont la borne supérieur n'est pas connue
d'avance. std::istream_iterator en serait un exemple type. En fait, il
se trouve que dans mes programmes, je me sers plus souvent de l'autre
«@itérateur » de la norme : std::basic_streambuf. qui m'apporte souvent
un surcharge (gestion de buffer, d'erreur, etc.) dont je n'ai pas
besoin. Et qui a un coût en temps d'exécution non negligible -- la
résolution dynamique fait qu'ils sont plus souples à l'utilisation qu'un
itérateur STL, mais c'est un avantage qui se paie, comme tu le sais.

Mais on entre alors dans la discussion itérateur simple -- itérateur
double. Qui est en quelque sort indépendant du concept abstrait ; on
peut bien implémenter les itérateurs tels que tu les as définis
ci-dessus des deux façons. Je dirais même que dans la mésure que
l'itérateur a une suite comme premier élément du couple, et que la suite
(telle que tu l'as définie) connaît sa fin, on s'attendrait
intuitivement que l'itérateur connaît aussi sa fin, et qu'on n'en a
besoin donc que d'un. C'est peut-être ce qui me gène dans cette
définition, d'ailleurs -- au niveau de l'implémentation, des itérateurs
STL ne connaissent pas la suite. Ils désigne un objet, et ils ont un
moyen pour naviguer à partir de cet objet, pour arriver à un autre
objet. Mais tant que je n'ai qu'un seul itérateur STL, c'est une suite
sans bornes (conceptuellement, au moins). Un itérateur, ne connaissant
les limites, ne connaît toujours que la suite infinie [-oo ; +oo]. Quand
je fais v.begin() (ou v est un std::vector), moi, le programmeur, sait
que cet itérateur correspond au couple ([0 ; v.size()[, 0). Pour
l'itérateur, en revanche, tout ce qu'il sait (formellement), c'est :
[-oo ; +oo], 0.

À noter que si tu as une chaîne de caractères de type C, tu connais
la taille, c'est que ce que te donne strlen().

Et comment est-ce que j'implémente strlen() ? En termes des suites et
des itérateurs ? strlen(), c'est bien le résultat de std::count_if, non
(avec un prédicate « true ») ?

Je cerche, conceptuellement, à me tenir au concept d'itérateur. Une fois
que j'ai fait strlen(), et que j'ai son résultat, j'ai effectivement une
suite sur un domaine borné, et ça entre dans la moule. Mais est-ce que
tu ne trouves pas que ça serait intéressant que l'implémentation de
strlen() utilise le concept d'itérateur. Dans la pratique, évidemment,
il peut l'utiliser, parce que la mémoire est finie. Donc, std::count(
start, quelqueChoseDeSuffisammentAudelaDuStart, '') fait l'affaire.
C'est peut-être juste une question de goût, mais je trouve que ça manque
d'élégance.

| Formellement, j'ai l'impression d'une circularité dans la
| définition,

Quelle définition ?

Les définitions dans la norme. C'est peut-être simplement un effet d'une
manque de définitions, mais j'ai l'impression qu'une suite, c'est en fin
de compte quelque chose qui est définie par les itérateurs, et que la
définition d'un itérateur, c'est quelque chose dont un paire définit une
suite.

| dès qu'on veut définir l'itérateur sans y introduire la notion d'une
| collection réele figée. La séquence est définie par les itérateurs,
| et la définition d'un itérateur fait référence à la séquence.

Dans la définition que j'ai donnée, je n'ai pas défini une suite en
termes d'itérateurs. Il n'y a pas de circularité.

Non. Je pensais déjà à la norme. J'ai sauté quelque démarches par
rapport à ce que tu disais.

| Je crois que ton début est bien : on a une application [0 ; n[ -> T.
| Même si n n'est pas forcement connu d'avance. Le problème, c'est que

Non, il ne faut pas insister que le domaine soit [0, n[. Il suffit
qu'il soit un sous-ensemble de ZZ ;

(Juste une petite question : je ne suis pas mathématicien. Alors, en
quoi est-ce que ZZ est différent de Z ?)

en particulier, il n'y a pas besoin que la suite soit bornée avant de
parler d'itérateur. Tu n'as besoin de cette hypothèse que lorsque tu
veux parler de one-past-the-end.

Entendu. C'est donc une limitation des itérateurs STL:-).

| les itérateurs ne dépendent pas d'une collection, où n'en dépendent
| qu'indirectement.

Les itérateurs itèrent sur quelque chose, qui est une suite.

Et la définition de suite est déjà donnée. D'accord.

Pour l'instant, je crois, on parle des « itérateurs » au sens le plus
général, et pas que des itérateurs STL. C'est peut-être là où je t'ai
mal compris -- je pensais tout de suite à la STL uniquement.

| Donc, si j'ai un std::vector< int > qui contient des entiers
| aléatoire, je peux bien vouloir en définir un paire d'itérateurs qui
| itère que sur les valeurs impaires. Une définition d'itérateur doit
| prendre ceci en compte.

Parfaitement, c'est pour cela que tu as besoin

(1) soit de pouvoir parler de sous-suites ;
(2) soit de décider librement de la position i dans (s, i).

Soit...soit, ou et...et ?

Ou c'est peut-être deux façons de dire la même chose ? Si mon vecteur
est la suite V, et les valeurs impaires la suite V', le couple (V,i),
associé à des règles de positionnement de i, définit une bijection sur
(V',i'), qui est une itérateur dans V'.

Les deux conditions ci-dessus ne sont qu'une expression de la même
idée : pouvoir construire de nouvelles suites à partir d'anciennes.

| Pour l'histoire, en Java, un itérateur est toujours défini par
| rapport à une collection (éventuellement virtuelle) -- la définition
| de l'itérateur sur les valeurs paires ci-dessus commence par la
| définition d'une collection qui est une vue sur la collection
| originale.

Donc, si tu as ce brackground de Java, tu n'as pas pu être perdu
par la définition que j'ai donnée ;-)

Non plus. Le seul problème, c'est précisement que j'ai essayé à la
limiter tout de suite à des itérateurs STL, sans voir plus loin que le
bout de mon nez.

| (Typiquement, en révanche, l'implémentation se fait à l'envers -- on
| définit la collection en fonction de l'itérateur.)

Tout le monde sait bien qu'une implémentation n'est qu'une
traduction d'une abstraction et qu'en générale une bonne traduction
n'est pas celle qui traduit mot à mot :-)

Tout à fait. De même que le choix itérateur simple/itérateur double est
en fait un choix de la traduction -- que dans ta définition, l'itérateur
abstrait contient l'information sur sa fin n'est pas un argument pour ou
contre l'une des traductions. (Il y en a d'autres, mais ça c'est une
autre histoire.)

--
James Kanze GABI Software mailto:
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16

Gabriel Dos Reis <gdr@cs.tamu.edu> wrote in message
news:<m3znb7cu8r.fsf@merlin.cs.tamu.edu>...

kanze@gabi-soft.fr writes:

| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote in message
| news:<m34qtg7jzl.fsf@merlin.cs.tamu.edu>...
| > kanze@gabi-soft.fr writes:

| > | La norme parle des « past-the-end values ». Comment doit-on
| > | rendre cette expression en français ? La norme C parle des
| > | pointeurs « one past the last object » ; on pourrait poser la
| > | même question ici.

| > À mon grand regret (et aussi celui de BS), nombre de formulations
| > actuellemment présentes dans la norme sont des long listes de cas
| > particuliers. Dans la composante IPR de la charpente de
| > représentation de programmes C++ en C++ (The Pivot) que nous
| > développons ici,

| C'est quoi, la composante IPR ? (« independant program
| representation » ? Mais même alors, je ne suis pas bien avancé.)

IPR == Internal Program Representation
XPR == External Program Representation

Il y a deux ans ou trois, BS avait fait une présentation au comité
d'une bibliothèque appelée XTI. XTI a évolué depuis Novembre dernier
en « The Pivot ». Si tu as encore accès aux documents du comité, tu
devrais avoir les slides. Si tu es abonné à l'ACCU, tu devrais aussi
avoir accès aux slides de sa présentation à l'ACCU Spring Conference
2002.

Je n'ai pas actuellement accès. Ou au moins, qu'intermittamment. Mais
j'essaierai à trouver le document.

| Et c'est quoi, « The Pivot » ?

Un outil qu'on développe pour faire des choses avec des programmes que
les autres n'arrivent pas à faire ;-) (Sérieusement, voir ci-dessus
pour une description schématique)

| > nous utilisons naturellement la notion de suite au sens abstrait
| > du terme (et certainement proche de l'ingénieur en chef, mais
| > aussi matheux, Alex Stepanov). Je ne sais pas si je proposerais
| > une formulation équivalente pour adoption dans la norme, mais
| > voici ce que j'ai mis dans la documentation de IPR (traduction) :

| > 1.1.1 Suite

| > Une /suite/ est une application I --> T où le domaine I est un
| > sous-ensemble des entiers relatifs ZZ. Les suites considérées
| > dans IPR ont des domaines bornés. En conséquence, lorsque nous
| > parlons de suite, il est implicitement entendu que son domaine
| > est borné. Le cardinal du domaine d'une suite est appelée sa
| > /taille/ (notée /size/). Une suite Sigma : I --> T de taille
| > /n/ admet la décomposition canonique nu : I --> [0, n[ suivie
| > de [0, n[ --> T, où l'application nu (une indexation du domaine
| > I) est une application strictement croissante.

| Je ne vois pas a priori l'intérêt de passer par l'application I -->
| T. J'aurais probablement commencé directement par le [0 ; n[
| (élément de Z) --> T. Mais bon, je ne suis pas mathieux ; il y a
| probablement quelque chose qui m'a passé de côté.

Si tu commences directement par [0, n[ --> T, tu limites de manière
gratuite ce qui peut être considérée comme suite; et il va te devoir
faire des acrobaties -- à mon avis complètement gratuites -- lorsque
tu veux parler de sous-suites ou de suites adaptées.

En somme, donné la suite [0 ; n[, la sous-suite [5 ; n-5[ est aussi une
suite. Je comprends.

Voici une analogie, si tu as l'esprit un peu géomètre. [...]

Je ne l'ai pas, mais ça fait rien. Le mot sous-suite a fait le déclic.

| Une suite, en fait, c'est que ce qu'on appelle une séquence dans la
| norme, si j'ai bien compris.

Je crois que « sequence » se traduit aussi par « suite » en français
-- du moins, c'est ce que m'apprend mon éducation mathématique ;-)

C'est possible. Je connais la notion mathématique de suite en français.
Assez vaguement, parce que les seules maths que j'ai fait, c'est un
cours de Math générale A à la CNAM. Je ne sais pas comment on l'appelera
en anglais. Je connais la notion d'une séquence (sequence, en anglais)
dans la norme C++ -- là, c'est en anglais, évidemment. Curieusement, ça
ne m'était pas venu à l'ésprit à les rapprocher. Probablement parce que
mes maths sont tellement anciennes, et qu'elles ne se rapprochent en
rien, ou au moins, ne s'en rapprochaient en rien dans la passée, à ce
que je fais en informatique. Si je reconnais l'importance de la façon de
penser qui y était enseigné, jusqu'ici, il y a eu fort peu de
connaissances concrète qui m'ont servies.

| > 1.1.2 Itérateur

| > Un itérateur est un couple de suite et d'entier appelé
| > /position/. Un itérateur (s, i) est /valide pour indirection/
| > si sa position est dans les bornes de l'indexation du domaine
| > de s, i.e. si i est positif et strictement plus petit que la
| > taille de s. Les itérateurs particuliers (s, 0) et (s, size(s))
| > sont respectivement appelés les itérateurs /first/ et
| > /one-past-the-end/ de s.

| J'ai un problème tout de suite, mais vu que tu en parles par la suite...

Mais « sequence » en anglais se traduit par « suite » en français, tu
ne peux pas être perdu :-)

D'accord : I have a problem all of a sequence... (En allemand, il y a
une forme d'humeur qui consiste entièrement en ce genre de
translitérations. Je n'ai jamais vu l'équivalent en français. Peut-être
parce qu'il ne marche, évidemment, que si on a une bonne connaissance
des deux langues.)

| > Exprès, je n'ai pas traduit /first/ et /one-past-the-end/. Mais,
| > cela te donne au moins une idée de ce que /one-past-the-end/
| > représente de manière abstraite. À noter que cette formulation de
| > one-past-the-end s'applique même si la suite est de taille nulle.

| En effet. En fait, j'ai démandé la traduction, mais je suis bien
| d'accord qu'il faut commencer par bien définir la chose dans la
| langue d'origine.

| > Je prétends que pour tous les containers (au moins ceux de la
| > bibliothèque standard), cette définition s'applique et, de plus,
| > est générale.

| Pas de problème avec les itérateurs issus des collections standard.
| Si j'ai bien compris l'intérêt de la STL, en revanche, ce n'en sont
| qu'une petite partie.

Tout à fait, mais la définition que je donne s'applique aussi à
n'importe quel itérateur issu de n'importe quelle suite -- c'était le
but de l'exercice de définir d'abord une suite :-). Un itérateur ne
vient pas comme ça, pouf, de nulle part. En particulier, tu ne peux
pas parler de one-past-the-end si tu n'as pas déjà la notion de suite
(bornée).

Le problème que je vois, a priori, c'est que ta suite est par définition
bornée. Or que dans la pratique, il est fort utile d'avoir des
itérateurs dont on ne reconnaît la fin que quand on y arrive. Et qui
sont potentiellement infinis en théorie, à condition que dans la
pratique...

| > Je crois que seuls les std::istream_iterator<>
| > std::ostream_iterator<> résistent à cette définition, mais alors
| > il est aussi vrai qu'ils ne sont attachés à aucune suite au sens
| > propre du terme (comme défini au 1.1.1).

| C'est le problème que j'ai toujours eu avec les itérateurs standard
| (mais sur un plan plus pragmatique). Les itérateurs de flux n'en
| sont qu'un exemple -- comment définir un itérateur standard quand la
| taille (ou la fin) n'est pas connue d'avance. Même une chaîne de
| caractères de type C pose le problème -- qu'on résoud dans ce cas-là
| en cherchant la fin avec des moyens autre que les itérateurs STL.

Là, je ne te suis pas. Si tu as la notion de suite, alors la notion
d'itérateur vient tout seul : c'est l'association d'une suite avec un
entier (position d'un élément dans la suite). Tu n'as pas besoin que
la taille soit connue d'avance. La notion de taille ne devient
critique que lorsque tu veux définir la notion de «
one-past-the-end ». Il me semble aller de bon sens de parler d'un
élément au delà de la fin seulement si on peut parler de fin, non ?

En effet. C'est un des problèmes que j'ai avec les itérateurs STL. Comme
tu dis ci-dessus : « Les suites considérées dans IPR ont des domaines
bornés. » Or, dans la pratique, j'ai assez souvent besoin des suites qui
ne sont pas bornées, ou dont la borne supérieur n'est pas connue
d'avance. std::istream_iterator en serait un exemple type. En fait, il
se trouve que dans mes programmes, je me sers plus souvent de l'autre
«@itérateur » de la norme : std::basic_streambuf. qui m'apporte souvent
un surcharge (gestion de buffer, d'erreur, etc.) dont je n'ai pas
besoin. Et qui a un coût en temps d'exécution non negligible -- la
résolution dynamique fait qu'ils sont plus souples à l'utilisation qu'un
itérateur STL, mais c'est un avantage qui se paie, comme tu le sais.

Mais on entre alors dans la discussion itérateur simple -- itérateur
double. Qui est en quelque sort indépendant du concept abstrait ; on
peut bien implémenter les itérateurs tels que tu les as définis
ci-dessus des deux façons. Je dirais même que dans la mésure que
l'itérateur a une suite comme premier élément du couple, et que la suite
(telle que tu l'as définie) connaît sa fin, on s'attendrait
intuitivement que l'itérateur connaît aussi sa fin, et qu'on n'en a
besoin donc que d'un. C'est peut-être ce qui me gène dans cette
définition, d'ailleurs -- au niveau de l'implémentation, des itérateurs
STL ne connaissent pas la suite. Ils désigne un objet, et ils ont un
moyen pour naviguer à partir de cet objet, pour arriver à un autre
objet. Mais tant que je n'ai qu'un seul itérateur STL, c'est une suite
sans bornes (conceptuellement, au moins). Un itérateur, ne connaissant
les limites, ne connaît toujours que la suite infinie [-oo ; +oo]. Quand
je fais v.begin() (ou v est un std::vector), moi, le programmeur, sait
que cet itérateur correspond au couple ([0 ; v.size()[, 0). Pour
l'itérateur, en revanche, tout ce qu'il sait (formellement), c'est :
[-oo ; +oo], 0.

À noter que si tu as une chaîne de caractères de type C, tu connais
la taille, c'est que ce que te donne strlen().

Et comment est-ce que j'implémente strlen() ? En termes des suites et
des itérateurs ? strlen(), c'est bien le résultat de std::count_if, non
(avec un prédicate « true ») ?

Je cerche, conceptuellement, à me tenir au concept d'itérateur. Une fois
que j'ai fait strlen(), et que j'ai son résultat, j'ai effectivement une
suite sur un domaine borné, et ça entre dans la moule. Mais est-ce que
tu ne trouves pas que ça serait intéressant que l'implémentation de
strlen() utilise le concept d'itérateur. Dans la pratique, évidemment,
il peut l'utiliser, parce que la mémoire est finie. Donc, std::count(
start, quelqueChoseDeSuffisammentAudelaDuStart, '') fait l'affaire.
C'est peut-être juste une question de goût, mais je trouve que ça manque
d'élégance.

| Formellement, j'ai l'impression d'une circularité dans la
| définition,

Quelle définition ?

Les définitions dans la norme. C'est peut-être simplement un effet d'une
manque de définitions, mais j'ai l'impression qu'une suite, c'est en fin
de compte quelque chose qui est définie par les itérateurs, et que la
définition d'un itérateur, c'est quelque chose dont un paire définit une
suite.

| dès qu'on veut définir l'itérateur sans y introduire la notion d'une
| collection réele figée. La séquence est définie par les itérateurs,
| et la définition d'un itérateur fait référence à la séquence.

Dans la définition que j'ai donnée, je n'ai pas défini une suite en
termes d'itérateurs. Il n'y a pas de circularité.

Non. Je pensais déjà à la norme. J'ai sauté quelque démarches par
rapport à ce que tu disais.

| Je crois que ton début est bien : on a une application [0 ; n[ -> T.
| Même si n n'est pas forcement connu d'avance. Le problème, c'est que

Non, il ne faut pas insister que le domaine soit [0, n[. Il suffit
qu'il soit un sous-ensemble de ZZ ;

(Juste une petite question : je ne suis pas mathématicien. Alors, en
quoi est-ce que ZZ est différent de Z ?)

en particulier, il n'y a pas besoin que la suite soit bornée avant de
parler d'itérateur. Tu n'as besoin de cette hypothèse que lorsque tu
veux parler de one-past-the-end.

Entendu. C'est donc une limitation des itérateurs STL:-).

| les itérateurs ne dépendent pas d'une collection, où n'en dépendent
| qu'indirectement.

Les itérateurs itèrent sur quelque chose, qui est une suite.

Et la définition de suite est déjà donnée. D'accord.

Pour l'instant, je crois, on parle des « itérateurs » au sens le plus
général, et pas que des itérateurs STL. C'est peut-être là où je t'ai
mal compris -- je pensais tout de suite à la STL uniquement.

| Donc, si j'ai un std::vector< int > qui contient des entiers
| aléatoire, je peux bien vouloir en définir un paire d'itérateurs qui
| itère que sur les valeurs impaires. Une définition d'itérateur doit
| prendre ceci en compte.

Parfaitement, c'est pour cela que tu as besoin

(1) soit de pouvoir parler de sous-suites ;
(2) soit de décider librement de la position i dans (s, i).

Soit...soit, ou et...et ?

Ou c'est peut-être deux façons de dire la même chose ? Si mon vecteur
est la suite V, et les valeurs impaires la suite V', le couple (V,i),
associé à des règles de positionnement de i, définit une bijection sur
(V',i'), qui est une itérateur dans V'.

Les deux conditions ci-dessus ne sont qu'une expression de la même
idée : pouvoir construire de nouvelles suites à partir d'anciennes.

| Pour l'histoire, en Java, un itérateur est toujours défini par
| rapport à une collection (éventuellement virtuelle) -- la définition
| de l'itérateur sur les valeurs paires ci-dessus commence par la
| définition d'une collection qui est une vue sur la collection
| originale.

Donc, si tu as ce brackground de Java, tu n'as pas pu être perdu
par la définition que j'ai donnée ;-)

Non plus. Le seul problème, c'est précisement que j'ai essayé à la
limiter tout de suite à des itérateurs STL, sans voir plus loin que le
bout de mon nez.

| (Typiquement, en révanche, l'implémentation se fait à l'envers -- on
| définit la collection en fonction de l'itérateur.)

Tout le monde sait bien qu'une implémentation n'est qu'une
traduction d'une abstraction et qu'en générale une bonne traduction
n'est pas celle qui traduit mot à mot :-)

Tout à fait. De même que le choix itérateur simple/itérateur double est
en fait un choix de la traduction -- que dans ta définition, l'itérateur
abstrait contient l'information sur sa fin n'est pas un argument pour ou
contre l'une des traductions. (Il y en a d'autres, mais ça c'est une
autre histoire.)

--
James Kanze GABI Software mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16

Vous avez filtré cet utilisateur ! Consultez son message

Gabriel Dos Reis wrote in message
news:...

writes:

| Gabriel Dos Reis wrote in message
| news:...
| > writes:

| > | La norme parle des « past-the-end values ». Comment doit-on
| > | rendre cette expression en français ? La norme C parle des
| > | pointeurs « one past the last object » ; on pourrait poser la
| > | même question ici.

| > À mon grand regret (et aussi celui de BS), nombre de formulations
| > actuellemment présentes dans la norme sont des long listes de cas
| > particuliers. Dans la composante IPR de la charpente de
| > représentation de programmes C++ en C++ (The Pivot) que nous
| > développons ici,

| C'est quoi, la composante IPR ? (« independant program
| representation » ? Mais même alors, je ne suis pas bien avancé.)

IPR == Internal Program Representation
XPR == External Program Representation

Il y a deux ans ou trois, BS avait fait une présentation au comité
d'une bibliothèque appelée XTI. XTI a évolué depuis Novembre dernier
en « The Pivot ». Si tu as encore accès aux documents du comité, tu
devrais avoir les slides. Si tu es abonné à l'ACCU, tu devrais aussi
avoir accès aux slides de sa présentation à l'ACCU Spring Conference
2002.

Je n'ai pas actuellement accès. Ou au moins, qu'intermittamment. Mais
j'essaierai à trouver le document.

| Et c'est quoi, « The Pivot » ?

Un outil qu'on développe pour faire des choses avec des programmes que
les autres n'arrivent pas à faire ;-) (Sérieusement, voir ci-dessus
pour une description schématique)

| > nous utilisons naturellement la notion de suite au sens abstrait
| > du terme (et certainement proche de l'ingénieur en chef, mais
| > aussi matheux, Alex Stepanov). Je ne sais pas si je proposerais
| > une formulation équivalente pour adoption dans la norme, mais
| > voici ce que j'ai mis dans la documentation de IPR (traduction) :

| > 1.1.1 Suite

| > Une /suite/ est une application I --> T où le domaine I est un
| > sous-ensemble des entiers relatifs ZZ. Les suites considérées
| > dans IPR ont des domaines bornés. En conséquence, lorsque nous
| > parlons de suite, il est implicitement entendu que son domaine
| > est borné. Le cardinal du domaine d'une suite est appelée sa
| > /taille/ (notée /size/). Une suite Sigma : I --> T de taille
| > /n/ admet la décomposition canonique nu : I --> [0, n[ suivie
| > de [0, n[ --> T, où l'application nu (une indexation du domaine
| > I) est une application strictement croissante.

| Je ne vois pas a priori l'intérêt de passer par l'application I -->
| T. J'aurais probablement commencé directement par le [0 ; n[
| (élément de Z) --> T. Mais bon, je ne suis pas mathieux ; il y a
| probablement quelque chose qui m'a passé de côté.

Si tu commences directement par [0, n[ --> T, tu limites de manière
gratuite ce qui peut être considérée comme suite; et il va te devoir
faire des acrobaties -- à mon avis complètement gratuites -- lorsque
tu veux parler de sous-suites ou de suites adaptées.

En somme, donné la suite [0 ; n[, la sous-suite [5 ; n-5[ est aussi une
suite. Je comprends.

Voici une analogie, si tu as l'esprit un peu géomètre. [...]

Je ne l'ai pas, mais ça fait rien. Le mot sous-suite a fait le déclic.

| Une suite, en fait, c'est que ce qu'on appelle une séquence dans la
| norme, si j'ai bien compris.

Je crois que « sequence » se traduit aussi par « suite » en français
-- du moins, c'est ce que m'apprend mon éducation mathématique ;-)

C'est possible. Je connais la notion mathématique de suite en français.
Assez vaguement, parce que les seules maths que j'ai fait, c'est un
cours de Math générale A à la CNAM. Je ne sais pas comment on l'appelera
en anglais. Je connais la notion d'une séquence (sequence, en anglais)
dans la norme C++ -- là, c'est en anglais, évidemment. Curieusement, ça
ne m'était pas venu à l'ésprit à les rapprocher. Probablement parce que
mes maths sont tellement anciennes, et qu'elles ne se rapprochent en
rien, ou au moins, ne s'en rapprochaient en rien dans la passée, à ce
que je fais en informatique. Si je reconnais l'importance de la façon de
penser qui y était enseigné, jusqu'ici, il y a eu fort peu de
connaissances concrète qui m'ont servies.

| > 1.1.2 Itérateur

| > Un itérateur est un couple de suite et d'entier appelé
| > /position/. Un itérateur (s, i) est /valide pour indirection/
| > si sa position est dans les bornes de l'indexation du domaine
| > de s, i.e. si i est positif et strictement plus petit que la
| > taille de s. Les itérateurs particuliers (s, 0) et (s, size(s))
| > sont respectivement appelés les itérateurs /first/ et
| > /one-past-the-end/ de s.

| J'ai un problème tout de suite, mais vu que tu en parles par la suite...

Mais « sequence » en anglais se traduit par « suite » en français, tu
ne peux pas être perdu :-)

D'accord : I have a problem all of a sequence... (En allemand, il y a
une forme d'humeur qui consiste entièrement en ce genre de
translitérations. Je n'ai jamais vu l'équivalent en français. Peut-être
parce qu'il ne marche, évidemment, que si on a une bonne connaissance
des deux langues.)

| > Exprès, je n'ai pas traduit /first/ et /one-past-the-end/. Mais,
| > cela te donne au moins une idée de ce que /one-past-the-end/
| > représente de manière abstraite. À noter que cette formulation de
| > one-past-the-end s'applique même si la suite est de taille nulle.

| En effet. En fait, j'ai démandé la traduction, mais je suis bien
| d'accord qu'il faut commencer par bien définir la chose dans la
| langue d'origine.

| > Je prétends que pour tous les containers (au moins ceux de la
| > bibliothèque standard), cette définition s'applique et, de plus,
| > est générale.

| Pas de problème avec les itérateurs issus des collections standard.
| Si j'ai bien compris l'intérêt de la STL, en revanche, ce n'en sont
| qu'une petite partie.

Tout à fait, mais la définition que je donne s'applique aussi à
n'importe quel itérateur issu de n'importe quelle suite -- c'était le
but de l'exercice de définir d'abord une suite :-). Un itérateur ne
vient pas comme ça, pouf, de nulle part. En particulier, tu ne peux
pas parler de one-past-the-end si tu n'as pas déjà la notion de suite
(bornée).

Le problème que je vois, a priori, c'est que ta suite est par définition
bornée. Or que dans la pratique, il est fort utile d'avoir des
itérateurs dont on ne reconnaît la fin que quand on y arrive. Et qui
sont potentiellement infinis en théorie, à condition que dans la
pratique...

| > Je crois que seuls les std::istream_iterator<>
| > std::ostream_iterator<> résistent à cette définition, mais alors
| > il est aussi vrai qu'ils ne sont attachés à aucune suite au sens
| > propre du terme (comme défini au 1.1.1).

| C'est le problème que j'ai toujours eu avec les itérateurs standard
| (mais sur un plan plus pragmatique). Les itérateurs de flux n'en
| sont qu'un exemple -- comment définir un itérateur standard quand la
| taille (ou la fin) n'est pas connue d'avance. Même une chaîne de
| caractères de type C pose le problème -- qu'on résoud dans ce cas-là
| en cherchant la fin avec des moyens autre que les itérateurs STL.

Là, je ne te suis pas. Si tu as la notion de suite, alors la notion
d'itérateur vient tout seul : c'est l'association d'une suite avec un
entier (position d'un élément dans la suite). Tu n'as pas besoin que
la taille soit connue d'avance. La notion de taille ne devient
critique que lorsque tu veux définir la notion de «
one-past-the-end ». Il me semble aller de bon sens de parler d'un
élément au delà de la fin seulement si on peut parler de fin, non ?

En effet. C'est un des problèmes que j'ai avec les itérateurs STL. Comme
tu dis ci-dessus : « Les suites considérées dans IPR ont des domaines
bornés. » Or, dans la pratique, j'ai assez souvent besoin des suites qui
ne sont pas bornées, ou dont la borne supérieur n'est pas connue
d'avance. std::istream_iterator en serait un exemple type. En fait, il
se trouve que dans mes programmes, je me sers plus souvent de l'autre
«@itérateur » de la norme : std::basic_streambuf. qui m'apporte souvent
un surcharge (gestion de buffer, d'erreur, etc.) dont je n'ai pas
besoin. Et qui a un coût en temps d'exécution non negligible -- la
résolution dynamique fait qu'ils sont plus souples à l'utilisation qu'un
itérateur STL, mais c'est un avantage qui se paie, comme tu le sais.

Mais on entre alors dans la discussion itérateur simple -- itérateur
double. Qui est en quelque sort indépendant du concept abstrait ; on
peut bien implémenter les itérateurs tels que tu les as définis
ci-dessus des deux façons. Je dirais même que dans la mésure que
l'itérateur a une suite comme premier élément du couple, et que la suite
(telle que tu l'as définie) connaît sa fin, on s'attendrait
intuitivement que l'itérateur connaît aussi sa fin, et qu'on n'en a
besoin donc que d'un. C'est peut-être ce qui me gène dans cette
définition, d'ailleurs -- au niveau de l'implémentation, des itérateurs
STL ne connaissent pas la suite. Ils désigne un objet, et ils ont un
moyen pour naviguer à partir de cet objet, pour arriver à un autre
objet. Mais tant que je n'ai qu'un seul itérateur STL, c'est une suite
sans bornes (conceptuellement, au moins). Un itérateur, ne connaissant
les limites, ne connaît toujours que la suite infinie [-oo ; +oo]. Quand
je fais v.begin() (ou v est un std::vector), moi, le programmeur, sait
que cet itérateur correspond au couple ([0 ; v.size()[, 0). Pour
l'itérateur, en revanche, tout ce qu'il sait (formellement), c'est :
[-oo ; +oo], 0.

À noter que si tu as une chaîne de caractères de type C, tu connais
la taille, c'est que ce que te donne strlen().

Et comment est-ce que j'implémente strlen() ? En termes des suites et
des itérateurs ? strlen(), c'est bien le résultat de std::count_if, non
(avec un prédicate « true ») ?

Je cerche, conceptuellement, à me tenir au concept d'itérateur. Une fois
que j'ai fait strlen(), et que j'ai son résultat, j'ai effectivement une
suite sur un domaine borné, et ça entre dans la moule. Mais est-ce que
tu ne trouves pas que ça serait intéressant que l'implémentation de
strlen() utilise le concept d'itérateur. Dans la pratique, évidemment,
il peut l'utiliser, parce que la mémoire est finie. Donc, std::count(
start, quelqueChoseDeSuffisammentAudelaDuStart, '') fait l'affaire.
C'est peut-être juste une question de goût, mais je trouve que ça manque
d'élégance.

| Formellement, j'ai l'impression d'une circularité dans la
| définition,

Quelle définition ?

Les définitions dans la norme. C'est peut-être simplement un effet d'une
manque de définitions, mais j'ai l'impression qu'une suite, c'est en fin
de compte quelque chose qui est définie par les itérateurs, et que la
définition d'un itérateur, c'est quelque chose dont un paire définit une
suite.

| dès qu'on veut définir l'itérateur sans y introduire la notion d'une
| collection réele figée. La séquence est définie par les itérateurs,
| et la définition d'un itérateur fait référence à la séquence.

Dans la définition que j'ai donnée, je n'ai pas défini une suite en
termes d'itérateurs. Il n'y a pas de circularité.

Non. Je pensais déjà à la norme. J'ai sauté quelque démarches par
rapport à ce que tu disais.

| Je crois que ton début est bien : on a une application [0 ; n[ -> T.
| Même si n n'est pas forcement connu d'avance. Le problème, c'est que

Non, il ne faut pas insister que le domaine soit [0, n[. Il suffit
qu'il soit un sous-ensemble de ZZ ;

(Juste une petite question : je ne suis pas mathématicien. Alors, en
quoi est-ce que ZZ est différent de Z ?)

en particulier, il n'y a pas besoin que la suite soit bornée avant de
parler d'itérateur. Tu n'as besoin de cette hypothèse que lorsque tu
veux parler de one-past-the-end.

Entendu. C'est donc une limitation des itérateurs STL:-).

| les itérateurs ne dépendent pas d'une collection, où n'en dépendent
| qu'indirectement.

Les itérateurs itèrent sur quelque chose, qui est une suite.

Et la définition de suite est déjà donnée. D'accord.

Pour l'instant, je crois, on parle des « itérateurs » au sens le plus
général, et pas que des itérateurs STL. C'est peut-être là où je t'ai
mal compris -- je pensais tout de suite à la STL uniquement.

| Donc, si j'ai un std::vector< int > qui contient des entiers
| aléatoire, je peux bien vouloir en définir un paire d'itérateurs qui
| itère que sur les valeurs impaires. Une définition d'itérateur doit
| prendre ceci en compte.

Parfaitement, c'est pour cela que tu as besoin

(1) soit de pouvoir parler de sous-suites ;
(2) soit de décider librement de la position i dans (s, i).

Soit...soit, ou et...et ?

Ou c'est peut-être deux façons de dire la même chose ? Si mon vecteur
est la suite V, et les valeurs impaires la suite V', le couple (V,i),
associé à des règles de positionnement de i, définit une bijection sur
(V',i'), qui est une itérateur dans V'.

Les deux conditions ci-dessus ne sont qu'une expression de la même
idée : pouvoir construire de nouvelles suites à partir d'anciennes.

| Pour l'histoire, en Java, un itérateur est toujours défini par
| rapport à une collection (éventuellement virtuelle) -- la définition
| de l'itérateur sur les valeurs paires ci-dessus commence par la
| définition d'une collection qui est une vue sur la collection
| originale.

Donc, si tu as ce brackground de Java, tu n'as pas pu être perdu
par la définition que j'ai donnée ;-)

Non plus. Le seul problème, c'est précisement que j'ai essayé à la
limiter tout de suite à des itérateurs STL, sans voir plus loin que le
bout de mon nez.

| (Typiquement, en révanche, l'implémentation se fait à l'envers -- on
| définit la collection en fonction de l'itérateur.)

Tout le monde sait bien qu'une implémentation n'est qu'une
traduction d'une abstraction et qu'en générale une bonne traduction
n'est pas celle qui traduit mot à mot :-)

Tout à fait. De même que le choix itérateur simple/itérateur double est
en fait un choix de la traduction -- que dans ta définition, l'itérateur
abstrait contient l'information sur sa fin n'est pas un argument pour ou
contre l'une des traductions. (Il y en a d'autres, mais ça c'est une
autre histoire.)

--
James Kanze GABI Software mailto:
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16

tib.motuelle

27/02/2004 à 08:13

wrote in message news:...

Gabriel Dos Reis wrote in message
news:...
writes:

| Gabriel Dos Reis wrote in message
| news:...
| > writes:

| > | La norme parle des « past-the-end values ». Comment doit-on
| > | rendre cette expression en français ? La norme C parle des
| > | pointeurs « one past the last object » ; on pourrait poser la
| > | même question ici.

| > À mon grand regret (et aussi celui de BS), nombre de formulations
| > actuellemment présentes dans la norme sont des long listes de cas
| > particuliers. Dans la composante IPR de la charpente de
| > représentation de programmes C++ en C++ (The Pivot) que nous
| > développons ici,

| C'est quoi, la composante IPR ? (« independant program
| representation » ? Mais même alors, je ne suis pas bien avancé.)

IPR == Internal Program Representation
XPR == External Program Representation

Il y a deux ans ou trois, BS avait fait une présentation au comité
d'une bibliothèque appelée XTI. XTI a évolué depuis Novembre dernier
en « The Pivot ». Si tu as encore accès aux documents du comité, tu
devrais avoir les slides. Si tu es abonné à l'ACCU, tu devrais aussi
avoir accès aux slides de sa présentation à l'ACCU Spring Conference
2002.

Je n'ai pas actuellement accès. Ou au moins, qu'intermittamment. Mais
j'essaierai à trouver le document.

Je pense que Gaby parle de cette présentation (ca s'appelle encore
XTI, je ne sais pas trop de quand elle date, mais elle présente les
grandes lignes):
http://www.klid.dk/arrangementer/XTI_kbh.pdf

Bertrand.

Gabriel Dos Reis

07/03/2004 à 17:45

[ J'ai eu entretemps l'occasion de discuster avec d'autres personnes
de la notion d'itérateur telle que je l'ai indiquée ici et il m'a
été signalé que Alex Stepanov en avait la même compréhension. Ce qui
est rigolo, c'est que c'est j'avais monté un groupe de travail sur
la programmation générique et la semaine où j'avais posté mon
message, j'avais donné aux étudiants un article à lire
(que j'avais seulement parcouru en diagonal, honte sur moi).

http://citeseer.nj.nec.com/musser88generic.html

La notion d'itérateur y est décrite sous le vocable de
« Coordinate ». La notion de suite délimitée par un intervalle
semi-ouvert à droite y est implicite, quoi que non distincte -- voir
les explications dans la description de Partition. ]

writes:

| > | > Exprès, je n'ai pas traduit /first/ et /one-past-the-end/. Mais,
| > | > cela te donne au moins une idée de ce que /one-past-the-end/
| > | > représente de manière abstraite. À noter que cette formulation de
| > | > one-past-the-end s'applique même si la suite est de taille nulle.
|
| > | En effet. En fait, j'ai démandé la traduction, mais je suis bien
| > | d'accord qu'il faut commencer par bien définir la chose dans la
| > | langue d'origine.
|
| > | > Je prétends que pour tous les containers (au moins ceux de la
| > | > bibliothèque standard), cette définition s'applique et, de plus,
| > | > est générale.
|
| > | Pas de problème avec les itérateurs issus des collections standard.
| > | Si j'ai bien compris l'intérêt de la STL, en revanche, ce n'en sont
| > | qu'une petite partie.
|
| > Tout à fait, mais la définition que je donne s'applique aussi à
| > n'importe quel itérateur issu de n'importe quelle suite -- c'était le
| > but de l'exercice de définir d'abord une suite :-). Un itérateur ne
| > vient pas comme ça, pouf, de nulle part. En particulier, tu ne peux
| > pas parler de one-past-the-end si tu n'as pas déjà la notion de suite
| > (bornée).
|
| Le problème que je vois, a priori, c'est que ta suite est par définition
| bornée.

La suite est uniquement bornée dans IPR -- parce que les suites
concrètes dans IPR sont bornées pour des raisons bassement matérielles :
un programme C++ est un machin fini, aussi volumineux qu'il soit :-)

| Or que dans la pratique, il est fort utile d'avoir des
| itérateurs dont on ne reconnaît la fin que quand on y arrive. Et qui

Oui, mais c'est quand même une suite finie, non ? :-)
[ Je crois qu'ici la différence de perception est probablement dûe à
nos cultures différentes -- pour moi c'est un infini potentiel donc
concrètement, c'est un machin fini. Voir le lien sur les infinis
que je donne plus bas. ]

Tu testes si tu es à la fin par un prédicat -- dans le modèle que
j'exposais, cela serait une comparaison avec un itérateur de référence
designé comme la fin. Conceptuellement et -pratiquement- il n'y a
aucun problème.

| sont potentiellement infinis en théorie, à condition que dans la
| pratique...

Pour moi, « potentiellement infini != infini » :-)

Il y a plusieurs choses qu'il faut bien distinguer : la notion
abstraite de suite, et ce qu'on considère comme suite par pure
accomodation. Par exemple, std::cin n'est pas vraiment une suite de
int au bon sens du terme. Et ce sont ces cas qui posent « problèmes. »
Elles ne sont pas applicatives, au sens que si tu déréferencent deux
fois de suite, tu n'as pas de garantie d'avoir la même valeur (cas
limites). Pire, si tu utilises un « vrai » InputIterator pour
parcourir une « suite », et que tu arrives à la fin, tu ne peux pas
reproduire la même chose. En particulier, calculer la taille d'une «
suite » avec un « vrai InputIterator » est une opération
destructrice. Tu n'as pas ces pathologies avec les itérateurs
bi-directionnels.

[...]

| En effet. C'est un des problèmes que j'ai avec les itérateurs STL. Comme
| tu dis ci-dessus : « Les suites considérées dans IPR ont des domaines
| bornés. » Or, dans la pratique, j'ai assez souvent besoin des suites qui
| ne sont pas bornées, ou dont la borne supérieur n'est pas connue
| d'avance. std::istream_iterator en serait un exemple type. En fait, il

Hmm, je crois plutôt que dans la pratique, tu as des suites bornées et
que tu ne le sais pas à l'avance ou que tu ne le décrouves que quand
tu arrives à la fin.

Mais, il n'y a pas vraiment de difficulté théorique. Requerir une
suite borné est un moyen simple de parler « d'itérateur avant » et
« d'itérateur après » que le commun des mortels peut comprendre sans
crier tout de suite à une abstraction excessive. Cependant, la théorie
marche tout aussi bien avec des ordinaux infinis (il faut faire un peu
attention mais ça marche). Pour un survol « gentil » des ordinaux infinis,
voir

http://www.eleves.ens.fr:8080/home/madore/math/infinity.pdf

| se trouve que dans mes programmes, je me sers plus souvent de l'autre
| «@itérateur » de la norme : std::basic_streambuf. qui m'apporte souvent
| un surcharge (gestion de buffer, d'erreur, etc.) dont je n'ai pas
| besoin. Et qui a un coût en temps d'exécution non negligible -- la
| résolution dynamique fait qu'ils sont plus souples à l'utilisation qu'un
| itérateur STL, mais c'est un avantage qui se paie, comme tu le sais.
|
| Mais on entre alors dans la discussion itérateur simple -- itérateur
| double.

Hmm, je ne comprends pas bien ce que tu appelles « itérateur double ».
Peux-tu développer ?

| Qui est en quelque sort indépendant du concept abstrait ; on
| peut bien implémenter les itérateurs tels que tu les as définis
| ci-dessus des deux façons. Je dirais même que dans la mésure que
| l'itérateur a une suite comme premier élément du couple, et que la suite
| (telle que tu l'as définie) connaît sa fin, on s'attendrait
| intuitivement que l'itérateur connaît aussi sa fin, et qu'on n'en a
| besoin donc que d'un.

Ce qui est marrant, c'est que la plupart du temps les itérateurs ne
sont pas implémentés comme cela (probablement pour des raisons de
performance), alors que l'itérateur qui pose problème
(istream_iterator<>) est implémenté comme cela. Ne me dis pas que
c'est le monde à l'envers :-)

| C'est peut-être ce qui me gène dans cette
| définition, d'ailleurs -- au niveau de l'implémentation, des itérateurs
| STL ne connaissent pas la suite.

Comme j'ai mentionné ci-dessus, dans la plupart des implémentations,
istream_iterator<> connait le flux dont il provient (le cas
exceptionnel est l'itérateur de fin). Également, j'ai vu plusieurs
implémentations « debug » de la STL où les itérateurs connaissent les
suites dont ils proviennent.

| Ils désigne un objet, et ils ont un
| moyen pour naviguer à partir de cet objet, pour arriver à un autre
| objet. Mais tant que je n'ai qu'un seul itérateur STL, c'est une suite
| sans bornes (conceptuellement, au moins).

Même conceptuellement, je dirais non. Il faut aussi savoir s'il est
« valide pour indirection ». Considère un output_iterator<> dont le
flux attaché est dans un état où on ne peut plus faire de sortie
(disque démenbré, par exemple).

| Un itérateur, ne connaissant
| les limites, ne connaît toujours que la suite infinie [-oo ; +oo]. Quand
| je fais v.begin() (ou v est un std::vector), moi, le programmeur, sait
| que cet itérateur correspond au couple ([0 ; v.size()[, 0). Pour
| l'itérateur, en revanche, tout ce qu'il sait (formellement), c'est :
| [-oo ; +oo], 0.

Oui, et il sait aussi s'il est valid pour indirection ou non.

| > À noter que si tu as une chaîne de caractères de type C, tu connais
| > la taille, c'est que ce que te donne strlen().
|
| Et comment est-ce que j'implémente strlen() ?

strlen() *fait partie de l'interface* de chaînes de caractères de type C.

| En termes des suites et des itérateurs ?

Je dirais « non », à moins bien sûr que tu veux répéter l'abstraction
istream_iterator<>.

| strlen(), c'est bien le résultat de std::count_if, non
| (avec un prédicate « true ») ?

Je dirais qu'ils concident, mais qu'en premier lieu strlen() est
« donnée » comme faisant partie de l'interface.

Encore une fois, un itérateur ne provient pas d'une fissure spontannée
dans l'espace temps : il provient d'une abstraction sous jacente qui est
une suite et un « position » (lorsque cette position est valide,
l'itérateur désigne un élément dans la suite).

| Je cerche, conceptuellement, à me tenir au concept d'itérateur. Une fois
| que j'ai fait strlen(), et que j'ai son résultat, j'ai effectivement une
| suite sur un domaine borné, et ça entre dans la moule. Mais est-ce que
| tu ne trouves pas que ça serait intéressant que l'implémentation de
| strlen() utilise le concept d'itérateur.

Je crois que ce serait tourner la notion d'itérateur tête-dessous
pieds-en-l'air ou prendre l'arbre pour la forêt.

À partir d'une suite on peut construire un itérateur (qui peut être
valide pour indirection ou non). Mais l'idée fondamentale est qu'un
itérateur est un moyen de parcours d'une suite. Maintenant, il est
tout à fait légitime de s'intéresser à la notion d'itérateur en tant
qu'abstraction en elle-même, mais une théorie d'itérateurs ne peut
pas ignorer le fait que le fondament est une suite.

Si tu as un itérateur, en général tu ne peux pas en faire grand
chose avec. Il faut d'abord savoir s'il est valide pour indirection.
Savoir s'il est valide pour indirection implique que l'itérateur est
dans les « bornes » de quelque chose et ce quelque chose est une suite
(ou quelque chose qui s'en approche).

| Dans la pratique, évidemment,
| il peut l'utiliser, parce que la mémoire est finie. Donc, std::count(
| start, quelqueChoseDeSuffisammentAudelaDuStart, '') fait l'affaire.
| C'est peut-être juste une question de goût, mais je trouve que ça manque
| d'élégance.

Je ne peux qu'être d'accord. Mais alors, à mon sens, cela est le
résultat d'un théorie qui oublie les fondements :-)

[...]

| > | Je crois que ton début est bien : on a une application [0 ; n[ -> T.
| > | Même si n n'est pas forcement connu d'avance. Le problème, c'est que
|
| > Non, il ne faut pas insister que le domaine soit [0, n[. Il suffit
| > qu'il soit un sous-ensemble de ZZ ;
|
| (Juste une petite question : je ne suis pas mathématicien. Alors, en
| quoi est-ce que ZZ est différent de Z ?)

Il n'y a pas de différence tant qu'on précise le contexte :-)
J'écris ZZ par pur déformation professionnelle :-)

[...]

| Pour l'instant, je crois, on parle des « itérateurs » au sens le plus
| général, et pas que des itérateurs STL.

Cela est tout à fait vrai.

| > | Donc, si j'ai un std::vector< int > qui contient des entiers
| > | aléatoire, je peux bien vouloir en définir un paire d'itérateurs qui
| > | itère que sur les valeurs impaires. Une définition d'itérateur doit
| > | prendre ceci en compte.
|
| > Parfaitement, c'est pour cela que tu as besoin
|
| > (1) soit de pouvoir parler de sous-suites ;
| > (2) soit de décider librement de la position i dans (s, i).
|
| Soit...soit, ou et...et ?
|
| Ou c'est peut-être deux façons de dire la même chose ? Si mon vecteur
| est la suite V, et les valeurs impaires la suite V', le couple (V,i),
| associé à des règles de positionnement de i, définit une bijection sur
| (V',i'), qui est une itérateur dans V'.

Oui, c'est exact.

[...]

| > | (Typiquement, en révanche, l'implémentation se fait à l'envers -- on
| > | définit la collection en fonction de l'itérateur.)
|
| > Tout le monde sait bien qu'une implémentation n'est qu'une
| > traduction d'une abstraction et qu'en générale une bonne traduction
| > n'est pas celle qui traduit mot à mot :-)
|
| Tout à fait. De même que le choix itérateur simple/itérateur double est
| en fait un choix de la traduction -- que dans ta définition, l'itérateur
| abstrait contient l'information sur sa fin n'est pas un argument pour ou
| contre l'une des traductions. (Il y en a d'autres, mais ça c'est une
| autre histoire.)

J'aimerais que tu me décrives un peu ce que tu entends pas itérateur
double. C'est un itérateur qui traverse des structures
bi-dimensionnelles ?

-- Gaby

[ J'ai eu entretemps l'occasion de discuster avec d'autres personnes
de la notion d'itérateur telle que je l'ai indiquée ici et il m'a
été signalé que Alex Stepanov en avait la même compréhension. Ce qui
est rigolo, c'est que c'est j'avais monté un groupe de travail sur
la programmation générique et la semaine où j'avais posté mon
message, j'avais donné aux étudiants un article à lire
(que j'avais seulement parcouru en diagonal, honte sur moi).

http://citeseer.nj.nec.com/musser88generic.html

La notion d'itérateur y est décrite sous le vocable de
« Coordinate ». La notion de suite délimitée par un intervalle
semi-ouvert à droite y est implicite, quoi que non distincte -- voir
les explications dans la description de Partition. ]

kanze@gabi-soft.fr writes:

| > | > Exprès, je n'ai pas traduit /first/ et /one-past-the-end/. Mais,
| > | > cela te donne au moins une idée de ce que /one-past-the-end/
| > | > représente de manière abstraite. À noter que cette formulation de
| > | > one-past-the-end s'applique même si la suite est de taille nulle.
|
| > | En effet. En fait, j'ai démandé la traduction, mais je suis bien
| > | d'accord qu'il faut commencer par bien définir la chose dans la
| > | langue d'origine.
|
| > | > Je prétends que pour tous les containers (au moins ceux de la
| > | > bibliothèque standard), cette définition s'applique et, de plus,
| > | > est générale.
|
| > | Pas de problème avec les itérateurs issus des collections standard.
| > | Si j'ai bien compris l'intérêt de la STL, en revanche, ce n'en sont
| > | qu'une petite partie.
|
| > Tout à fait, mais la définition que je donne s'applique aussi à
| > n'importe quel itérateur issu de n'importe quelle suite -- c'était le
| > but de l'exercice de définir d'abord une suite :-). Un itérateur ne
| > vient pas comme ça, pouf, de nulle part. En particulier, tu ne peux
| > pas parler de one-past-the-end si tu n'as pas déjà la notion de suite
| > (bornée).
|
| Le problème que je vois, a priori, c'est que ta suite est par définition
| bornée.

La suite est uniquement bornée dans IPR -- parce que les suites
concrètes dans IPR sont bornées pour des raisons bassement matérielles :
un programme C++ est un machin fini, aussi volumineux qu'il soit :-)

| Or que dans la pratique, il est fort utile d'avoir des
| itérateurs dont on ne reconnaît la fin que quand on y arrive. Et qui

Oui, mais c'est quand même une suite finie, non ? :-)
[ Je crois qu'ici la différence de perception est probablement dûe à
nos cultures différentes -- pour moi c'est un infini potentiel donc
concrètement, c'est un machin fini. Voir le lien sur les infinis
que je donne plus bas. ]

Tu testes si tu es à la fin par un prédicat -- dans le modèle que
j'exposais, cela serait une comparaison avec un itérateur de référence
designé comme la fin. Conceptuellement et -pratiquement- il n'y a
aucun problème.

| sont potentiellement infinis en théorie, à condition que dans la
| pratique...

Pour moi, « potentiellement infini != infini » :-)

Il y a plusieurs choses qu'il faut bien distinguer : la notion
abstraite de suite, et ce qu'on considère comme suite par pure
accomodation. Par exemple, std::cin n'est pas vraiment une suite de
int au bon sens du terme. Et ce sont ces cas qui posent « problèmes. »
Elles ne sont pas applicatives, au sens que si tu déréferencent deux
fois de suite, tu n'as pas de garantie d'avoir la même valeur (cas
limites). Pire, si tu utilises un « vrai » InputIterator pour
parcourir une « suite », et que tu arrives à la fin, tu ne peux pas
reproduire la même chose. En particulier, calculer la taille d'une «
suite » avec un « vrai InputIterator » est une opération
destructrice. Tu n'as pas ces pathologies avec les itérateurs
bi-directionnels.

[...]

| En effet. C'est un des problèmes que j'ai avec les itérateurs STL. Comme
| tu dis ci-dessus : « Les suites considérées dans IPR ont des domaines
| bornés. » Or, dans la pratique, j'ai assez souvent besoin des suites qui
| ne sont pas bornées, ou dont la borne supérieur n'est pas connue
| d'avance. std::istream_iterator en serait un exemple type. En fait, il

Hmm, je crois plutôt que dans la pratique, tu as des suites bornées et
que tu ne le sais pas à l'avance ou que tu ne le décrouves que quand
tu arrives à la fin.

Mais, il n'y a pas vraiment de difficulté théorique. Requerir une
suite borné est un moyen simple de parler « d'itérateur avant » et
« d'itérateur après » que le commun des mortels peut comprendre sans
crier tout de suite à une abstraction excessive. Cependant, la théorie
marche tout aussi bien avec des ordinaux infinis (il faut faire un peu
attention mais ça marche). Pour un survol « gentil » des ordinaux infinis,
voir

http://www.eleves.ens.fr:8080/home/madore/math/infinity.pdf

| se trouve que dans mes programmes, je me sers plus souvent de l'autre
| «@itérateur » de la norme : std::basic_streambuf. qui m'apporte souvent
| un surcharge (gestion de buffer, d'erreur, etc.) dont je n'ai pas
| besoin. Et qui a un coût en temps d'exécution non negligible -- la
| résolution dynamique fait qu'ils sont plus souples à l'utilisation qu'un
| itérateur STL, mais c'est un avantage qui se paie, comme tu le sais.
|
| Mais on entre alors dans la discussion itérateur simple -- itérateur
| double.

Hmm, je ne comprends pas bien ce que tu appelles « itérateur double ».
Peux-tu développer ?

| Qui est en quelque sort indépendant du concept abstrait ; on
| peut bien implémenter les itérateurs tels que tu les as définis
| ci-dessus des deux façons. Je dirais même que dans la mésure que
| l'itérateur a une suite comme premier élément du couple, et que la suite
| (telle que tu l'as définie) connaît sa fin, on s'attendrait
| intuitivement que l'itérateur connaît aussi sa fin, et qu'on n'en a
| besoin donc que d'un.

Ce qui est marrant, c'est que la plupart du temps les itérateurs ne
sont pas implémentés comme cela (probablement pour des raisons de
performance), alors que l'itérateur qui pose problème
(istream_iterator<>) est implémenté comme cela. Ne me dis pas que
c'est le monde à l'envers :-)

| C'est peut-être ce qui me gène dans cette
| définition, d'ailleurs -- au niveau de l'implémentation, des itérateurs
| STL ne connaissent pas la suite.

Comme j'ai mentionné ci-dessus, dans la plupart des implémentations,
istream_iterator<> connait le flux dont il provient (le cas
exceptionnel est l'itérateur de fin). Également, j'ai vu plusieurs
implémentations « debug » de la STL où les itérateurs connaissent les
suites dont ils proviennent.

| Ils désigne un objet, et ils ont un
| moyen pour naviguer à partir de cet objet, pour arriver à un autre
| objet. Mais tant que je n'ai qu'un seul itérateur STL, c'est une suite
| sans bornes (conceptuellement, au moins).

Même conceptuellement, je dirais non. Il faut aussi savoir s'il est
« valide pour indirection ». Considère un output_iterator<> dont le
flux attaché est dans un état où on ne peut plus faire de sortie
(disque démenbré, par exemple).

| Un itérateur, ne connaissant
| les limites, ne connaît toujours que la suite infinie [-oo ; +oo]. Quand
| je fais v.begin() (ou v est un std::vector), moi, le programmeur, sait
| que cet itérateur correspond au couple ([0 ; v.size()[, 0). Pour
| l'itérateur, en revanche, tout ce qu'il sait (formellement), c'est :
| [-oo ; +oo], 0.

Oui, et il sait aussi s'il est valid pour indirection ou non.

| > À noter que si tu as une chaîne de caractères de type C, tu connais
| > la taille, c'est que ce que te donne strlen().
|
| Et comment est-ce que j'implémente strlen() ?

strlen() *fait partie de l'interface* de chaînes de caractères de type C.

| En termes des suites et des itérateurs ?

Je dirais « non », à moins bien sûr que tu veux répéter l'abstraction
istream_iterator<>.

| strlen(), c'est bien le résultat de std::count_if, non
| (avec un prédicate « true ») ?

Je dirais qu'ils concident, mais qu'en premier lieu strlen() est
« donnée » comme faisant partie de l'interface.

Encore une fois, un itérateur ne provient pas d'une fissure spontannée
dans l'espace temps : il provient d'une abstraction sous jacente qui est
une suite et un « position » (lorsque cette position est valide,
l'itérateur désigne un élément dans la suite).

| Je cerche, conceptuellement, à me tenir au concept d'itérateur. Une fois
| que j'ai fait strlen(), et que j'ai son résultat, j'ai effectivement une
| suite sur un domaine borné, et ça entre dans la moule. Mais est-ce que
| tu ne trouves pas que ça serait intéressant que l'implémentation de
| strlen() utilise le concept d'itérateur.

Je crois que ce serait tourner la notion d'itérateur tête-dessous
pieds-en-l'air ou prendre l'arbre pour la forêt.

À partir d'une suite on peut construire un itérateur (qui peut être
valide pour indirection ou non). Mais l'idée fondamentale est qu'un
itérateur est un moyen de parcours d'une suite. Maintenant, il est
tout à fait légitime de s'intéresser à la notion d'itérateur en tant
qu'abstraction en elle-même, mais une théorie d'itérateurs ne peut
pas ignorer le fait que le fondament est une suite.

Si tu as un itérateur, en général tu ne peux pas en faire grand
chose avec. Il faut d'abord savoir s'il est valide pour indirection.
Savoir s'il est valide pour indirection implique que l'itérateur est
dans les « bornes » de quelque chose et ce quelque chose est une suite
(ou quelque chose qui s'en approche).

| Dans la pratique, évidemment,
| il peut l'utiliser, parce que la mémoire est finie. Donc, std::count(
| start, quelqueChoseDeSuffisammentAudelaDuStart, '') fait l'affaire.
| C'est peut-être juste une question de goût, mais je trouve que ça manque
| d'élégance.

Je ne peux qu'être d'accord. Mais alors, à mon sens, cela est le
résultat d'un théorie qui oublie les fondements :-)

[...]

| > | Je crois que ton début est bien : on a une application [0 ; n[ -> T.
| > | Même si n n'est pas forcement connu d'avance. Le problème, c'est que
|
| > Non, il ne faut pas insister que le domaine soit [0, n[. Il suffit
| > qu'il soit un sous-ensemble de ZZ ;
|
| (Juste une petite question : je ne suis pas mathématicien. Alors, en
| quoi est-ce que ZZ est différent de Z ?)

Il n'y a pas de différence tant qu'on précise le contexte :-)
J'écris ZZ par pur déformation professionnelle :-)

[...]

| Pour l'instant, je crois, on parle des « itérateurs » au sens le plus
| général, et pas que des itérateurs STL.

Cela est tout à fait vrai.

| > | Donc, si j'ai un std::vector< int > qui contient des entiers
| > | aléatoire, je peux bien vouloir en définir un paire d'itérateurs qui
| > | itère que sur les valeurs impaires. Une définition d'itérateur doit
| > | prendre ceci en compte.
|
| > Parfaitement, c'est pour cela que tu as besoin
|
| > (1) soit de pouvoir parler de sous-suites ;
| > (2) soit de décider librement de la position i dans (s, i).
|
| Soit...soit, ou et...et ?
|
| Ou c'est peut-être deux façons de dire la même chose ? Si mon vecteur
| est la suite V, et les valeurs impaires la suite V', le couple (V,i),
| associé à des règles de positionnement de i, définit une bijection sur
| (V',i'), qui est une itérateur dans V'.

Oui, c'est exact.

[...]

| > | (Typiquement, en révanche, l'implémentation se fait à l'envers -- on
| > | définit la collection en fonction de l'itérateur.)
|
| > Tout le monde sait bien qu'une implémentation n'est qu'une
| > traduction d'une abstraction et qu'en générale une bonne traduction
| > n'est pas celle qui traduit mot à mot :-)
|
| Tout à fait. De même que le choix itérateur simple/itérateur double est
| en fait un choix de la traduction -- que dans ta définition, l'itérateur
| abstrait contient l'information sur sa fin n'est pas un argument pour ou
| contre l'une des traductions. (Il y en a d'autres, mais ça c'est une
| autre histoire.)

J'aimerais que tu me décrives un peu ce que tu entends pas itérateur
double. C'est un itérateur qui traverse des structures
bi-dimensionnelles ?

-- Gaby

Vous avez filtré cet utilisateur ! Consultez son message

[ J'ai eu entretemps l'occasion de discuster avec d'autres personnes
de la notion d'itérateur telle que je l'ai indiquée ici et il m'a
été signalé que Alex Stepanov en avait la même compréhension. Ce qui
est rigolo, c'est que c'est j'avais monté un groupe de travail sur
la programmation générique et la semaine où j'avais posté mon
message, j'avais donné aux étudiants un article à lire
(que j'avais seulement parcouru en diagonal, honte sur moi).

http://citeseer.nj.nec.com/musser88generic.html

La notion d'itérateur y est décrite sous le vocable de
« Coordinate ». La notion de suite délimitée par un intervalle
semi-ouvert à droite y est implicite, quoi que non distincte -- voir
les explications dans la description de Partition. ]

writes:

| > | > Exprès, je n'ai pas traduit /first/ et /one-past-the-end/. Mais,
| > | > cela te donne au moins une idée de ce que /one-past-the-end/
| > | > représente de manière abstraite. À noter que cette formulation de
| > | > one-past-the-end s'applique même si la suite est de taille nulle.
|
| > | En effet. En fait, j'ai démandé la traduction, mais je suis bien
| > | d'accord qu'il faut commencer par bien définir la chose dans la
| > | langue d'origine.
|
| > | > Je prétends que pour tous les containers (au moins ceux de la
| > | > bibliothèque standard), cette définition s'applique et, de plus,
| > | > est générale.
|
| > | Pas de problème avec les itérateurs issus des collections standard.
| > | Si j'ai bien compris l'intérêt de la STL, en revanche, ce n'en sont
| > | qu'une petite partie.
|
| > Tout à fait, mais la définition que je donne s'applique aussi à
| > n'importe quel itérateur issu de n'importe quelle suite -- c'était le
| > but de l'exercice de définir d'abord une suite :-). Un itérateur ne
| > vient pas comme ça, pouf, de nulle part. En particulier, tu ne peux
| > pas parler de one-past-the-end si tu n'as pas déjà la notion de suite
| > (bornée).
|
| Le problème que je vois, a priori, c'est que ta suite est par définition
| bornée.

La suite est uniquement bornée dans IPR -- parce que les suites
concrètes dans IPR sont bornées pour des raisons bassement matérielles :
un programme C++ est un machin fini, aussi volumineux qu'il soit :-)

| Or que dans la pratique, il est fort utile d'avoir des
| itérateurs dont on ne reconnaît la fin que quand on y arrive. Et qui

Oui, mais c'est quand même une suite finie, non ? :-)
[ Je crois qu'ici la différence de perception est probablement dûe à
nos cultures différentes -- pour moi c'est un infini potentiel donc
concrètement, c'est un machin fini. Voir le lien sur les infinis
que je donne plus bas. ]

Tu testes si tu es à la fin par un prédicat -- dans le modèle que
j'exposais, cela serait une comparaison avec un itérateur de référence
designé comme la fin. Conceptuellement et -pratiquement- il n'y a
aucun problème.

| sont potentiellement infinis en théorie, à condition que dans la
| pratique...

Pour moi, « potentiellement infini != infini » :-)

Il y a plusieurs choses qu'il faut bien distinguer : la notion
abstraite de suite, et ce qu'on considère comme suite par pure
accomodation. Par exemple, std::cin n'est pas vraiment une suite de
int au bon sens du terme. Et ce sont ces cas qui posent « problèmes. »
Elles ne sont pas applicatives, au sens que si tu déréferencent deux
fois de suite, tu n'as pas de garantie d'avoir la même valeur (cas
limites). Pire, si tu utilises un « vrai » InputIterator pour
parcourir une « suite », et que tu arrives à la fin, tu ne peux pas
reproduire la même chose. En particulier, calculer la taille d'une «
suite » avec un « vrai InputIterator » est une opération
destructrice. Tu n'as pas ces pathologies avec les itérateurs
bi-directionnels.

[...]

| En effet. C'est un des problèmes que j'ai avec les itérateurs STL. Comme
| tu dis ci-dessus : « Les suites considérées dans IPR ont des domaines
| bornés. » Or, dans la pratique, j'ai assez souvent besoin des suites qui
| ne sont pas bornées, ou dont la borne supérieur n'est pas connue
| d'avance. std::istream_iterator en serait un exemple type. En fait, il

Hmm, je crois plutôt que dans la pratique, tu as des suites bornées et
que tu ne le sais pas à l'avance ou que tu ne le décrouves que quand
tu arrives à la fin.

Mais, il n'y a pas vraiment de difficulté théorique. Requerir une
suite borné est un moyen simple de parler « d'itérateur avant » et
« d'itérateur après » que le commun des mortels peut comprendre sans
crier tout de suite à une abstraction excessive. Cependant, la théorie
marche tout aussi bien avec des ordinaux infinis (il faut faire un peu
attention mais ça marche). Pour un survol « gentil » des ordinaux infinis,
voir

http://www.eleves.ens.fr:8080/home/madore/math/infinity.pdf

| se trouve que dans mes programmes, je me sers plus souvent de l'autre
| «@itérateur » de la norme : std::basic_streambuf. qui m'apporte souvent
| un surcharge (gestion de buffer, d'erreur, etc.) dont je n'ai pas
| besoin. Et qui a un coût en temps d'exécution non negligible -- la
| résolution dynamique fait qu'ils sont plus souples à l'utilisation qu'un
| itérateur STL, mais c'est un avantage qui se paie, comme tu le sais.
|
| Mais on entre alors dans la discussion itérateur simple -- itérateur
| double.

Hmm, je ne comprends pas bien ce que tu appelles « itérateur double ».
Peux-tu développer ?

| Qui est en quelque sort indépendant du concept abstrait ; on
| peut bien implémenter les itérateurs tels que tu les as définis
| ci-dessus des deux façons. Je dirais même que dans la mésure que
| l'itérateur a une suite comme premier élément du couple, et que la suite
| (telle que tu l'as définie) connaît sa fin, on s'attendrait
| intuitivement que l'itérateur connaît aussi sa fin, et qu'on n'en a
| besoin donc que d'un.

Ce qui est marrant, c'est que la plupart du temps les itérateurs ne
sont pas implémentés comme cela (probablement pour des raisons de
performance), alors que l'itérateur qui pose problème
(istream_iterator<>) est implémenté comme cela. Ne me dis pas que
c'est le monde à l'envers :-)

| C'est peut-être ce qui me gène dans cette
| définition, d'ailleurs -- au niveau de l'implémentation, des itérateurs
| STL ne connaissent pas la suite.

Comme j'ai mentionné ci-dessus, dans la plupart des implémentations,
istream_iterator<> connait le flux dont il provient (le cas
exceptionnel est l'itérateur de fin). Également, j'ai vu plusieurs
implémentations « debug » de la STL où les itérateurs connaissent les
suites dont ils proviennent.

| Ils désigne un objet, et ils ont un
| moyen pour naviguer à partir de cet objet, pour arriver à un autre
| objet. Mais tant que je n'ai qu'un seul itérateur STL, c'est une suite
| sans bornes (conceptuellement, au moins).

Même conceptuellement, je dirais non. Il faut aussi savoir s'il est
« valide pour indirection ». Considère un output_iterator<> dont le
flux attaché est dans un état où on ne peut plus faire de sortie
(disque démenbré, par exemple).

| Un itérateur, ne connaissant
| les limites, ne connaît toujours que la suite infinie [-oo ; +oo]. Quand
| je fais v.begin() (ou v est un std::vector), moi, le programmeur, sait
| que cet itérateur correspond au couple ([0 ; v.size()[, 0). Pour
| l'itérateur, en revanche, tout ce qu'il sait (formellement), c'est :
| [-oo ; +oo], 0.

Oui, et il sait aussi s'il est valid pour indirection ou non.

| > À noter que si tu as une chaîne de caractères de type C, tu connais
| > la taille, c'est que ce que te donne strlen().
|
| Et comment est-ce que j'implémente strlen() ?

strlen() *fait partie de l'interface* de chaînes de caractères de type C.

| En termes des suites et des itérateurs ?

Je dirais « non », à moins bien sûr que tu veux répéter l'abstraction
istream_iterator<>.

| strlen(), c'est bien le résultat de std::count_if, non
| (avec un prédicate « true ») ?

Je dirais qu'ils concident, mais qu'en premier lieu strlen() est
« donnée » comme faisant partie de l'interface.

Encore une fois, un itérateur ne provient pas d'une fissure spontannée
dans l'espace temps : il provient d'une abstraction sous jacente qui est
une suite et un « position » (lorsque cette position est valide,
l'itérateur désigne un élément dans la suite).

| Je cerche, conceptuellement, à me tenir au concept d'itérateur. Une fois
| que j'ai fait strlen(), et que j'ai son résultat, j'ai effectivement une
| suite sur un domaine borné, et ça entre dans la moule. Mais est-ce que
| tu ne trouves pas que ça serait intéressant que l'implémentation de
| strlen() utilise le concept d'itérateur.

Je crois que ce serait tourner la notion d'itérateur tête-dessous
pieds-en-l'air ou prendre l'arbre pour la forêt.

À partir d'une suite on peut construire un itérateur (qui peut être
valide pour indirection ou non). Mais l'idée fondamentale est qu'un
itérateur est un moyen de parcours d'une suite. Maintenant, il est
tout à fait légitime de s'intéresser à la notion d'itérateur en tant
qu'abstraction en elle-même, mais une théorie d'itérateurs ne peut
pas ignorer le fait que le fondament est une suite.

Si tu as un itérateur, en général tu ne peux pas en faire grand
chose avec. Il faut d'abord savoir s'il est valide pour indirection.
Savoir s'il est valide pour indirection implique que l'itérateur est
dans les « bornes » de quelque chose et ce quelque chose est une suite
(ou quelque chose qui s'en approche).

| Dans la pratique, évidemment,
| il peut l'utiliser, parce que la mémoire est finie. Donc, std::count(
| start, quelqueChoseDeSuffisammentAudelaDuStart, '') fait l'affaire.
| C'est peut-être juste une question de goût, mais je trouve que ça manque
| d'élégance.

Je ne peux qu'être d'accord. Mais alors, à mon sens, cela est le
résultat d'un théorie qui oublie les fondements :-)

[...]

| > | Je crois que ton début est bien : on a une application [0 ; n[ -> T.
| > | Même si n n'est pas forcement connu d'avance. Le problème, c'est que
|
| > Non, il ne faut pas insister que le domaine soit [0, n[. Il suffit
| > qu'il soit un sous-ensemble de ZZ ;
|
| (Juste une petite question : je ne suis pas mathématicien. Alors, en
| quoi est-ce que ZZ est différent de Z ?)

Il n'y a pas de différence tant qu'on précise le contexte :-)
J'écris ZZ par pur déformation professionnelle :-)

[...]

| Pour l'instant, je crois, on parle des « itérateurs » au sens le plus
| général, et pas que des itérateurs STL.

Cela est tout à fait vrai.

| > | Donc, si j'ai un std::vector< int > qui contient des entiers
| > | aléatoire, je peux bien vouloir en définir un paire d'itérateurs qui
| > | itère que sur les valeurs impaires. Une définition d'itérateur doit
| > | prendre ceci en compte.
|
| > Parfaitement, c'est pour cela que tu as besoin
|
| > (1) soit de pouvoir parler de sous-suites ;
| > (2) soit de décider librement de la position i dans (s, i).
|
| Soit...soit, ou et...et ?
|
| Ou c'est peut-être deux façons de dire la même chose ? Si mon vecteur
| est la suite V, et les valeurs impaires la suite V', le couple (V,i),
| associé à des règles de positionnement de i, définit une bijection sur
| (V',i'), qui est une itérateur dans V'.

Oui, c'est exact.

[...]

| > | (Typiquement, en révanche, l'implémentation se fait à l'envers -- on
| > | définit la collection en fonction de l'itérateur.)
|
| > Tout le monde sait bien qu'une implémentation n'est qu'une
| > traduction d'une abstraction et qu'en générale une bonne traduction
| > n'est pas celle qui traduit mot à mot :-)
|
| Tout à fait. De même que le choix itérateur simple/itérateur double est
| en fait un choix de la traduction -- que dans ta définition, l'itérateur
| abstrait contient l'information sur sa fin n'est pas un argument pour ou
| contre l'une des traductions. (Il y en a d'autres, mais ça c'est une
| autre histoire.)

J'aimerais que tu me décrives un peu ce que tu entends pas itérateur
double. C'est un itérateur qui traverse des structures
bi-dimensionnelles ?

-- Gaby

Richard Delorme

07/03/2004 à 19:23

http://citeseer.nj.nec.com/musser88generic.html

http://citeseer.nj.nec.com/ ne répond plus. Il a, semble-t-il, été
remplacé par http://citeseer.ist.psu.edu

--
Richard

Gabriel Dos Reis

07/03/2004 à 20:22

Richard Delorme writes:

| > http://citeseer.nj.nec.com/musser88generic.html
|
| http://citeseer.nj.nec.com/ ne répond plus. Il a, semble-t-il, été
| remplacé par http://citeseer.ist.psu.edu

C'est très récent alors. As-tu pu accéder au document sur le nouveau
serveur ?

Merci.

-- Gaby

Richard Delorme

07/03/2004 à 20:49

Richard Delorme writes:

| > http://citeseer.nj.nec.com/musser88generic.html
|
| http://citeseer.nj.nec.com/ ne répond plus. Il a, semble-t-il, été
| remplacé par http://citeseer.ist.psu.edu

C'est très récent alors.

Ça doit dater de quelques jours je pense.

As-tu pu accéder au document sur le nouveau serveur ?

http://citeseer.ist.psu.edu/musser88generic.html

existe et mène au bon document.

--
Richard

Gabriel Dos Reis

08/03/2004 à 01:08

find()

7 réponses

Veuillez sélectionner un problème