find()

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.

On remarque bien qu'il s'agit d'une expression technique très précise,
dont la signification ne se résume pas entièrement dans la signification
habituelle des mots qu'elle comporte. Donc, si « valeur au-delà de la
fin » pourrait être un candidat, il est loin d'être certain que c'est la
meilleur solution. D'autant plus qu'en C++, de tels itérateurs peuvent
exister pour un tableau vide, ou il n'y a pas de « last object ».

Je crois (à confirmer) qu'en français on utilise la notion de "sentinelle".

Une sentinelle correspond à une case d'un tableau ou à une cellule d'une
liste chaînée situées juste après le dernier élément. Elle permet
d'améliorer certains algo.

Quelqu'un sait-il si la classe vector utilise ce système ?

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

"Tom" <tom-bombadil@wanadoo.fr> wrote in message
news:<c1d1q7$mnj$1@news-reader1.wanadoo.fr>...

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.

On remarque bien qu'il s'agit d'une expression technique très
précise, dont la signification ne se résume pas entièrement dans la
signification habituelle des mots qu'elle comporte. Donc, si «
valeur au-delà de la fin » pourrait être un candidat, il est loin
d'être certain que c'est la meilleur solution. D'autant plus qu'en
C++, de tels itérateurs peuvent exister pour un tableau vide, ou il
n'y a pas de « last object ».

Je crois (à confirmer) qu'en français on utilise la notion de
"sentinelle".

J'aurais cru que « sentinelle » correspond à l'anglais « sentinal »,
c-à-d un élément ajouté au tableau pour assurer la termination de la
boucle sans avoir à comparer l'indice (ou appliqué aux itérateurs STL,
sans avoir à comparer l'itérateur). Donc, la boucle dans une
implémentation de find pourrait être :

std::vector< T >::iterator current = v.begin () ;
std::vector< T >::iterator end = v.end () ;
while ( current != end && *current != target ) {
++ current ;
}

Il y a deux tests à chaque passage dans la boucle. Le même algorithme
avec sentielle serait :

v.push_back( target ) ;
std::vector< T >::iterator current = v.begin () ;
while ( *current != target ) {
++ target ;
}

Une sentinelle correspond à une case d'un tableau ou à une cellule
d'une liste chaînée situées juste après le dernier élément. Elle
permet d'améliorer certains algo.

Tout à fait. Ce n'est pas le cas de l'itérateur final dans la STL. Il
n'y a pas de case qui lui correspond.

Quelqu'un sait-il si la classe vector utilise ce système ?

Pas du tout.

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

kanze@gabi-soft.fr writes:

| Gabriel Dos Reis <gdr@integrable-solutions.net> wrote in message
| news:<m33c932d16.fsf@uniton.integrable-solutions.net>...
| > James Kanze <kanze@gabi-soft.fr> writes:
|
| > | Nicolas Aunai <nicolas.aunai@free.fr> writes:
|
| > | |> Anthony Fleury a dit :
|
| > | |> > Pour un vecteur d'entiers par exemple : int n, x = 42;
| > | |> > vector<int> a(n); // remplissage de a...
| > | |> > if(find(a.begin(), a.end(), x) == a.end())
| > | |> > // Echec de la recherche...
|
| > | |> > Si 42 n'est pas dans a vecteur, alors find te renvoie a.end().
| > | |> > il n'y a qu'à tester cette valeur pour savoir si find a
| > | |> > échouée ou pas.
|
| > | |> ok, mais l'iterateur a.end(), désigne-t-il l'adresse du dernier
| > | |> élément ? ou la dernière adresse de mon tableau ?
|
| > | Il designe en fait un élément au delà de la fin du tableau.
|
| > Plus précisément, c'est l'iterator (fictif) qui suit immédiatement
| > l'itérateur qui pointe sur a.back() -- si a n'est pas vide.
|
| 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, 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.

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.

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.

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.

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

| On remarque bien qu'il s'agit d'une expression technique très précise,
| dont la signification ne se résume pas entièrement dans la signification
| habituelle des mots qu'elle comporte. Donc, si « valeur au-delà de la
| fin » pourrait être un candidat, il est loin d'être certain que c'est la
| meilleur solution. D'autant plus qu'en C++, de tels itérateurs peuvent
| exister pour un tableau vide, ou il n'y a pas de « last object ».

Est-ce que l'explication ci-dessus te satisfait ?

-- Gaby

"Tom" <tom-bombadil@wanadoo.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.
| >
| > On remarque bien qu'il s'agit d'une expression technique très précise,
| > dont la signification ne se résume pas entièrement dans la signification
| > habituelle des mots qu'elle comporte. Donc, si « valeur au-delà de la
| > fin » pourrait être un candidat, il est loin d'être certain que c'est la
| > meilleur solution. D'autant plus qu'en C++, de tels itérateurs peuvent
| > exister pour un tableau vide, ou il n'y a pas de « last object ».
|
| Je crois (à confirmer) qu'en français on utilise la notion de "sentinelle".

La notion de sentinelle à laquelle je suis habituée (en français)
consiste à traiter *un élément particulier de la suite* comme point
d'arrêt. Or un itérateur est un *moyen de parcours* de la suite et, a
priori, ne fait pas partie de la suite.

| Quelqu'un sait-il si la classe vector utilise ce système ?

Non.

-- Gaby

Franck Branjonneau <fasbjx@free.fr> writes:

| Gabriel Dos Reis <gdr@integrable-solutions.net> écrivait:
|
| > James Kanze <kanze@gabi-soft.fr> writes:
| >
| > | Nicolas Aunai <nicolas.aunai@free.fr> writes:
| > |
| > | |> Anthony Fleury a dit :
| > |
| > | |> > Pour un vecteur d'entiers par exemple : int n, x = 42;
| > | |> > vector<int> a(n); // remplissage de a...
| > | |> > if(find(a.begin(), a.end(), x) == a.end())
| > | |> > // Echec de la recherche...
| > |
| > | |> > Si 42 n'est pas dans a vecteur, alors find te renvoie a.end(). il
| > | |> > n'y a qu'à tester cette valeur pour savoir si find a
| > | |> > échouée ou pas.
| > |
| > | |> ok, mais l'iterateur a.end(), désigne-t-il l'adresse du dernier
| > | |> élément ? ou la dernière adresse de mon tableau ?
| > |
| > | Il designe en fait un élément au delà de la fin du tableau.
| >
| > Plus précisément, c'est l'iterator (fictif) qui suit immédiatement
| > l'itérateur qui pointe sur a.back() -- si a n'est pas vide.
|
| Et si a est vide ?

Alors, c'est l'itérateur de valeur égale à a.begin().

Cette définition est trop proche de l'implémentation pour être
entièrement satisfaisante -- mais le posteur originel était déjà très
(trop ?) proche de l'implémentation :-).

Pour une explication un peu plus satisfaisante, voir mon autre poste
en réponse à James. Mais grosso modo, un itérateur est
conceptuellement une paire (s, i) de suite "s" et de position "i".
L'itérateur (s, 0) est le "s.begin()" et (s, size(s)) est le
"s.end()". En particulier, si s n'est pas vide, s.end() est
l'itérateur qui suite immédiatement (s, size(s) - 1) qui désigne s.back().

(Il se fait juste que dans les implémentations, souvent on ne représente
pas séparément la position et container ; on se sert d'autres
détails d'implémentation. Mais en mode « debug », par exemple, je
pourrais bien imaginer une telle implémentation. Note aussi que cette
description abstraite couvre aussi les adapteurs d'itérateurs)

-- Gaby

Franck Branjonneau <fasbjx@free.fr> writes:

[...]

| Note que a.begin() == a.end() est une propriété de a.end() quand

tout comme la « définition » que j'ai donnée. Tu connais beaucoup de
définitions qui ne sont pas basées ou n'énoncent pas des propriétés ?
:-)

| a est vide. Ce ne sera une définition de a.end() que quand a.begin()
| aura été défini ;-)

Voir mon message en réponse à James :-)

-- Gaby

Gabriel Dos Reis <gdr@cs.tamu.edu> écrivait:

Franck Branjonneau <fasbjx@free.fr> writes:

[...]

| Note que a.begin() == a.end() est une propriété de a.end() quand

tout comme la « définition » que j'ai donnée. Tu connais beaucoup de
définitions qui ne sont pas basées ou n'énoncent pas des propriétés ?
:-)

Au plus une ;-)

| a est vide. Ce ne sera une définition de a.end() que quand a.begin()
| aura été défini ;-)

Voir mon message en réponse à James :-)

D'où je tire :

Si c est un container vide, il n'existe pas de d'itérateur valide pour
indirection et c.end() == c.begin(). Sinon, c.end() est l'unique
itérateur non valide pour indirection ; c'est le successeur du
l'itérateur qui désigne c.back().

Merci.
--
Franck Branjonneau <fasbjx@free.fr>

Franck Branjonneau <fasbjx@free.fr> writes:

| > | a est vide. Ce ne sera une définition de a.end() que quand a.begin()
| > | aura été défini ;-)
| >
| > Voir mon message en réponse à James :-)
|
| D'où je tire :
|
| Si c est un container vide, il n'existe pas de d'itérateur valide pour
| indirection et c.end() == c.begin(). Sinon, c.end() est l'unique
| itérateur non valide pour indirection ; c'est le successeur du
| l'itérateur qui désigne c.back().

Tout est bon sauf "c.end() est l'unique itérateur non valide pour
indirection". D'après la définition que j'ai donnée, il existe plein
d'itérateur invalide pour indirection. Je reformulerais donc la dernière
phrase comme :

Sinon, c.end() est le successeur de l'itérateur qui désigne
c.back() ; il n'est pas valide pour indirection.

À part ça, tu as bien résumé :-)

-- Gaby

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

Et c'est quoi, « The Pivot » ?

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

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

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

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.

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.

Formellement, j'ai l'impression d'une circularité dans la définition,
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.

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
les itérateurs ne dépendent pas d'une collection, où n'en dépendent
qu'indirectement. 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.

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

| On remarque bien qu'il s'agit d'une expression technique très
| précise, dont la signification ne se résume pas entièrement dans la
| signification habituelle des mots qu'elle comporte. Donc, si «
| valeur au-delà de la fin » pourrait être un candidat, il est loin
| d'être certain que c'est la meilleur solution. D'autant plus qu'en
| C++, de tels itérateurs peuvent exister pour un tableau vide, ou il
| n'y a pas de « last object ».

Est-ce que l'explication ci-dessus te satisfait ?

Moyennement. Mais c'est un début -- je suis bien d'accord avec toi que
les définitions dans la norme ne sont pas réelement suffisantes.

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

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.

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

Voici une analogie, si tu as l'esprit un peu géomètre. Supposons que
tu veuilles formaliser la notion de courbe. Bien sûr tu peux dire
qu'une courbe c'est une application [0, L] --> E, où L est la longeur
d'arc -- on appelle cela un paramétrage par la longueur d'arc, et
c'est utile pour définir d'autres choses de manière intrinsèque comme
l'accélération lorque tu parcours la courbe. Mais c'est loin d'être LA
définition d'une courbe. Si tu as une autre bijection [u, v] --> [0, L]
(qui n'est qu'une autre manière de parcourir l'intervalle [0, L]), il
est naturel de voir la composée [u, v] --> [0, L] --> E aussi comme une
courbe, parcourue différemment que l'autre courbe. En fait ce n'est
qu'un reparamétrage de la courbe [0, L] --> E. Prétendre que l'application
[u, v] --> E N'est PAS une courbe demande une sérieux travail de
justification -- qui, à mon sens, tu arriveras difficilement à
produire de manière satisfaisante :-)

Ici, le paramétrage [0, n[ --> T correspond au paramétrage par la
longueur d'arc d'une courbe (n == taille de la suite ~~ L == longueur
de la courbe). J'ai défini la taille d'une suite de manière intrinsèque
(comme le cardinal de son domaine, quelque chose qui ne change pas
si tu fais un parcous de la suite dans un ordre différent, mais de
manière bijective), c'est analogue à comment on définit la longeur
d'une courbe de manière intrinsèque.

| 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 ;-)

| > 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 :-)

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

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

À 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().

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

Quelle définition ?

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

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

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

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

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 ;-)

| (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 :-)

-- Gaby