iterator = NULL

kanze

08/09/2005 à 14:14

Gabriel Dos Reis wrote:

Henri de Solages writes:

| > Pourquoi ne pas placer ces itérateurs dans un vector ?

| Je n'aime pas les vector car, quand on fait un erase, les
| iterateurs sur les élements suivants ne sont plus valides.

Oui mais d'après ce que tu as dit jusqu'à présent, tu ne
gardes pas des itérateurs (de vecteurs) vers les itérateurs de
(listes), donc ta crainte n'a aucun fondement dans ce cas
ici. De plus, si tu ne fais pas de erase() sur ton tableau,
pourquoi veux-tu en faire sur un vector ?

Parce que le vecteur ne contient qu'un sous-ensemble des
éléments dans la liste, et que ce sous-ensemble évolve ?

Évidemment, si j'ai besoin de pouvoir enlever des éléments
arbitraire d'une collection sans invalider des itérateurs sur
des éléments qui suivent, je n'utilise pas std::vector. Mais ce
n'est pas le cas le plus fréquent, même si ça peut arriver. J'ai
cru comprendre que s'il y avait plusieurs types de collections,
c'est parce que parfois un type ne convenait pas, et qu'il
fallait s'en servir d'un autre.

En général, c'est vrai, j'évite de maintenir des itérateurs au
delà de l'algorithme qui s'en sert. Je crois que je n'ai jamais
fait une collection d'itérateurs. Mais il faut analyser chaque
cas, et non partir du principe de ne pas se servir du tout de
vector parce qu'il invalide certains itérateurs dans certains
cas.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Gabriel Dos Reis

08/09/2005 à 14:14

Marc Boyer writes:

| Gabriel Dos Reis a écrit :
| > Loïc Joly writes:
| >
| >| > Bonjour.
| >| > Est-il légal d'assigner la valeur NULL à un itérateur ?
| >|
| >| Souvent, l'équivalent moral de NULL pour un itérateur sur une
| >| collection "c" est c.end()
| >
| > Cela peut cependant réserver des surprises.
| >
| > list<int> l;
| > // ...
| > copy(l.begin(), l.end(), back_inserter(l));

[...]

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

-- Gaby

Gabriel Dos Reis

08/09/2005 à 14:18

"kanze" writes:

| Gabriel Dos Reis wrote:
| > Henri de Solages writes:
|
|
| > | > Pourquoi ne pas placer ces itérateurs dans un vector ?
|
| > | Je n'aime pas les vector car, quand on fait un erase, les
| > | iterateurs sur les élements suivants ne sont plus valides.
|
| > Oui mais d'après ce que tu as dit jusqu'à présent, tu ne
| > gardes pas des itérateurs (de vecteurs) vers les itérateurs de
| > (listes), donc ta crainte n'a aucun fondement dans ce cas
| > ici. De plus, si tu ne fais pas de erase() sur ton tableau,
| > pourquoi veux-tu en faire sur un vector ?
|
| Parce que le vecteur ne contient qu'un sous-ensemble des
| éléments dans la liste, et que ce sous-ensemble évolve ?

Mais, même dans ce cas là, il n'est faisait pas de erase() -- ou
équivalent -- avant, James.

-- Gaby

kanze

08/09/2005 à 14:28

Gabriel Dos Reis wrote:

Henri de Solages writes:

| >>Je veux un tableau d'itérateurs sur des éléments d'une list.

| > Sinon, ce dont tu as besoin, c'est d'un délimiteur de
| > fin, donc le end() de la liste me semble une bonne
| > valeur interdite.

| Mais si j'ajoute ensuite des éléments à ma liste, le end()
| de la list est-il tenu par la norme de garder une même
| valeur ?

Tu n'as pas à te soucier de end() -- il suffit que tu ne le
stockes nulle part (c'est une proprieté intrinsèque de chaque
liste à chaque instant). Stockes uniquement les itérateurs
vers les éléments que tu as effectivement mis dans la liste,
non des artéfacts comme begin()/end().

C'est un point intéressant. J'aurais cru avoir les mêmes
garanties sur les itérateurs obtenu de begin() ou de end() que
sur les autres itérateurs. D'ailleurs, la plupart du temps, les
autres itérateurs que je pourrais avoir en dérivent : le
résultat de std::find dérive bien de l'itérateur que je lui ai
passé, qui lui dérive de begin().

Dans le cas de vector, par exemple, si l'itérateur suit
l'élément effacé ou inséré, ou s'il y a réallocation,
l'itérateur est invalidé -- dans le cas du résultat de end(), il
suit forcément, et donc, il est toujours invalidé. Dans le cas
de liste, en revanche, j'aurais crû qu'il n'aurait jamais de
problème avec end (parce que l'itérateur est valid tant qu'on
n'efface pas l'élément de la collection, et qu'on ne peut pas
effacer end()), de même qu'on n'aurait un problème avec begin()
que si on efface le premier élément.

Mais évidemment, surtout dans le cas de begin(), il faut savoir
ce qu'on entend par valide. Si la liste n'est pas vide, begin()
designe un élément, sinon, il est égal à end(). Si je le sauve,
et ensuite j'insère un élément au début, l'itérateur sauvé
designe toujours l'élément qu'il désignait avant (ou end(), s'il
designait end() avant), ce qui n'est plus le début.

C'est, d'ailleurs, ce que je croyais que g++ faisait (sans
l'avoir vérifier, mais d'après le code que j'ai lu).

Je suis curieux pourquoi tu penses que les résultats de begin()
ou de end() sont des exceptions. Ou est-ce que tu es concerné
simplement du fait que dans quelque chose comme ceci :

typedef std::list< int > L ;
L l ;
l.push_back( 1 ) ;
L::iterator i = l.begin() ;
l.push_front( 0 ) ;

i ne désigne plus le même élément que l.begin() ?

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Gabriel Dos Reis wrote:

Henri de Solages <solages@CICT.fr_> writes:

| >>Je veux un tableau d'itérateurs sur des éléments d'une list.

| > Sinon, ce dont tu as besoin, c'est d'un délimiteur de
| > fin, donc le end() de la liste me semble une bonne
| > valeur interdite.

| Mais si j'ajoute ensuite des éléments à ma liste, le end()
| de la list est-il tenu par la norme de garder une même
| valeur ?

Tu n'as pas à te soucier de end() -- il suffit que tu ne le
stockes nulle part (c'est une proprieté intrinsèque de chaque
liste à chaque instant). Stockes uniquement les itérateurs
vers les éléments que tu as effectivement mis dans la liste,
non des artéfacts comme begin()/end().

C'est un point intéressant. J'aurais cru avoir les mêmes
garanties sur les itérateurs obtenu de begin() ou de end() que
sur les autres itérateurs. D'ailleurs, la plupart du temps, les
autres itérateurs que je pourrais avoir en dérivent : le
résultat de std::find dérive bien de l'itérateur que je lui ai
passé, qui lui dérive de begin().

Dans le cas de vector, par exemple, si l'itérateur suit
l'élément effacé ou inséré, ou s'il y a réallocation,
l'itérateur est invalidé -- dans le cas du résultat de end(), il
suit forcément, et donc, il est toujours invalidé. Dans le cas
de liste, en revanche, j'aurais crû qu'il n'aurait jamais de
problème avec end (parce que l'itérateur est valid tant qu'on
n'efface pas l'élément de la collection, et qu'on ne peut pas
effacer end()), de même qu'on n'aurait un problème avec begin()
que si on efface le premier élément.

Mais évidemment, surtout dans le cas de begin(), il faut savoir
ce qu'on entend par valide. Si la liste n'est pas vide, begin()
designe un élément, sinon, il est égal à end(). Si je le sauve,
et ensuite j'insère un élément au début, l'itérateur sauvé
designe toujours l'élément qu'il désignait avant (ou end(), s'il
designait end() avant), ce qui n'est plus le début.

C'est, d'ailleurs, ce que je croyais que g++ faisait (sans
l'avoir vérifier, mais d'après le code que j'ai lu).

Je suis curieux pourquoi tu penses que les résultats de begin()
ou de end() sont des exceptions. Ou est-ce que tu es concerné
simplement du fait que dans quelque chose comme ceci :

typedef std::list< int > L ;
L l ;
l.push_back( 1 ) ;
L::iterator i = l.begin() ;
l.push_front( 0 ) ;

i ne désigne plus le même élément que l.begin() ?

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Vous avez filtré cet utilisateur ! Consultez son message

Gabriel Dos Reis wrote:

Henri de Solages writes:

| >>Je veux un tableau d'itérateurs sur des éléments d'une list.

| > Sinon, ce dont tu as besoin, c'est d'un délimiteur de
| > fin, donc le end() de la liste me semble une bonne
| > valeur interdite.

| Mais si j'ajoute ensuite des éléments à ma liste, le end()
| de la list est-il tenu par la norme de garder une même
| valeur ?

Tu n'as pas à te soucier de end() -- il suffit que tu ne le
stockes nulle part (c'est une proprieté intrinsèque de chaque
liste à chaque instant). Stockes uniquement les itérateurs
vers les éléments que tu as effectivement mis dans la liste,
non des artéfacts comme begin()/end().

C'est un point intéressant. J'aurais cru avoir les mêmes
garanties sur les itérateurs obtenu de begin() ou de end() que
sur les autres itérateurs. D'ailleurs, la plupart du temps, les
autres itérateurs que je pourrais avoir en dérivent : le
résultat de std::find dérive bien de l'itérateur que je lui ai
passé, qui lui dérive de begin().

Dans le cas de vector, par exemple, si l'itérateur suit
l'élément effacé ou inséré, ou s'il y a réallocation,
l'itérateur est invalidé -- dans le cas du résultat de end(), il
suit forcément, et donc, il est toujours invalidé. Dans le cas
de liste, en revanche, j'aurais crû qu'il n'aurait jamais de
problème avec end (parce que l'itérateur est valid tant qu'on
n'efface pas l'élément de la collection, et qu'on ne peut pas
effacer end()), de même qu'on n'aurait un problème avec begin()
que si on efface le premier élément.

Mais évidemment, surtout dans le cas de begin(), il faut savoir
ce qu'on entend par valide. Si la liste n'est pas vide, begin()
designe un élément, sinon, il est égal à end(). Si je le sauve,
et ensuite j'insère un élément au début, l'itérateur sauvé
designe toujours l'élément qu'il désignait avant (ou end(), s'il
designait end() avant), ce qui n'est plus le début.

C'est, d'ailleurs, ce que je croyais que g++ faisait (sans
l'avoir vérifier, mais d'après le code que j'ai lu).

Je suis curieux pourquoi tu penses que les résultats de begin()
ou de end() sont des exceptions. Ou est-ce que tu es concerné
simplement du fait que dans quelque chose comme ceci :

typedef std::list< int > L ;
L l ;
l.push_back( 1 ) ;
L::iterator i = l.begin() ;
l.push_front( 0 ) ;

i ne désigne plus le même élément que l.begin() ?

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

kanze

08/09/2005 à 14:55

Henri de Solages wrote:

Je veux un tableau d'itérateurs sur des éléments d'une list.

Sinon, ce dont tu as besoin, c'est d'un délimiteur de fin,
donc le end() de la liste me semble une bonne valeur
interdite.

Mais si j'ajoute ensuite des éléments à ma liste, le end() de
la list est-il tenu par la norme de garder une même valeur ?

Je crois que oui, parce que l'insertion n'invalide aucun
itérateur, et la suppression n'en invalide que ceux qui
désignaient l'élément supprimé (ce qui n'est jamais le cas d'un
résultat de end()). En ce qui concerne std::list, je crois même
que ça marche.

Il faut faire un peu gaffe quand même. On a, par exemple,
l'habitude de dire que std::vector::push_back n'invalide aucun
itérateur si la capacity suffisait. Or, selon la norme,
push_back est défini en termes d'insert, et std::vector::insert
invalide toujours tous les itérateurs qui suivent l'élément
inséré. Et un itérateur end() suit bien l'élément qu'on a
inséré.

En fait, je le trouve utile de considérer qu'il y a un élément
virtuel qui est toujours présent et qui se trouve toujours à la
fin, et que end() désigne cet élément. Aussi, que tant qu'un
itérateur est valid, il désigne le même élément (et non
forcément le même endroit dans la collection) -- l'élément
virtuel, si l'itérateur provient de end(). Ensuite, tu appliques
les règles de validité des itérateurs de chaque collection : en
cas de modification, un vector invalide toujours tous les
itérateurs aux éléments derrière l'élément inséré ou suppri mé,
donc en tous les cas, un itérateur en provenance de end(). Une
std::list, en revanche, n'invalide que l'itérateur de l'élément
supprimé, donc, jamais la valeur de end().

Attention cependant en ce qui concerne la définition de la
validité quand tu l'appliques au résultat de begin().
L'itérateur est valide tant qu'il désigne le même élément. Or, à
l'encontre de end(), tu peux bien insérer des éléments devant
begin(). Ce qui veut dire que l'itérateur n'est plus égal à
begin().

Les implications en ce qui concerne les rbegin() et les rend()
ne sont pas forcement très intuitives non plus.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Henri de Solages wrote:

Je veux un tableau d'itérateurs sur des éléments d'une list.

Sinon, ce dont tu as besoin, c'est d'un délimiteur de fin,
donc le end() de la liste me semble une bonne valeur
interdite.

Mais si j'ajoute ensuite des éléments à ma liste, le end() de
la list est-il tenu par la norme de garder une même valeur ?

Je crois que oui, parce que l'insertion n'invalide aucun
itérateur, et la suppression n'en invalide que ceux qui
désignaient l'élément supprimé (ce qui n'est jamais le cas d'un
résultat de end()). En ce qui concerne std::list, je crois même
que ça marche.

Il faut faire un peu gaffe quand même. On a, par exemple,
l'habitude de dire que std::vector::push_back n'invalide aucun
itérateur si la capacity suffisait. Or, selon la norme,
push_back est défini en termes d'insert, et std::vector::insert
invalide toujours tous les itérateurs qui suivent l'élément
inséré. Et un itérateur end() suit bien l'élément qu'on a
inséré.

En fait, je le trouve utile de considérer qu'il y a un élément
virtuel qui est toujours présent et qui se trouve toujours à la
fin, et que end() désigne cet élément. Aussi, que tant qu'un
itérateur est valid, il désigne le même élément (et non
forcément le même endroit dans la collection) -- l'élément
virtuel, si l'itérateur provient de end(). Ensuite, tu appliques
les règles de validité des itérateurs de chaque collection : en
cas de modification, un vector invalide toujours tous les
itérateurs aux éléments derrière l'élément inséré ou suppri mé,
donc en tous les cas, un itérateur en provenance de end(). Une
std::list, en revanche, n'invalide que l'itérateur de l'élément
supprimé, donc, jamais la valeur de end().

Attention cependant en ce qui concerne la définition de la
validité quand tu l'appliques au résultat de begin().
L'itérateur est valide tant qu'il désigne le même élément. Or, à
l'encontre de end(), tu peux bien insérer des éléments devant
begin(). Ce qui veut dire que l'itérateur n'est plus égal à
begin().

Les implications en ce qui concerne les rbegin() et les rend()
ne sont pas forcement très intuitives non plus.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Vous avez filtré cet utilisateur ! Consultez son message

Henri de Solages wrote:

Je veux un tableau d'itérateurs sur des éléments d'une list.

Sinon, ce dont tu as besoin, c'est d'un délimiteur de fin,
donc le end() de la liste me semble une bonne valeur
interdite.

Mais si j'ajoute ensuite des éléments à ma liste, le end() de
la list est-il tenu par la norme de garder une même valeur ?

Je crois que oui, parce que l'insertion n'invalide aucun
itérateur, et la suppression n'en invalide que ceux qui
désignaient l'élément supprimé (ce qui n'est jamais le cas d'un
résultat de end()). En ce qui concerne std::list, je crois même
que ça marche.

Il faut faire un peu gaffe quand même. On a, par exemple,
l'habitude de dire que std::vector::push_back n'invalide aucun
itérateur si la capacity suffisait. Or, selon la norme,
push_back est défini en termes d'insert, et std::vector::insert
invalide toujours tous les itérateurs qui suivent l'élément
inséré. Et un itérateur end() suit bien l'élément qu'on a
inséré.

En fait, je le trouve utile de considérer qu'il y a un élément
virtuel qui est toujours présent et qui se trouve toujours à la
fin, et que end() désigne cet élément. Aussi, que tant qu'un
itérateur est valid, il désigne le même élément (et non
forcément le même endroit dans la collection) -- l'élément
virtuel, si l'itérateur provient de end(). Ensuite, tu appliques
les règles de validité des itérateurs de chaque collection : en
cas de modification, un vector invalide toujours tous les
itérateurs aux éléments derrière l'élément inséré ou suppri mé,
donc en tous les cas, un itérateur en provenance de end(). Une
std::list, en revanche, n'invalide que l'itérateur de l'élément
supprimé, donc, jamais la valeur de end().

Attention cependant en ce qui concerne la définition de la
validité quand tu l'appliques au résultat de begin().
L'itérateur est valide tant qu'il désigne le même élément. Or, à
l'encontre de end(), tu peux bien insérer des éléments devant
begin(). Ce qui veut dire que l'itérateur n'est plus égal à
begin().

Les implications en ce qui concerne les rbegin() et les rend()
ne sont pas forcement très intuitives non plus.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Stan

08/09/2005 à 15:01

"kanze" a écrit dans le message de news:

En général, c'est vrai, j'évite de maintenir des itérateurs au
delà de l'algorithme qui s'en sert. Je crois que je n'ai jamais
fait une collection d'itérateurs. Mais il faut analyser chaque

Il serait interessant de savoir à quoi est destinée cette collection
d'itérateurs...
J'ai l'intuition ( probablement erronée ) qu'un set pourrait être utile pour
manipuler ces itérateurs ( genre union / intersection ).
Mais je ne trouve pas d'exemple concret qui pourrait me donner raison.

Des idées ?

--
-Stan

kanze

08/09/2005 à 15:06

Marc Boyer wrote:

Depuis quand est-ce qu'il y a un pointeur NULL dans une
liste chaînée en C.

A l'école ?

Là, je ne saurais pas. Je n'ai jamais eu de cours d'informatique
ou de programmation dans ma vie. (Enfin, prèsque. J'ai assisté à
un cour de l'autocodeur 1401 en auditeur libre quand mon père le
suivait. Mais on n'y a pas abordé des listes chaînées.)

Je sais que j'ai effectivement vu une telle technique dans des
livres. Mais que je n'ai jamais compris pourquoi -- la solution
avec la liste circulaire est tellement évidente, et bien plus
simple à coder ET plus rapide. Il ne m'est jamais venu à
l'ésprit d'en faire autrement.

Peut-être c'est parce que quand j'ai abordé les listes chaînées
pour la première fois, on avait déjà assez de mémoire pour ne
pas être obligé à s'emmerder avec des listes à chaînage simple,
or que les auteurs des livres ont commencé avec des listes à
chaînage simple (où je ne vois guère d'autre solution qu'une
valeur sentinelle comme NULL), et ont simplement continué pareil
avec des listes à chaînage double, même si une solution plus
simple existe.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jean-Marc Bourguet

08/09/2005 à 15:17

"kanze" writes:

Peut-être c'est parce que quand j'ai abordé les listes chaînées
pour la première fois, on avait déjà assez de mémoire pour ne
pas être obligé à s'emmerder avec des listes à chaînage simple,
or que les auteurs des livres ont commencé avec des listes à
chaînage simple (où je ne vois guère d'autre solution qu'une
valeur sentinelle comme NULL), et ont simplement continué pareil
avec des listes à chaînage double, même si une solution plus
simple existe.

Ca depend du contexte, utiliser NULL peut etre utile si tu dois
parcourir la fin de la liste et que tu n'as pas acces au noeud special
pour t'en servir de sentinelle (par exemple si ta liste est invasive).

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

Marc Boyer

08/09/2005 à 16:49

Gabriel Dos Reis a écrit :

Marc Boyer writes:
| > Je crois. Je crois qu'il font à peu près comme j'ai fait
| > ci-dessus. J'ai l'impression que la seule différence entre leur
| > code et ce que je faisais auparavent (depuis au moins vingt ans
| > maintenant), c'est qu'ils allouent la racine dynamiquement,
|
| Oui.

Non, il n'y a pas d'allocation dynamique de la racine.

Je pense que nous ne parlons pas du même code: j'ai
un GCC 3.3, et le fichier stl_list.h ne contient pas
de _List_impl.

Marc Boyer
--
À vélo, prendre une rue à contre-sens est moins dangeureux
que prendre un boulevard dans le sens légal. À qui la faute ?

Gabriel Dos Reis

08/09/2005 à 17:13

Marc Boyer writes:

| Gabriel Dos Reis a écrit :
| > Marc Boyer writes:
| >| > Je crois. Je crois qu'il font à peu près comme j'ai fait
| >| > ci-dessus. J'ai l'impression que la seule différence entre leur
| >| > code et ce que je faisais auparavent (depuis au moins vingt ans
| >| > maintenant), c'est qu'ils allouent la racine dynamiquement,
| >|
| >| Oui.
| >
| > Non, il n'y a pas d'allocation dynamique de la racine.
|
| Je pense que nous ne parlons pas du même code: j'ai
| un GCC 3.3, et le fichier stl_list.h ne contient pas
| de _List_impl.

Je parlais effectivement de 3.4.x et 4.0.x -- je n'ai plus le source de
3.3.x sur ma machine actuelle, mais je te crois.

-- Gaby

iterator = NULL

10 réponses

Veuillez sélectionner un problème