replication d'objet dans un container STL

**istdasklar** · 13/05/2007, 02h17

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

**JolyLoic** · 13/05/2007, 02h56

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

**koala01** · 13/05/2007, 03h13

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**istdasklar** · 13/05/2007, 12h22

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!
}

**koala01** · 13/05/2007, 22h09

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

**istdasklar** · 14/05/2007, 11h51

Ok je vais faire comme ca ! Merci!!

**HanLee** · 14/05/2007, 17h31

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.

**koala01** · 14/05/2007, 18h29

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.

**HanLee** · 14/05/2007, 22h50

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

.

**koala01** · 15/05/2007, 01h32

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"

**HanLee** · 15/05/2007, 01h41

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

.

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

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