replication d'objet dans un container STL

BOnjour... avis au amateur, j'ai trop du mal a jouer avec les container de la STL!

Mon programme doit simuler la reproduction d'entité vivante.

L'entité vivante est un objet LIFE, ou live() renvoie le status : JE_VIS, JE_ME_REPLIQUE, JE_MEURT.

En gros, il s'agit de mettre des Life dans un container, de tester les Life du container dans une boucle, et d' enlever ou d'ajouter une copie dans dans le container en fct du status.


Exemple avec un list!

list <LIFE> listLife;
LIFE lifeDepart;
list.push_back(lifeDepart); //On part d'une entité.

list <LIFE>::iterator it;

While ( temps < tempsMax)
{
for ( it = listLife.begin(); it!= listLife.end(); ++it)
{
int status = it->live();

if ( status == JE_ME_REPLIQUE)
list.push_back(&it);

if ( status == JE_MEURT)
list.remove(it);
}
}


Bon, bien sur ca marche pas!! Car je sais pas trop comment ca marche la liste! J'ai des segment faut et tout!
Et sinon, c'est quoi le mieux pour ce que je fait : list ? vector ? deques?
et encore, comment je peux faire un parcours aleatoire de la liste? Car, si je definit une population Maximum, je vais avoir des entités vivantes avantagée.....Bref, bien compliqué tout ca!!

Bref, si on execute dans la boucle ça :

cout<<listLife.size()<<endl;

Je devrais avoir une suite exponentiel du type:
1,2,4,8,16,32 ....pMax

IDK

:tagcode:

Si tu as des segmentation faults, une possibilité est que ton objet ne réponde pas aux critères nécessaires pour pouvoir être mis dans un conteneur de la STL. En particulier, ils doivent être copiables. Pourrait-on voir leurs constructeurs de recopie, leur opérateur=, leur destructeur ?

Autre point à suivre : Modifier la liste en même temps que tu itères dessus est dangereux. Par exemple, dans ton code, tu fais list.remove(it) suivi d'un it++, alors que remove a rendu it invalide. Soit tu travaille sur deux listes, une source, une destination (ce qui peut simplifier aussi la stabilité de l'algorithme, dès qu'il y aura interactions entre les différentes entités, même si c'est moins efficace en mémoire), soit tu fais bien attention à ne pas utiliser d'itérateurs invalides (par exemple pour une list, en sauvant l'itérateur, puis en l'incrémentant, puis en effaçant la valeur sauvée, pour un vecteur, étant donné que tous les itérateurs peuvent être invalidés à chaque changement de taille, il vaut mieux alors travailler par index).

Pour le choix entre conteneurs, Laurent avait pondu un joli dessin : http://c.developpez.com/faq/cpp/?pag...hoix_conteneur

Salut,

En gros, l'idéal est peut etre de fournir une méthode à ta classe live qui permette de renvoyer un nouvel objet qui soit le "clone" de l'objet qui se réplique, et d'insérer ce clone dans ton conteneur.

Ainsi, tu pourrais envisager une fonction "clone()" (ca va bien, ca non:question) sous la forme de

Code:

---

1 2 3 4 5 6 7 8 9

LIVE LIVE::clone() { LIVE nouveau(*this);// ou peut etre préféreras tu utiliser // le constructeur par défaut ? //si tu as dans ta classe LIVE un membre chargé de compter le nombre // de réplications, il faut penser à l'incrémenter ici :D return nouveau; }

---

A partir de là, tu pourras envisager d'insérer l'objet nouvellement créé sous la forme de

Code:

---

1 2 3

if ( status == JE_ME_REPLIQUE) listLife.push_back(it->clone());

---

Ceci dit, tu aurais visiblement intérêt à envisager le status sous la forme d'une énumération...

En effet, il est difficilement envisageable qu'une meme entité puisse avoir plus d'un status à la fois...

L'énumération pourrait prendre la forme de

Code:

---

1 2 3 4 5 6 7

enum estatus { JE_VIS, JE_ME_REPLIQUE, JE_MEURE };

---

ton int status deviendrait un estatus, et, en outre, ta succession de if serait remplacée par un switch... case, du seul fait qu'encore une fois, une meme entité n'auras jamais deux status en meme temps ;)

Les trois if seraient donc avantageusement remplacés par

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

estatus status== it->live(); switch(status) { case JE_VIS: /*...*/ break; case JE_ME_REPLIQUE: listLife.push_back(it->clone());/* n'oublie pas que tu dois travailler sur   * l'objet list existant :D */ break: case JE_MEURE: /* Attention... l'itérateur devient invalide apres la suppression   et, comme on doit etre sur de passer par l'élément suivant   dans la liste, il faut penser à prendre temporairement celui qui précede */ list <LIFE>::iterator temp=it--; listLife.erase(it);/* ici aussi, tu dois travailler sur l'objet list existant ;) */ it=temp; break; }

---

Pour finir, un mot du choix du conteneur à utiliser...

La grosse difficulté vient du fait qu'un acces aléatoire implique plutot l'utilisation d'un vector, alors que de nombreuses insertions et de nombreux retraits potentiels "au milieu des éléments" impliquent, plutot, l'utilisation d'une liste ou d'une file...

De plus, il faut garder en mémoire que, théoriquement, la première entité a de fortes chances, apres s'etre répliquée un certain nombre de fois, d'être parmis les premières à mourrir, et que le cycle meme des réplications a des chances d'être basé plus sur une variable temporelle (je me réplique toutes les X minutes) que sur une sélection aléatoire de l'entité à répliquer...

Partant de là, il *semble* cohérent d'estimer que l'ajout se fasse "vers la fin" de la liste, et que le retrait se fasse *le plus souvent* "vers le début"...

La liste (std::list) *semble* donc définitivement etre la meilleure solution, mais il faudra réfléchir un peu à réorganiser la boucle, car une boucle "pour" finira fatalement par poser problème, sur base du code que je viens de présenter avec le switch, en cas de suppression du premier élément de la liste ;)

Ok, super c'est genial!! Meci!! Le clone, cé une super idée, surtout pour ce que je veux faire apres....

Mais il reste un petit soucis!

Si dans ma boucle, j'ajoute un objet, la taille du container va s'agrandir, et ma boucle va finir par tester l'objet que je viens d'ajouter , qui a son tour va se repliquer, et ainsi de suite.. Donc je me demandais si c'etait logique ce qui suit. CAD, de definir l'intervalle à tester dans la boucle. Comme ça, ce qu'on ajoute ne sera pas tester.

listLife<LIFE>::iterator it= listLife.begin();
listLife<LIFE>::iterator itEnd = listLife.end();

while ( tps <tpsMax)
{
while ( it != itEnd)
{
estatus status= it->live();
switch(status)
{
case JE_VIS:it++; //incremente pour la boucle
break;

case JE_ME_REPLIQUE:
listLife.push_back(it->clone()); it++; //incremente pour la boucle
break:
case JE_MEURE:
it = listLife.erase(it); //it renvoie au suivant, donc pas d'incrementation
itEnd --; //par contre, on reduit la taille de la liste à tester.
break;
}
}
tps++;
itEnd =listLife.end() ; // Fin du tour de liste, on redifini la fin!
}

En fait, il faut savoir que, bien souvent conteneur.end() renvoie... tout simplement NULL, et que tu ne peux donc pas prendre un itérateur renvoyé par end en espérant qu'un élément inséré apres ne soit pas testé.

De plus, l'élément cloné ayant été traité, il ne le sera plus pour le parcours en cours de la liste.

Par contre, ce qui est vrai, c'est que le clone sera susceptible d'etre testé...

Mais, il suffit de mettre son status à JE_VIS, et il sera alors traité comme n'importe quel élément vivant, ne prévoyant pas de se dupliquer...

Si, à tout hasard, un élément qui vient juste de naitre, venait à devoir effectuer une (série d') action(s) spéciale(s), il te suffirait de rajouter un status possible: JE_NAIS qui représentera ce status spécial ;)

Ok je vais faire comme ca ! Merci!!

Mais le problème, c'est que tu effectues quand même du temps de calcul pour rien.

Ce que tu pourrais faire, c'est quand tu crées une nouvelle entité, tu la mets dans une liste temporaire.

Quand toutes les entités ont été créées, il te suffira de faire un list::splice() pour déplacer les éléments de la liste temporaire vers la vraie grosse liste. La complexité de splice() est en temps constant, c'est quelque chose de très rapide, une histoire de 2 ou 3 pointeurs en interne.

Citation:

---

Envoyé par HanLee

Mais le problème, c'est que tu effectues quand même du temps de calcul pour rien.

Ce que tu pourrais faire, c'est quand tu crées une nouvelle entité, tu la mets dans une liste temporaire.

Quand toutes les entités ont été créées, il te suffira de faire un list::splice() pour déplacer les éléments de la liste temporaire vers la vraie grosse liste. La complexité de splice() est en temps constant, c'est quelque chose de très rapide, une histoire de 2 ou 3 pointeurs en interne.

---

Avant que le nombre de test à effectuer sur les nouveaux éléments ne provoque réellement une augmentation significative du temps de calcul, il faudrait vraiment que les insertions soient réellement nombreuses...

Visiblement, il s'agit plus d'un programme de simulation que d'un programme pour lequel les performances sont réellment importantes et doivent se rapprocher du temps réel...

Je me pose donc réellement la question de la nécessité d'essayer d'éviter cette perte de temps.

Ben, pour moi, plus que de l'optimisation, c'était plus le souci d'être conforme et direct par rapport à ce qu'il voulait faire.

Pour moi, quand je vois ça, c'est comme si quand je te demande d'écrire un algorithme qui rajoute un élément en tête d'une liste, tu vas écrire un algorithme qui rajoute 2 fois cet élément, puis retire un élément, si tu vois ce que j'veux dire :)

L'algorithme n'est pas le même, il n'est pas significativement plus lent, mais le résultat est le même. Mais conceptuellement, j'aurais trouvé ça gênant de programmer un push_front() comme ça ;) .

En parlant d'optimisation, on ne fera qu'au plus gagner un facteur 2 en vitesse ici (pour moi, c'est négligeable ; en général les programmes de simulation de vie artificielle, s'il y a des interactions, on peut facilement se retrouver avec des algorithmes quadratiques).

Si j'ai voulu faire ça, c'est juste que ça ne demande que 2 lignes de code en plus, et de modifier une autre, c'est tout ;) .

L'astuce, c'est que, l'un dans l'autre, je ne suis absolument pas persuadé que cela te prenne plus de temps de tester les éléments fraichements rajoutés que de les recopier d'une liste temporaire vers la liste principale...

De plus, on ne dispose malgré tout pas forcément de toutes les informations utiles, et, comme je l'ai déjà dit, rien n'empeche d'envisager qu'un élément à peine né ne doive déjà subir une action bien précise qui nécessiterait une valeur qui n'est pas disponible au travers de l'élément cloné...

D'ou la proposition de rajouter un status "JE_NAIS" ;)

list::splice() déplace les éléments, sans recopie ;) .

http://www.cppreference.com/cpplist/splice.html

Citation:

---

De plus, on ne dispose malgré tout pas forcément de toutes les informations utiles, et, comme je l'ai déjà dit, rien n'empeche d'envisager qu'un élément à peine né ne doive déjà subir une action bien précise qui nécessiterait une valeur qui n'est pas disponible au travers de l'élément cloné...

D'ou la proposition de rajouter un status "JE_NAIS" ;)

---

Ben, ça dépend de ce qu'il voulait, pour l'instant il a l'air de se contenter de ne rien faire d'autre à part leur donner la vie :zoubi:

Bein, a vrait dire... Je compte mettre dans la liste, plus de 100 000 entité....
Donc je vais qd meme voir du coté de splice!!

LOL.....SUPER la methode de la table temporaire!

J'ai crée sur mon portable, 15 millions d'entité vivanteen moins de 4 sec!