Tri des membres d'une classe (std::vector ou std::list)

Salut à tous !
je suis actuellement en train de programmer un petit jeu sans prétentions en C++/SDL

Malheureusement je suis confronté à un problème sur lequel je bloque grave ...

J'ai créé un systeme qui charge une carte et l'affiche à l'écran.
Sur cette carte se balladent actuellement quelques personnages controlés
par ordinateur. Jusque là tout va bien, surtout qu'ils tiennent compte
des collisions etc ... ;)

Ces persos sont une instansation de la classe "Npc" que j'ai codé :

 				Npc *m_npc; 		

 				m_npc = new Npc[MAXNPCS]; 		

ainsi je créé un tableau de X Npc et j'accède à chaque Npc grâce à son
indice : m_npc[0] pour le 1er Npc par exemple.

Mon problème intervient lorsque je dessine mes persos à l'écran;
en effet, je les dessine un par un avec une boucle for :

 				for(int i = 0; i < MAXNPCS; i++) m_npc[i].draw(); 		

Ce qui fait que le perso avec le plus haut indice est toujours repeint en dernier.

Ceci pose problème lorsque certains persos repeints ont une coordonnée
Y inférieure aux autres Npcs repeints précédemment.

En fait cela créé un problème de chevauchement (les jambes d'un perso + haut sur l'écran vont
être peintent sur la tête d'un perso qui est plus bas si ce dernier a un indice inférieur dans le tableau m_npc).

Je voudrai donc trier mon tableau m_npc par la valeur de sa propriété "m_inf.m_y"
(m_npc[x].m_inf.m_y donc, qui est un entier qui représente la position Y du npc X. PS : m_inf est une structure)
pour qu'ainsi m_npc[0] ai le m_inf.m_y le plus petit et m_npc[n] ai le m_inf.m_y le plus grand.

Je me doute qu'il serait dangereux de toucher directement à la structure du tableau m_npc, j'ai
donc pensé à utiliser une std::list ou un std::vector qui contiendrai le pointeur de chaque indice
du tableau et à trier cette liste (ou ce vector) grâce à sa fonction sort().
Pour repeindre ensuite, il me suffirait de parcourir la liste (ou le vector), et d'utiliser chaque
pointeur qu'il contient pour repeindre mes persos.

L'autre problème c'est que je n'y connais absolument rien en list ou vector

Pourriez vous m'aider svp ?

Y a sûrement sur ce site des dizaines de codes avec des listes chaînées, tu pourrais en récupérer un.

juju12 > Oui il y en a surement, j'ai même avec moi un bouquin de prog sur le C++ mais franchement j'y comprend rien ... pour utiliser un vector avec des type de style float, int, etc ... c'est sans problème (et encore, en excluant les foncteurs pour les tris, j'ai pas encore bien compris ça non plus...) mais pour faire des vector de classe et pouvoir utiliser chaque objet de mon vector comme si il était dans un tableau j'ai pas encore trouvé :(

luthor > je pensais plutot à conserver mon tableau et à utiliser un vector pour stocker les adresses de chaque pointeur vers les indices du tableau. Ceci dit il est vrai que si utiliser un vector est exactement la même chose qu'utiliser un tableau je pourrais peut être passer directement par un vector pour initialiser et gérer tous mes objets npc ... Mais en fait je me suis basé sur ce topic :
http://www.cppfrance.com/infomsg_TRIER-STD-MAP_552236.aspx
sur lequel j'ai cru comprendre que l'auteur utilisait un tableau + un vector à la fin... maintenant je peux très bien me tromper :/

Comment faire pour allouer dynamiquement un vector ? c'est avec "new" aussi ? style

std::vector<Npc*> m_npc;

m_npc = new std::vector<Npc>[MAXNPCS]

?
Pour ensuite utiliser la fonction init() par exemple d'un npc d'indice N il me suffit de faire

m_npc[n].init()

?

Et enfin, pour trier ce vector par m_inf.m_y croissant, quel foncteur dois-je appliquer ?

PS : Le tri va s'effectuer à chaque déplacement des npc (c'est à dire assez souvent vu qu'il y a 60 frames par seconde et qu'ils bougent quasi tout le temps ...), est-ce une bonne méthode ou ça risque de trop ramer comme ça ?

Merci !!

C'est débile d'allouer un std::vector. J'ai l'impression que tu comprends pas bien ce que c'est :)

std::vector<Npc*> m_npc; // <= la tu as un tableau dynamique, qui prend la taille qu'il faut

Npc * unObject = new Npc();
m_npc.push_back(unObject);

m_npc[0]->init();

Mais un conseil, que je te conseil de suivre: "au lieu de errer dans les entrailles austères de la STL". Prend deux minutes pour lire: ca:http://cpp.developpez.com/cours/stl/ (juste la partie qui t'intéresse, cad III. Les classes conteneur de la STL)

Pour le tri, il y a une méthode efficace, mais seulement si tu tolères quelques bugs de la durée d'une frame. Quand tu affiches tous les objets de ton vecteur a chaque frame, tu regardes si l'objet suivant dans le tableau est devant ou derrière l'objet actuel. Si l'objet suivant doit etre dessiné avant l'objet actuel, tu remplaces inverse les deux pointeurs du tableau. De cette facon, le coup du tri est quasiment nul mais génère quelques anomalies mineurs qui durent une frame.

Comme tu n'as pas l'air habitué à la STL, je vais utiliser des indices pour que tu comprennes. (en pratique, mieux vaut utiliser les std::vector<Npc*>::iterator. Tu comprendras apres avoir lu le site).

for(int k = 0 ; k < m_npc.size() ; ++k)
{
    if ((k < m_npc.size() - 1) && (m_npc[k]->DistanceALaCamera() > m_npc[k+1]->DistanceALaCamera()))
    {
        Npc * ptr = m_npc[k];
        m_npc[k] = m_npc[k+1];
        m_npc[k+1] = ptr;
    }

    m_npc[k]->draw();
}

De cette facon, le tri va se faire progressivement. Par exemple, si tu as 60 objets superposés, il faudra dans le pire des cas, 60 frames (cad 1seconde) pour que tous les objets soient triés.

Bon ben j'ai, grâce à votre aide, résolu mon problème.
Voilà la solution pour les intéréssés :

Il faut déclarer les Npcs non pas dans un tableau mais dans un vector :

vector<Npc *> m_npc;

Pour initialiser chaque Npc, je fait :

for(int i = 0; i < MAXNPCS; i++)

{

    Npc *npc_m = new Npc();

    m_npc.push_back(npc_m);

    m_npc[i]->initNpc();

}

Ensuite, dans la classe Npc, j'ai ajouté cette fonction membre :

déclaration dans npc.h:

static bool estDerriere(Npc *npc1, Npc *npc2);

dans npc.cpp :

bool Npc::estDerriere(Npc *npc1, Npc *npc2)

{

    return npc1->m_inf.m_y < npc2->m_inf.m_y;

}

Enfin, avant de dessiner les Npc à l'écran, j'appel :

sort(m_npc.begin(), m_npc.end(), Npc::estDerriere);

Ce qui à pour effet de trier mon vecteur !

Par contre j'ai une dernière question. Quand je fait un push_back(npc_m), l'objet pointé par npc_m (donc une instance de Npc) est "recopié" dans le vecteur ou celui-ci contient juste l'adresse du pointeur ? Parce que je voudrais savoir si il faut à un moment ou un autre que je vide npc_m avec un delete.

Voilà, merci à tous :)