OVH Cloud OVH Cloud

Implementation end/rend pour list et map

19 réponses
Avatar
Marc Boyer
Bonjour,

dans le cadre d'unn projet en C, j'en suis ammené à m'interroger
sur l'implémentation des itérateurs end/rend dans list et map.

En effet, dans ces deux conteneurs, une impleméntation triviale d'un
itérateur est de faire un pointeur sur un élément interne (cellule
pour list et noeud pour map), avec une surcharge de * et ->.

Mais, comment coder end (et rend), en restant homogène ?
J'ai plusieurs idées en tête, mais la plus réaliste est aussi
la plus moche :-(

1) Ajouter des éléments end/rend
Ajouter dans la liste et dans l'arbre des éléments "en plus",
des cellules/noeuds marqueurs de fin. Mais autant c'est faisable
pour la liste (avec des tests genre it->next->next != NULL
au lieu de it->next != NULL), autant dans l'arbre, ça
complique tous les codes.

2) Itérateur comme tuple (pointeur element, pointeur conteneur)
Mettre dans un itérateur un pointeur sur le conteneur lui
même, ainsi, on peu imaginer que (NULL, p1) est le résultat
de p1->end().

A priori, je me dirige vers 2), surtout pour l'arbre de map,
mais j'ai peut-être raté un truc.

J'ai tenté de jetter un coup d'oeuil sur les sources
de la stl de gcc, et les itérateurs semblent n'etre qu'un
pointeur. Le list semble codé avec un element en rab, en
tête (?), end() étant l'adresse de ce pointeur, et
begin étant end()->next (en gros). Pour l'arbre, ça semble
être la racine, mais j'ai pas compris comment ils font si
par hasard on fait un erase() de cette racine...


Marc Boyer
--
La contractualisation de la recherche, c'est me donner de l'argent pour
faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce
que je sais faire, je le fais sans moyens...

9 réponses

1 2
Avatar
Marc Boyer
In article , Jean-Marc Bourguet wrote:
Marc Boyer writes:

En fait, avec dans l'itérateur un pointeur sur l'élément *et*
un pointeur sur le conteneur, on peut avoir le passage de end()
a son prédécesseur (et inversement) en temps constant. Mais
on double la taille d'un itérateur.
Est-ce grave docteur ? ;-)


Je suis partisan des iterateurs connaissant leur conteneur, meme quand
c'est possible de faire autrement.


Heuh, pourquoi ?
Dans ce cas, je gagne en performance sur une opération, mais ça
fait un itérateur plus gros (2 pointeurs).

(Mais je suis aussi partisan des
iterateurs sachant quand ils sont invalides plutot que faisant
n'importe quoi...)


C'est à dire ? Qu'ils aient le même résultat de déréférencer
le pointeur nul ?

Marc Boyer
--
La contractualisation de la recherche, c'est me donner de l'argent pour
faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce
que je sais faire, je le fais sans moyens...


Avatar
Jean-Marc Bourguet
Marc Boyer writes:

In article , Jean-Marc Bourguet wrote:
Marc Boyer writes:

En fait, avec dans l'itérateur un pointeur sur l'élément *et*
un pointeur sur le conteneur, on peut avoir le passage de end()
a son prédécesseur (et inversement) en temps constant. Mais
on double la taille d'un itérateur.
Est-ce grave docteur ? ;-)


Je suis partisan des iterateurs connaissant leur conteneur, meme quand
c'est possible de faire autrement.


Heuh, pourquoi ?
Dans ce cas, je gagne en performance sur une opération, mais ça
fait un itérateur plus gros (2 pointeurs).


Et permettant de faire des verifications.

(Mais je suis aussi partisan des
iterateurs sachant quand ils sont invalides plutot que faisant
n'importe quoi...)


C'est à dire ? Qu'ils aient le même résultat de déréférencer
le pointeur nul ?


Cad qu'on peut leur demander s'ils sont invalides (et ils font en fait
quelque chose de sense pour ++ permettant d'iterer sur tout et effacer
une partie assez naturellement).

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org



Avatar
Marc Boyer
Jean-Marc Bourguet wrote:
Heuh, pourquoi ?
Dans ce cas, je gagne en performance sur une opération, mais ça
fait un itérateur plus gros (2 pointeurs).


Et permettant de faire des verifications.


A quelles vérifications penses-tu ?

(Mais je suis aussi partisan des
iterateurs sachant quand ils sont invalides plutot que faisant
n'importe quoi...)


C'est à dire ? Qu'ils aient le même résultat de déréférencer
le pointeur nul ?


Cad qu'on peut leur demander s'ils sont invalides (et ils font en fait
quelque chose de sense pour ++ permettant d'iterer sur tout et effacer
une partie assez naturellement).


Je comprends pas trop ta remarque.
Tu aimerais que end()+1 == end() ?

Marc Boyer
--
La contractualisation de la recherche, c'est me donner de l'argent pour
faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce
que je sais faire, je le fais sans moyens...



Avatar
Jean-Marc Bourguet
Marc Boyer writes:

Jean-Marc Bourguet wrote:
Heuh, pourquoi ?
Dans ce cas, je gagne en performance sur une opération, mais ça
fait un itérateur plus gros (2 pointeurs).


Et permettant de faire des verifications.


A quelles vérifications penses-tu ?

(Mais je suis aussi partisan des
iterateurs sachant quand ils sont invalides plutot que faisant
n'importe quoi...)


C'est à dire ? Qu'ils aient le même résultat de déréférencer
le pointeur nul ?


Cad qu'on peut leur demander s'ils sont invalides (et ils font en fait
quelque chose de sense pour ++ permettant d'iterer sur tout et effacer
une partie assez naturellement).


Je comprends pas trop ta remarque.
Tu aimerais que end()+1 == end() ?


Non, ce n'est pas sense. Faire ++ sur un iterateur invalide parce
qu'un element a ete efface fait pointer l'iterateur sur le prochain
element valide de la collection.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org




Avatar
Marc Boyer
Jean-Marc Bourguet wrote:
Non, ce n'est pas sense. Faire ++ sur un iterateur invalide parce
qu'un element a ete efface fait pointer l'iterateur sur le prochain
element valide de la collection.


Et tu préfererais un segfault, c'est ça ?

Marc Boyer
--
La contractualisation de la recherche, c'est me donner de l'argent pour
faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce
que je sais faire, je le fais sans moyens...

Avatar
Jean-Marc Bourguet
Marc Boyer writes:

Jean-Marc Bourguet wrote:
Non, ce n'est pas sense. Faire ++ sur un iterateur invalide parce
qu'un element a ete efface fait pointer l'iterateur sur le prochain
element valide de la collection.


Et tu préfererais un segfault, c'est ça ?


Pour quelle opération?

Ma préférence pour des collections d'usage général, c'est:

- Déréférencer un itérateur invalide fait foirer une assertion.
- "Incrémenter" un itérateur invalide le fait pointer vers l'élément
non visité suivant de la collection (ou foirer une assertion s'il n'y
en a plus).
- Il est possible de tester si un itérateur est valide ou pas, et s'il y
a encore des éléments non visité ou pas.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org


Avatar
Jean-Marc Bourguet
drkm writes:

De plus, il me semble que typiquement, on n'a pas beaucoup
d'itérateurs simultanément dans une application. Il me semble qu'il
est rare d'avoir des conteneurs d'itérateurs. Donc que

sizeof( Iterator ) == 2 ;

ou

sizeof( Iterator ) == 20 ;

n'est que de peu d'intérêt.


Passage par registre plutot que passage de copies en memoire ou des
passages par reference.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Avatar
drkm
Jean-Marc Bourguet writes:

Marc Boyer writes:

In article , Jean-Marc Bourguet wrote:



[...]

Je suis partisan des iterateurs connaissant leur conteneur, meme quand
c'est possible de faire autrement.


Heuh, pourquoi ?
Dans ce cas, je gagne en performance sur une opération, mais ça
fait un itérateur plus gros (2 pointeurs).


Et permettant de faire des verifications.


De plus, il me semble que typiquement, on n'a pas beaucoup
d'itérateurs simultanément dans une application. Il me semble qu'il
est rare d'avoir des conteneurs d'itérateurs. Donc que

sizeof( Iterator ) == 2 ;

ou

sizeof( Iterator ) == 20 ;

n'est que de peu d'intérêt.

[...]

--drkm, en recherche d'un stage : http://www.fgeorges.org/ipl/stage.html



Avatar
Marc Boyer
Jean-Marc Bourguet wrote:
Passage par registre plutot que passage de copies en memoire ou des
passages par reference.


C'est pour cela que je doute entre autre.
D'un côté, avec les mécanismes de cache, je me dis que
lire un pointeur ou en lire deux contigus, ça doit pas faire
grande différence.

Enfin bon...

Marc Boyer
--
La contractualisation de la recherche, c'est me donner de l'argent pour
faire ce que je ne sais pas faire, que je fais donc mal, pendant que ce
que je sais faire, je le fais sans moyens...

1 2