voila on est en train de faire une liste simplement lié (ou liste chainé) comme celle de la bilbiothèque de c++ (même fonction, meme nom, meme parametre) et j´ai quelque misere avec la fonction insert... mais je vous explique d´abord les grandes lignes..

donc dans notre Slist, on a deux champ, la premiere étant la donné (m_donnée) et la deuxieme étant un pointeur sur la prochaine donnée (m_pSuiv) , on garde en mémoire un pointeur sur le début de la liste, un pointeur sur le dernier élément ainsi que le nombre d´élément dans la liste.

pour parcourir la liste, on se sert D´iterateur qui pointe sur l´élément précédent celui qu´on veut avoir (par exemple, si j´ai une liste avec "4, 5, 6, 7, 8" et que je veux l´élément "8", l´iterateur pointe sur le "7"), on a également un bool dans la classe iterateur qui nous dit si l´élément pointé est le premier de la liste ou non (vu qu´il n´y a pas d´élément précédent, l´adresse du pointeur sera alors exactement la bonne et non celle du précédent) et lorsque l´on arrive à la fin, le pointeur (m_pSuiv) est null

voici donc une petit résumé de ma fonction insert:

void insert(p_donné, p_itérateur)
{
if (++m_nbElements == 1) // pour ajouter dans une
liste vide

if (p_itérateur == m_pTete) // pour ajouter au déb
ut de la liste

if (p_itérateur == m_pQueue) //pour ajouter a la f
in de la liste

..... // pour ajouter quelque part au milieu
}

ca marche très bien pour tout sauf dans un cas: lo
rsqu´il n´y a qu´un seul élément dans la liste, l´itérateur pointe nécessairement sur la tete et la queue de la liste en meme temps.. vous voyez le bug? dès qu´il entre dans la fonction insert, il ira tout simplement dans la premiere condition qu´il trouvera sur son chemin et non dans la condition qu´il lui faut.. j´ai penser rajouter une condition du genre "if (m_nbElements == 1)" mais je sais pas vraiment quoi mettre dedans..

bref, je sais pas vraiment si j´ai été clair et si ma question a du sens mais bon.. c´est le plus court que j´ai pu faire!

Si ta liste est simplement chainé, tu n´a pas besoin de stocker le derniere element ? (ou il y a une subtilité que je n´ai pas suivit ?)

Tu as 2 façons de gérer cela :

- soit tu gardes la façon dont tu fais les choses, et il te faut considérer les cas particuliers.

- soit tu appliques la méthode de la "sentinelle"
--> un maillon de plus (qui pointe sur lui meme), que tu mets en fin de maillon.

Ainsi, ta liste n´est jamais vide (un cas particulier de moins) y´a au moins la sentinelle.
Ton pointeur fin pointe sur la sentinelle de façon a ce que tu puisses itérer avec :

for(i=begin();i!=end();i.incremente())

et le seul cas ou les 2 pointeurs begin et end pointent au meme endroit, c´est quand la liste est vide (ils pointent tous les deux sur la sentinelle)

ça te rajoute un element, mais ta liste contient beaucoup moins de cas particuliers. Et les STL (std::slist et std::list) sont gérés comme ça

godrik: on garde un pointeur sur la fin de la liste en tout temps, histoire de ne pas reparcourir la liste a chaque fois qu´on fait un .end()

Fvirtman: la est le probleme, on doit garder cette structure de liste (c´est un exercice dans mon cours d´info), c´est-à-dire que la liste peut etre vide et le dernier élément a un pointeur null.. l´élément "bidon" à la fin de la liste est représenté par ce pointeur null

le gros du probleme, c´est que je ne peux pas comparer l´itérateur à m_pTete ou m_pQueue puisque les deux sont vrais parce qu´ils pointent sur la meme donnée...

Alors :
- Ajouter une sentinelle ne nécessite pas de changer tes structures.

Sinon, si tu ne veux pas de sentinelle :
- Le but d´une liste simplement chainée n´est pas de stocker le dernier élément. Je pense que ton pointeur "end" t´encombre si tu ne geres pas de sentinelle.
Pourquoi aurais tu besoin sans arret d´un pointeur sur le dernier élément ? celui ci est + sollicité que les autres ?
Tester que c´est le dernier élément revient juste a tester que le pointeur "suivant" est a NULL.

"le gros du probleme, c´est que je ne peux pas comparer l´itérateur à m_pTete ou m_pQueue puisque les deux sont vrais parce qu´ils pointent sur la meme donnée... "

--> ?
un itérateur est "vrai" ?
Comparer l´itérateur d´une liste chainée, c´est simplement comparer les adresses qu´ils pointent, c´est tout !

Si tu consideres m_pTete et m_pQueue comme des pointeurs, le simple teste m_pQueue == m_pTete te permet de savoir si ces pointeurs montrent le meme élément !
Mais je suis convaincu que dans une liste simplement chainée, tu n´as pas besoin de m_pQueue...

un pointeur sur le dernier élément sert a renvoyer.. le dernier élément! sinon, dans la fonction .end(), faudrait refaire la liste à partir du début simplement pour renvoyé le dernier élément? et s´il y a 3 millions d´éléments? ca risque d´etre long!

l´iterateur est "vrai" lorsque l´adresse pointé par celui-ci est égal à l´adresse de m_pTete ou m_pQueue.. lors du test (it == m_pTete), cette comparaison renvoie nécessairement vrai ou faux... tu pige? donc dans le cas ou ou it == m_pQueue == m_pTete, ceux-ci sont "vrai"... faut vraiment s´expliquer sur tout?!

le test m_pQueue == m_pTete permet de savoir s´il pointe sur le meme élément je suis bien d´accord, ceci dit, ca ne me dit pas si la donnée doit être inséré AVANT ou APRES la donnée pointé par m_pTete et m_pQueue!

Je suis d´accor que si tu veux respecter l´interface de la STL il faut pouvoir répondre a end().
mais pourquoi ne pas renvoyer NULL lors de cet appel?

la n´est pas le probleme..

Je trouve que tu te casses la tete pour rien.
"l´iterateur est "vrai" lorsque l´adresse pointé par celui-ci est égal à l´adresse de m_pTete ou m_pQueue"
--> normalement, un itérateur n´est ni "vrai" ni "faux", il est égal a end(), ou a begin() si tu veux, ou a autre chose...

"et s´il y a 3 millions d´éléments? ca risque d´etre long"
--> Je sais bien (crois moi, j´en ai bouffe des listes chainées), mais la ou je ne suis pas d´accord, c´est qu´il n´y a pas de réel intéret dans une slist de faire cela. Comme dit Godrik, fait juste que end() renvoie NULL dans ce cas la.
Ta fonction end() sert normalement uniquement a savoir si tu as atteint la fin de la liste, si un itérateur IT déja placé, donné, l´a atteint...
Dans le cas d´une slist, tu as juste struct::suivant == NULL pour définir qu´une liste est finie, il suffit de tester l´élément ou tu es et de regarder si le pointeur suivant est a NULL ou pas, ainsi, tu sauras si tu es sur end().

Voila, si tu as l´impression que je réponds a coté, ce n´est pas parce que je ne sais pas faire de slist (j´en ai bouffé des slist), c´est juste que je trouve que tu te compliques la vie pour une slist, et que dans cette vie compliquée, j´ai du mal a te suivre.

je suis sur que tu t´y connais assez, sinon je t´aurais meme pas poser la question..

mais relit mon deuxieme message... j´ai pas le choix de le faire comme ca, c´est un exercice à faire dans un cours, le prof nous a donné cette structure de liste et il nous as dit de la complété.. on sait très bien que ce n´est pas la seule et surtout la meilleure facon de faire une list, mais c´est comme ca qu´on doit la faire!

Bon, alors on va dire que ce dernier pointeur queue est obligatoire.
Si tu inseres un élément, tu l´inseres a la fin ?
Donc tu n´as qu´as te dire que si tu inseres un élément, tu l´inseres APRES le derniere élément.

Comme ça, tu te sers de ton dernier pointeur, tu crées un nouvel élément E;
tu remplis E.
tu mets Mqueue->suivant = E;
puis ensuite Mqueue = E; (pour bien remettre ton pointeur de fin sur le dernier élément)
Ainsi, tu gardes tout cohérent

Mais testes bien sur que Mqueue ne pointe pas sur NULL (liste vide)
si c´est le cas, tu crées une nouvelle liste et tu fous les 2 pointeurs (tete et queue) sur le meme et seul élément.

Pour l´insertion, il ne devrait pas y avoir de soucis ni de conflit avec Mtete, si tu inseres apres Mqueue (insertion en fin de liste)

ca ne fait jamais que 4 cas:
tu insere au début, ou en fin, ou ni l´un ni l´autre, ou les deux.

je vais faire une petite trace pour etre sur qu´on se comprend bien car je crois que j´ai pas été vraiment clair :P

disons que j´ajoute 2 et 6 dans la liste

a date, on a 4 cas (dans cette ordre dans la fonction insert) :
-ajout dans une liste vide if (++m_nbElement == 1)
-ajout a la tete if (it == m_pTete)
-ajout a la queue if (it == m_pQueue)
-ajout au milieu (par défaut à la fin)

alors quand je fait list.insert(2) il s´insère dans une liste vide, un pointeur est donc assigner à m_pTete et à m_pQueue (il est à la fois, au début et à la fin de la liste)
donc m_pTete pointe sur la donnée qui elle a un pointeur null

le probleme vient quand je fais list.insert(6), il passe par dessus la premiere condition (ajout dans une liste vide), il arrive donc a "if (it == m_pTete)" et s´insère a la tete car end() et begin() pointe sur la meme chose... donc dans la liste on obtient {6, 2}

et si on inverse les conditions (mettre m_pQueue avant m_pTete dans la fonction insert), on arrive au même résultat si on insère 2 et 6, on obtient {6, 2}

j´espere avoir été plus clair cette fois ci.. si non bah laisser tomber et j´attendrai à demain pour savoir :P

petite précision quand je disais

"- ajout au milieu (par défaut à la fin)"

je voulais dire a la fin de la fonction et non a la fin de la liste... car la liste doit etre en ordre..

Un exemple est déja + parlant.

je numérote tes cas :

1)ajout dans une liste vide if (++m_nbElement == 1)
2)ajout a la tete if (it == m_pTete)
3)ajout a la queue if (it == m_pQueue)
4)ajout au milieu (par défaut à la fin)

D´acc, donc si tu gardes tes conditions dans l´ordre donné, forcément, il tombe sur le cas "insérer en tete" d´abord : donc tu auras bien 6,2. (il passe dans le cas 2 )

Par contre, ce qu´il faut c´est tester d´abord m_pQueue, avant m_pTete. (autrement dit permuter les tests 2 et 3)
Ainsi, normalement, il devrait passer dans la condition 3 quand tu mets ton 6.
Et, normalement, tu devrais bien avoir 2,6 a la sortie et non 6,2.
ça veut dire que ta sous fonction qui insert à m_pqueue (donc l´appel de 3 ) a un petit bug.

Vérifie déja que quand tu inseres ton 6, tu passes bien dans cette condition (la 3) APRES PERMUTATION. (avec un printf si tu n´as pas de débuggueur)

si je permute les conditions 2 et 3, il arrivera le meme bug (mais inverser) lorsque je vais insérer respectivement 6 et 2 :

6 passera par la condition 1, qui l´insère dans une liste vide

2 passera par condition 3 (maintenant 2 avec la permutation) et s´insère à la queue donc je vais avoir 6,2

le probleme c´est que les conditions 2 et 3 sont toujours vrais lorsqu´on insère le deuxieme éléments de la liste, donc il va toujours s´inséré dans la premiere condition qu´il rencontre!

notes qu´au pire tu peux detecter le cas en regardant ptr=beggin && ptr=end
...

De toute façon, dans le cas ou t´as un seul élément, il faut trancher ! et c´est a toi de trancher !
Soit tu inseres avant, soit tu inseres apres, mais de toute façon, c´est ambigu !

c´est très ambigu... d´ou ma question : comment faire pour savoir si je dois insérer avant ou apres..!

En fait, c´est toi qui voit, c´est toi qui écris la lib...

Ici, tu cherches a mimer la STL alors regarde ce qu´elle fait.