Marc Boyer writes:
| Ils font une liste circulaire ?
En quelque sorte. Mais un noeud dans cette liste «
circulaire » sert à marquer end(), donc de l'extérieur ce
n'est pas une liste circulaire.
Mais on peut expliquer pourquoi le code ci-dessus va boucler
indéfiniment (à condition que l.size() > 0) sans regarder
une implémentation particulière.
A condition de comprendre que end() est modifié par le
push_back(), c'est à dire que end() dépend du contenu de la
liste.
Et puis il y a cette connaissance que les itérateurs de liste
ne sont pas invalidés par les insertions. En réflechissant
2mn, on réalise que begin() est fondamentalement invalidé par
un push_front(), donc, on peut se méfier du fait que end() le
soit de temps en temps.
Mais en fait, faudrait que je prenne un papier et un crayon
peut-être, mais je n'arrive pas à voir ce qui invalide end()
dans l'implémentation de liste quasi-circulaire dont nous
parlons.
Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:
| Ils font une liste circulaire ?
En quelque sorte. Mais un noeud dans cette liste «
circulaire » sert à marquer end(), donc de l'extérieur ce
n'est pas une liste circulaire.
Mais on peut expliquer pourquoi le code ci-dessus va boucler
indéfiniment (à condition que l.size() > 0) sans regarder
une implémentation particulière.
A condition de comprendre que end() est modifié par le
push_back(), c'est à dire que end() dépend du contenu de la
liste.
Et puis il y a cette connaissance que les itérateurs de liste
ne sont pas invalidés par les insertions. En réflechissant
2mn, on réalise que begin() est fondamentalement invalidé par
un push_front(), donc, on peut se méfier du fait que end() le
soit de temps en temps.
Mais en fait, faudrait que je prenne un papier et un crayon
peut-être, mais je n'arrive pas à voir ce qui invalide end()
dans l'implémentation de liste quasi-circulaire dont nous
parlons.
Marc Boyer writes:
| Ils font une liste circulaire ?
En quelque sorte. Mais un noeud dans cette liste «
circulaire » sert à marquer end(), donc de l'extérieur ce
n'est pas une liste circulaire.
Mais on peut expliquer pourquoi le code ci-dessus va boucler
indéfiniment (à condition que l.size() > 0) sans regarder
une implémentation particulière.
A condition de comprendre que end() est modifié par le
push_back(), c'est à dire que end() dépend du contenu de la
liste.
Et puis il y a cette connaissance que les itérateurs de liste
ne sont pas invalidés par les insertions. En réflechissant
2mn, on réalise que begin() est fondamentalement invalidé par
un push_front(), donc, on peut se méfier du fait que end() le
soit de temps en temps.
Mais en fait, faudrait que je prenne un papier et un crayon
peut-être, mais je n'arrive pas à voir ce qui invalide end()
dans l'implémentation de liste quasi-circulaire dont nous
parlons.
| On boucle. Si copy est du genre
| while (begin != end) {
| _It cur(begin);
| ++begin;
| *dest = *cur;
| }
| on ne boucle pas. Y a-t'il
Mais je crois que cela n'est pas une implémentation générique valide de
std::copy().
| On boucle. Si copy est du genre
| while (begin != end) {
| _It cur(begin);
| ++begin;
| *dest = *cur;
| }
| on ne boucle pas. Y a-t'il
Mais je crois que cela n'est pas une implémentation générique valide de
std::copy().
| On boucle. Si copy est du genre
| while (begin != end) {
| _It cur(begin);
| ++begin;
| *dest = *cur;
| }
| on ne boucle pas. Y a-t'il
Mais je crois que cela n'est pas une implémentation générique valide de
std::copy().
Jean-Marc Bourguet writes:
| Marc Boyer writes:
| > > Marc Boyer writes:
| > >| Ils font une liste circulaire ?
| > > En quelque sorte. Mais un noeud dans cette liste «
| > > circulaire » sert à marquer end(), donc de l'extérieur
| > > ce n'est pas une liste circulaire.
| > > Mais on peut expliquer pourquoi le code ci-dessus va
| > > boucler indéfiniment (à condition que l.size() > 0) sans
| > > regarder une implémentation particulière.
| > A condition de comprendre que end() est modifié par le
| > push_back(), c'est à dire que end() dépend du contenu de
| > la liste.
| > Et puis il y a cette connaissance que les itérateurs de
| > liste ne sont pas invalidés par les insertions. En
| > réflechissant 2mn, on réalise que begin() est
| > fondamentalement invalidé par un push_front(), donc, on
| > peut se méfier du fait que end() le soit de temps en
| > temps.
| > Mais en fait, faudrait que je prenne un papier et un
| > crayon peut-être, mais je n'arrive pas à voir ce qui
| > invalide end() dans l'implémentation de liste
| > quasi-circulaire dont nous parlons.
| end() n'est pas invalide. En fait ca boucle ou non suivant
| l'implementation de copy.
| Si copy est du genre
| while (begin != end) {
| *dest = *begin;
| ++begin;
| }
| On boucle. Si copy est du genre
| while (begin != end) {
| _It cur(begin);
| ++begin;
| *dest = *cur;
| }
| on ne boucle pas.
Mais je crois que cela n'est pas une implémentation générique
valide de std::copy(). La raison est que std::copy attend un
InputIterator : pour un tel iterateur, si tu fais une copie,
tu n'as plus d'assurance que l'itérateur copié est encore bon
pour faire quoi que ce soit (en particulier tester pour
égalité). Voir la table 72, en particulier la phrase
pre: r is dereferenceable.
post: r is dereferenceable or r is past-the-end.
post: any copies of the previous value of r are no longer
required either to be dereferenceable or to be in the domain
of ==.
Maintenant, si tu écris plusieurs versions de std::copy()
suivant la catégorie d'itérateurs, alors... Mains même là je
ne serais pas d'accord avec toi, parce que _It peut être
essentiellement un pointeur vers un noeud et dans ce cas, que
tu copies l'itérateur ou non, ne change rien à l'affaire.
Jean-Marc Bourguet <jm@bourguet.org> writes:
| Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:
| > > Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:
| > >| Ils font une liste circulaire ?
| > > En quelque sorte. Mais un noeud dans cette liste «
| > > circulaire » sert à marquer end(), donc de l'extérieur
| > > ce n'est pas une liste circulaire.
| > > Mais on peut expliquer pourquoi le code ci-dessus va
| > > boucler indéfiniment (à condition que l.size() > 0) sans
| > > regarder une implémentation particulière.
| > A condition de comprendre que end() est modifié par le
| > push_back(), c'est à dire que end() dépend du contenu de
| > la liste.
| > Et puis il y a cette connaissance que les itérateurs de
| > liste ne sont pas invalidés par les insertions. En
| > réflechissant 2mn, on réalise que begin() est
| > fondamentalement invalidé par un push_front(), donc, on
| > peut se méfier du fait que end() le soit de temps en
| > temps.
| > Mais en fait, faudrait que je prenne un papier et un
| > crayon peut-être, mais je n'arrive pas à voir ce qui
| > invalide end() dans l'implémentation de liste
| > quasi-circulaire dont nous parlons.
| end() n'est pas invalide. En fait ca boucle ou non suivant
| l'implementation de copy.
| Si copy est du genre
| while (begin != end) {
| *dest = *begin;
| ++begin;
| }
| On boucle. Si copy est du genre
| while (begin != end) {
| _It cur(begin);
| ++begin;
| *dest = *cur;
| }
| on ne boucle pas.
Mais je crois que cela n'est pas une implémentation générique
valide de std::copy(). La raison est que std::copy attend un
InputIterator : pour un tel iterateur, si tu fais une copie,
tu n'as plus d'assurance que l'itérateur copié est encore bon
pour faire quoi que ce soit (en particulier tester pour
égalité). Voir la table 72, en particulier la phrase
pre: r is dereferenceable.
post: r is dereferenceable or r is past-the-end.
post: any copies of the previous value of r are no longer
required either to be dereferenceable or to be in the domain
of ==.
Maintenant, si tu écris plusieurs versions de std::copy()
suivant la catégorie d'itérateurs, alors... Mains même là je
ne serais pas d'accord avec toi, parce que _It peut être
essentiellement un pointeur vers un noeud et dans ce cas, que
tu copies l'itérateur ou non, ne change rien à l'affaire.
Jean-Marc Bourguet writes:
| Marc Boyer writes:
| > > Marc Boyer writes:
| > >| Ils font une liste circulaire ?
| > > En quelque sorte. Mais un noeud dans cette liste «
| > > circulaire » sert à marquer end(), donc de l'extérieur
| > > ce n'est pas une liste circulaire.
| > > Mais on peut expliquer pourquoi le code ci-dessus va
| > > boucler indéfiniment (à condition que l.size() > 0) sans
| > > regarder une implémentation particulière.
| > A condition de comprendre que end() est modifié par le
| > push_back(), c'est à dire que end() dépend du contenu de
| > la liste.
| > Et puis il y a cette connaissance que les itérateurs de
| > liste ne sont pas invalidés par les insertions. En
| > réflechissant 2mn, on réalise que begin() est
| > fondamentalement invalidé par un push_front(), donc, on
| > peut se méfier du fait que end() le soit de temps en
| > temps.
| > Mais en fait, faudrait que je prenne un papier et un
| > crayon peut-être, mais je n'arrive pas à voir ce qui
| > invalide end() dans l'implémentation de liste
| > quasi-circulaire dont nous parlons.
| end() n'est pas invalide. En fait ca boucle ou non suivant
| l'implementation de copy.
| Si copy est du genre
| while (begin != end) {
| *dest = *begin;
| ++begin;
| }
| On boucle. Si copy est du genre
| while (begin != end) {
| _It cur(begin);
| ++begin;
| *dest = *cur;
| }
| on ne boucle pas.
Mais je crois que cela n'est pas une implémentation générique
valide de std::copy(). La raison est que std::copy attend un
InputIterator : pour un tel iterateur, si tu fais une copie,
tu n'as plus d'assurance que l'itérateur copié est encore bon
pour faire quoi que ce soit (en particulier tester pour
égalité). Voir la table 72, en particulier la phrase
pre: r is dereferenceable.
post: r is dereferenceable or r is past-the-end.
post: any copies of the previous value of r are no longer
required either to be dereferenceable or to be in the domain
of ==.
Maintenant, si tu écris plusieurs versions de std::copy()
suivant la catégorie d'itérateurs, alors... Mains même là je
ne serais pas d'accord avec toi, parce que _It peut être
essentiellement un pointeur vers un noeud et dans ce cas, que
tu copies l'itérateur ou non, ne change rien à l'affaire.
"kanze" writes:
[...]
| Dans la spécification de std::copy, il y a une contrainte :
| « result shall not be in the range [first, last). »
Oui, mais le back_inserter() n'est jamais dans cet intervalle.
De fait, c'est un proxy à quelque chose qui n'est pas un
itérateur. Ce que fait le back_inserter(), c'est qu'il modifie
la longueur de l'intervalle à chaque « *out = ... ».
| Je ne sais pas comment appliquer cette phrase au juste
elle ne s'applique pas, cherche pas.
| si result est un back_insertion_iterator, mais je crois
| qu'on pourrait bien arguer que l'intention est que cet appel
| soit invalide.
on peut tout arguer. Le point réel n'est pas vraiment de
l'argumentation, mais plutôt de la preuve de quelque chose est
ou n'est pas.
[...]
| (Je sens qu'il y a une faiblesse dans la norme ici, mais je
| ne sais pas l'exprimer mieux non plus. Peut-être quelque
| chose sur des effets de l'expression *(result + i), for 0 <=
| i < end-begin.)
La description des « requirements » est incomplète, ça tout le
monde le sait -- du moins, lorsqu'on suffisamment travaillé
avec les itérateurs et les algorithmes. Ce qui manque
problement dans ec cas particulier, c'est de supposer que
l'expressions « *out++ = t » ne modifie pas la longeur de la
suite d'entrée, mais encore là...
"kanze" <kanze@gabi-soft.fr> writes:
[...]
| Dans la spécification de std::copy, il y a une contrainte :
| « result shall not be in the range [first, last). »
Oui, mais le back_inserter() n'est jamais dans cet intervalle.
De fait, c'est un proxy à quelque chose qui n'est pas un
itérateur. Ce que fait le back_inserter(), c'est qu'il modifie
la longueur de l'intervalle à chaque « *out = ... ».
| Je ne sais pas comment appliquer cette phrase au juste
elle ne s'applique pas, cherche pas.
| si result est un back_insertion_iterator, mais je crois
| qu'on pourrait bien arguer que l'intention est que cet appel
| soit invalide.
on peut tout arguer. Le point réel n'est pas vraiment de
l'argumentation, mais plutôt de la preuve de quelque chose est
ou n'est pas.
[...]
| (Je sens qu'il y a une faiblesse dans la norme ici, mais je
| ne sais pas l'exprimer mieux non plus. Peut-être quelque
| chose sur des effets de l'expression *(result + i), for 0 <=
| i < end-begin.)
La description des « requirements » est incomplète, ça tout le
monde le sait -- du moins, lorsqu'on suffisamment travaillé
avec les itérateurs et les algorithmes. Ce qui manque
problement dans ec cas particulier, c'est de supposer que
l'expressions « *out++ = t » ne modifie pas la longeur de la
suite d'entrée, mais encore là...
"kanze" writes:
[...]
| Dans la spécification de std::copy, il y a une contrainte :
| « result shall not be in the range [first, last). »
Oui, mais le back_inserter() n'est jamais dans cet intervalle.
De fait, c'est un proxy à quelque chose qui n'est pas un
itérateur. Ce que fait le back_inserter(), c'est qu'il modifie
la longueur de l'intervalle à chaque « *out = ... ».
| Je ne sais pas comment appliquer cette phrase au juste
elle ne s'applique pas, cherche pas.
| si result est un back_insertion_iterator, mais je crois
| qu'on pourrait bien arguer que l'intention est que cet appel
| soit invalide.
on peut tout arguer. Le point réel n'est pas vraiment de
l'argumentation, mais plutôt de la preuve de quelque chose est
ou n'est pas.
[...]
| (Je sens qu'il y a une faiblesse dans la norme ici, mais je
| ne sais pas l'exprimer mieux non plus. Peut-être quelque
| chose sur des effets de l'expression *(result + i), for 0 <=
| i < end-begin.)
La description des « requirements » est incomplète, ça tout le
monde le sait -- du moins, lorsqu'on suffisamment travaillé
avec les itérateurs et les algorithmes. Ce qui manque
problement dans ec cas particulier, c'est de supposer que
l'expressions « *out++ = t » ne modifie pas la longeur de la
suite d'entrée, mais encore là...
