Question sur std::vector

Version imprimable

Bonjour,

Dans le cadre du developpement d'un jeu, je dois gérer l'ajout ou suppréssion de bombes d'un plateau de jeu (classe Bombe).
Dans une classe Jeu, j'ai un vecteur de bombe sous la forme:
vector<Bombe*> bombe;

Quand j'ajoute une bombe, je fais:
Bombe *bombe = new Bombe( /*...arguments...*/ );
this->bombe.push_back(bombe);

Je dois supprimer les bombes du vecteur quand la méthode bool est_terminee() de la classe Bombe retourne true.
Pour cela, j'ai tappé ce code:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void Jeu :: nettoyer_bombe() { vector<Bombe*>::iterator ite = this->bombe.begin(); do { if( (*ite)->est_terminee() ) { delete (*ite); this->bombe.erase(ite); } else ite++; } while(ite != this->bombe.end()); }
Est ce que mon code est correct? Pas de fuite mémoire?
Dois-je faire le delete ou alors erase() s'en charge ?

Merci de m'éclairer sur mon code !

23/06/2007, 15h16
Laurent Gomila

- Ce devrait être un while {} plûtôt qu'un do {} while (si le vecteur est vide --> crash sur la première itération)
- L'itérateur n'est pas mis à jour lorsque tu appelles erase ; il faut le récupérer en retour de la fonction (ite = erase(...)) ; tout ça est expliqué dans la FAQ
- Les suppressions aléatoires sur un vecteur sont très lentes, une liste ne serait pas plus adaptée dans ton cas ? Sinon, si l'ordre n'est pas important, tu peux également interchanger l'élément à supprimer avec le dernier, la suppression du dernier élément étant elle très rapide.
- delete est bien entendu obligatoire, le vecteur ne peut pas prendre la responsabilité de détruire les éléments, puisque tu pourrais très bien stocker des instances non allouées dynamiquement, ou dont la durée de vie doit excéder celle du conteneur.
- Si tu es en forme, tu peux essayer de transformer ça avec un petit std::remove_if + le foncteur qui va bien à base de std::mem_fun ;)
23/06/2007, 16h39
FabaCoeur

Tout d'abord, merci beaucoup pour toutes tes réponses qui sont toujours précice et pertinente.

Citation:

Ce devrait être un while {} plûtôt qu'un do {} while (si le vecteur est vide --> crash sur la première itération)

A la base j'étais parti sur un for ce qui semblait logique, mais j'avais peut que si je supprime un élément avec l'itération je passe au suivant, mais je viens de me rendre compte que avec un while normal ca marche aussi bien...!

Citation:

L'itérateur n'est pas mis à jour lorsque tu appelles erase ; il faut le récupérer en retour de la fonction (ite = erase(...)) ; tout ça est expliqué dans la FAQ

Hum j'avais lu dans une doc en anglais de la STL que l'itérateur était mis à jour automatiquement, j'ai du avoir un petit souci de langue. Je vais aller voir la FAQ sur ce point.

Citation:

Les suppressions aléatoires sur un vecteur sont très lentes, une liste ne serait pas plus adaptée dans ton cas ? Sinon, si l'ordre n'est pas important, tu peux également interchanger l'élément à supprimer avec le dernier, la suppression du dernier élément étant elle très rapide.

Oui une liste serait aussi adapté, surtout que l'ordre des éléments n'a pas d'importance. J'ai opté pour le vecteur car quand on écrit des boucles on peut utiliser les indices (dans un souci d'écriture donc), mais bon je me rends compte que la liste est ici plus appropriée.

Citation:

Si tu es en forme, tu peux essayer de transformer ça avec un petit std::remove_if + le foncteur qui va bien à base de std::mem_fun

J'ai vu un script dans lequel on utilise un remove_if, c'est vrai que ca semble la meilleur utilisation mais je n'avais vraiment pas très bien compris le principe. Je pense me tourner vers cette solution car c'est quand même bien plus propre.

Bon je viens d'essayer de faire un test avec remove_if(), ca semble fonctionner mais étant donné que le code que je fais sert juste à nettoyer la mémoire, je n'ai pas trop moyen de savoir si ca fonctionne correctement!

D'autant plus que j'ai copié/coller du code en le modifiant, mais je n'ai vraiment pas compris comment ça fontionne au final.

Voila le code que j'ai fait.
Dans un premier temps j'ai créer une classe/fonction pour pouvoir utiliser le remove_if(). J'ai préférer la mettre dans la classe Bombe pour plus de propretée:

bombe.h
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /* ... En tête ... */ class Bombe { public: /* ... Méthodes ... */ // Classe pour nettoyage des bombe struct EstTerminee : public std::unary_function<Bombe*,bool> { bool operator() (Bombe *bombe) { return bombe->est_terminee(); } }; private: /* ... Suite... */ };
Et ensuite j'appelle remove_if() dans la méthode de Jeu:

jeu.cpp
Code:

1 2 3 4 5 6 // Supprime les bombes ayant terminé leur explosion void Jeu :: nettoyer_bombe() { this->bombe.remove_if( Bombe::EstTerminee() ); }
Voila ca compile bien mais je suis à des années lumières de savoir si ce que j'ai fait fonctionne :oops:

PS: J'ai bien entendu transformé le vecteur en liste.

Citation:

Code:

this->bombe.remove_if( Bombe::EstTerminee() );

this->bombe est toujours un std::vector ? Parce que std::vector::remove_if, ça n'existe pas à ma connaissance (par contre ça existe pour std::list).

Ensuite ça fonctionne, seulement il manque la destruction des éléments via delete.

Dans ton cas il faudrait le faire en plusieurs étapes :
Code:

1 2 3 4 5 6 7 8 9 // On déplace les éléments à supprimer vers la fin du conteneur std::vector<Bombe*>::iterator begin = std::remove_if(bombe.begin(), bombe.end(), std::mem_fun(&Bombe::est_terminee)); // On détruit tous les éléments déplacés for (std::vector<Bombe*>::iterator it = begin; it != bombe.end(); ++it) delete *it; // On retire physiquement du conteneur les éléments supprimés bombe.erase(begin, bombe.end());
Pour ce qui est de std::mem_fun, ça permet simplement que les éléments soient testés en appelant elt->fonction() plutôt que fonction(elt).

Bon c'est pas forcément plus court que la première solution (ça ne prendrait qu'une ligne s'il n'y avait pas le delete à faire), donc à toi de voir quelle écriture te paraît plus intuitive.

Citation:

this->bombe est toujours un std::vector ? Parce que std::vector::remove_if, ça n'existe pas à ma connaissance (par contre ça existe pour std::list).

Oui je l'avais mis à la fin de mon post dans le PS ^^

Pour ce qui est de la suite, j'avais carrément oublié de faire les deletes...!
J'ai regardé ce bout de code:
Code:

1 2 3 4 5 6 7 8 9 // On déplace les éléments à supprimer vers la fin du conteneur std::vector<Bombe*>::iterator begin = std::remove_if(bombe.begin(), bombe.end(), std::mem_fun(&Bombe::est_terminee)); // On détruit tous les éléments déplacés for (std::vector<Bombe*>::iterator it = begin; it != bombe.end(); ++it) delete *it; // On retire physiquement du conteneur les éléments supprimés bombe.erase(begin, bombe.end());
Mais je n'ai vraiment pas compris (erf).
En quoi la première ligne met-elle les élément à la fin ?
Qu'est ce que "std::mem_fun(&Bombe::est_terminee)" ?
Je comprends la dedans qu'on passe en argument un pointeur sur le fonction, c'est tout.

Merci de m'éclairer un peu plus :)

Citation:

En quoi la première ligne met-elle les élément à la fin ?

Ben c'est comme ça c'est tout :aie:
La fonction std::remove_if place à la fin du conteneur tous les éléments qui vérifient le prédicat. En général on ne l'utilise pas seule, on la couple à la fonction qui va physiquement supprimer ces éléments du conteneur (erase).
Et elle renvoie bien sûr un itérateur vers le premier élément déplacé, pour que l'on puisse les retrouver.

Citation:

Qu'est ce que "std::mem_fun(&Bombe::est_terminee)" ?

std::remove_if attend un foncteur qui prend en paramètre un Bombe* et renvoie un booléen. Or nous c'est presque exactement ce que nous avons avec Bombe::est_terminee, sauf que comme c'est une fonction membre, la bombe n'est pas passée directement en paramètre. std::mem_fun permet de transformer une fonction membre qui s'écrirait elt->fonction() en quelque chose de plus compatible avec std::remove_if, à savoir fonction(elt).

Si ça peut t'aider à mieux visualiser, voilà comment on pourrait écrire std::mem_fun (c'est plus compliqué mais là j'ai simplifié pour le cas qui nous intéresse) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 template <typename T> struct mem_fun_t { typedef bool (T::*Function)(); mem_fun_t(Function F) : Func(F) { } bool operator()(T& Obj) { return (Obj.*Func)(); } Function Func; }; template <typename T> mem_fun_t<T> mem_fun(bool (T::*Function)()) { return mem_fun_t<T>(Function); }

Citation:

Envoyé par Laurent Gomila

Ben c'est comme ça c'est tout :aie:
La fonction std::remove_if place à la fin du conteneur tous les éléments qui vérifient le prédicat. En général on ne l'utilise pas seule, on la couple à la fonction qui va physiquement supprimer ces éléments du conteneur (erase).
Et elle renvoie bien sûr un itérateur vers le premier élément déplacé, pour que l'on puisse les retrouver.

Arf ok, pour une fois je trouve pas la STL très logique !
Pour moi "remove_if" ca semble logique que ca supprime (remove) si (if) la condition est vérifiée...!

Citation:

Envoyé par Laurent Gomila

std::remove_if attend un foncteur qui prend en paramètre un Bombe* et renvoie un booléen. Or nous c'est presque exactement ce que nous avons avec Bombe::est_terminee, sauf que comme c'est une fonction membre, la bombe n'est pas passée directement en paramètre. std::mem_fun permet de transformer une fonction membre qui s'écrirait elt->fonction() en quelque chose de plus compatible avec std::remove_if, à savoir fonction(elt).

Ok, sur ce point je pense avoir tout compris !
Citation:
Envoyé par Laurent Gomila
Si ça peut t'aider à mieux visualiser, voilà comment on pourrait écrire std::mem_fun (c'est plus compliqué mais là j'ai simplifié pour le cas qui nous intéresse) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 template <typename T> struct mem_fun_t { typedef bool (T::*Function)(); mem_fun_t(Function F) : Func(F) { } bool operator()(T& Obj) { return (Obj.*Func)(); } Function Func; }; template <typename T> mem_fun_t<T> mem_fun(bool (T::*Function)()) { return mem_fun_t<T>(Function); }
Bon bah le "si ca peut t'aider" est de trop :aie:
Je n'ai strictement rien compris :aie:
Cependant je vais en rester sur la première partie de l'explication, car je ne pense pas avoir les connaissances suffisantes pour comprendre le code.

Encore une fois merci beaucoup pour ton aide :king:

Erf j'ai mis super longtemps à débugger à cause d'une erreur bête...
Il ne faut bien entendu pas mettre un itérateur de vector mais de list désormais !
Voila le code au final:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using namespace std;
 
#include <algorithm>
#include <functional>
#include <list>
#include "jeu.h"
 
 
/** ... Implémentation de Jeu ... **/
 
 
// Supprime les bombes ayant terminé leur explosion
void Jeu :: nettoyer_bombe() {
 
	/* Merci à Laurent Gomila de Developpez.net pour ce bout de code */
 
	// Déclaration d'itérateurs
	list<Bombe*>::iterator debut, ite;
 
	// On déplace les éléments à supprimer vers la fin du conteneur
	debut = remove_if(this->bombe.begin(), this->bombe.end(), mem_fun(&Bombe::est_terminee));
 
	// On détruit tous les éléments déplacés à la fin
	for(ite = debut; ite != this->bombe.end(); ite++)
		delete (*ite);
 
	// On retire physiquement du conteneur les éléments supprimés
	this->bombe.erase(debut, this->bombe.end());
}

24/06/2007, 17h49
Alp

Pour le coup des Bombe*, pourquoi ne pas utiliser des smart pointers ? Ca t'empêche d'avoir des problèmes de fuites, déjà.

Ensuite cherche toujours si un algo stl ne convient pas pour ce que tu veux faire, ils sont en général assez optimisés ... ;)
24/06/2007, 18h11
FabaCoeur

Heuuuu... c'est quoi un smart pointer ?
Puis utiliser un algo de la STL, c'est bien ce que l'on fait puisqu'on utilise remove_if, non ?
24/06/2007, 18h22
Alp

Oui oui, et je te conseille justement de généraliser cette démarche(regarder si un algo stl ne correspond pas à ton besoin) pour chaque fois où tu pourrais en avoir besoin.
Pour les smart pointers : http://c.developpez.com/faq/cpp/inde...S_intelligents