Discussion :

[hpfx]

bonjour,
j'aimerai faire le point sur les différentes méthodes de suppression d'éléments de vector, car j'en ai trouvés plusieurs, et j'aimerai etudier avec vous ces methodes.

voici déjà un bout de code de base :

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
21
22
23
24
25
26
27
28
#include <vector>
#include <iostream>
using namespace std;
 
class Item
{public :
	int a;
	Item(int x):a(x) { } // constructeur
	bool a_retirer() {return a%2==0; } // test bidon pour l'exemple.
};
 
void afficher(vector<Item*> &v)
{ 	cout<<v.size()<<" items = ";
	for (vector<Item*>::const_iterator it = v.begin(); it != v.end(); ++it) cout<<(*it)->a<<", ";
	cout<<endl;
}
 
int main(int argc, char* argv[])
{
	vector<Item*> vItem;
	for (int i=0;i<10;i++)
		vItem.push_back (new Item(i));
 
	afficher(vItem); // afficher le vecteur avant.
/*-- ici mettre le code de suppression --*/
	afficher(vItem); // afficher le vecteur apres.
	return 0;
}

voilà maintenant quelques bouts de code pour supprimer un ou des elements de vecteur (note : je ne gere pas les delete dans cet exemple)

* la premiere methode c'est une methode que j'ai trouvé moi-même par tatonement (j'avais pas internet en vacances!)

Code :

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

1
2
3
/* -- methode "curieuse" -- */
	for(int j=0;j<vItem.size();j++)
		if(vItem[j]->a_retirer()) vItem.erase(&vItem[j]);

J'en suis pas super fier, je ne comprends pas pourquoi il faut que je mette l'adresse de mon objet, mais ca a l'aire de marcher (mon compilo : VC6)

* la deuxieme methode, je l'ai adapté de ce que j'ai trouvé sur internet aujoutd'hui, je la trouve pas mal...

Code :

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

1
2
3
/* -- methode "avec begin" -- */
	for(int j=0;j<vItem.size();j++)
		if(vItem[j]->a_retirer()) vItem.erase(vItem.begin()+j);

ca me plait car plus de "&" dans le erase.

* la troisieme methode, trouvé sur internet ce jour aussi...

Code :

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

1
2
3
/* -- methode "avec iterator" -- */
	for (vector<Item*>::iterator it = vItem.begin(); it != vItem.end(); ++it)
		if((*it)->a_retirer()) 	vItem.erase(it);

Attention, il ne faut surtout pas utiliser cette methode, elle semble marcher, mais si vous supprimer le dernier element, alors ca plante (a cause du test du for it!=vItem.end() ) essayer avec un vecteur de 11 elements au lieu de 10, vous verrez!

* la quatrieme methode, est la methode que je n'ai pas reussit a implementer, et pourtant c'est celle de la FAQ d'ici. je me dis qu'elle dois être super geniale, mais elle est super pas facile a comprendre.

Code :

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

1
2
3
/* -- methode "Laurent Gomila :predicat, foncteurs et cie" -- */
// http://c.developpez.com/faq/cpp/?page=STL#STL_suppression_elements
// j'ai pas compris comment l'implementer.

bon voilà, dans ma lecture j'ai aussi lu que c'est pas super efficasse de supprimer un element au milieu d'un vecteur (dans mon cas réel, j'aurai un vecteur d'une centaine d'elem, et de temps en temps j'en supprimerai un au milieu) je me suis dis : je vais utiliser vItem.pop_back et me debrouiller pour deplacer l'element a supprimer vers la fin. j'ai pensé a swap (pour intervertir mes deux elements) mais en fait swap echange entre deux vecteurs, c'est pas la bonne methode.

mes questions :
- savez-vous s'il existe une methode (simple) pour intervertir deux elements de vecteur (element indexé j et celui indexé vItem.size()-1)
- pourquoi ma methode "curieuse" marche ?
- quelle est ma meilleur methode selon vous ?
- savez-vous comment implementer la derniere methode (celle de la faq de Laurent Gomila) ?

Merci.

note : voici stdout.

Code :

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

1
2
10 items = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
5 items = 1, 3, 5, 7, 9,

note2 : en fait il faudrait que je parcours les for a l'envers (de vItem.size()-1 à 0) pour traiter la suppression de deux elements consecutifs. bon, mais mis a part ce bug, vous en pensez quoi ?

[ZaaN]

mes questions :
- savez-vous s'il existe une methode (simple) pour intervertir deux elements de vecteur (element indexé j et celui indexé vItem.size()-1)
pas a ma connaissance mais facile a faire
- pourquoi ma methode "curieuse" marche ?
l'operatuer [] retourne une reference
- quelle est ma meilleur methode selon vous ?
euh.... en terme de rapidité ?

[hpfx]

Merci,

mes questions :
- savez-vous s'il existe une methode (simple) pour intervertir deux elements de vecteur (element indexé j et celui indexé vItem.size()-1)
pas a ma connaissance mais facile a faire

J'avoue être sacrement interressé, t'as un debut de piste ?

- quelle est ma meilleur methode selon vous ?
euh.... en terme de rapidité ?

ben, globalement, la plus presentable, la plus portable, la plus propre, et pourquoi pas la plus rapide aussi... oui pourquoi pas

[Jean-Marc.Bourguet]

mes questions :
- savez-vous s'il existe une methode (simple) pour intervertir deux elements de vecteur (element indexé j et celui indexé vItem.size()-1)

swap(v[j], v[v.size()-1]);

- pourquoi ma methode "curieuse" marche ?

Parce que tu as par hasard une implementation qui utilise un T* comme iterateur sur un vector<T>.

- quelle est ma meilleur methode selon vous ?

Celle de la FAQ

- savez-vous comment implementer la derniere methode (celle de la faq de Laurent Gomila) ?

oui.

Code :

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

1
2
3
4
5
6
7
8
 
bool AEffacer(Item* ptr) {
   return ptr->a_retirer();
}
...
v.erase(std::remove_if(v.begin(), v.end(), AEffacer), v.end());
//
v.erase(std::remove_if(v.begin(), v.end(), std::mem_fun_t<bool, Item>(&Item::a_retirer)), v.end());

(On peut savoir pourquoi Item::a_retirer n'est pas const?)

[hpfx]

swap(v[j], v[v.size()-1]);

Ho merci, je n'y étais pas arrivé !!!
Maintenant, voici (enfin) la 5eme et derniere methode :

Code :

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

1
2
3
4
5
6
7
 
/* -- methode "a décallage" -- */
	for(int j=vItem.size()-1;j>=0;j--)
		if(vItem[j]->a_retirer())
		{	swap(vItem[j], vItem[vItem.size()-1]);
			vItem.pop_back();
		}

elle marche super.
c'est vrai que les elements a l'interieur du vecteur se trouve désordonné, mais pour moi celà n'a pas d'importance.

Parce que tu as par hasard une implementation qui utilise un T* comme iterateur sur un vector<T>.

La meilleur methode :

Celle de la FAQ

Je n'en doute pas une seconde. (elle est surtout elegante)
mais dans ce cas precit, est-ce que la derniere solution (avec le swap) n'est pas préferable ? (on evite de décaller tout le vecteur a partir de l'element a supprimer)

Code :

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

1
2
3
4
5
6
7
8
 
bool AEffacer(Item* ptr) {
   return ptr->a_retirer();
}
...
v.erase(std::remove_if(v.begin(), v.end(), AEffacer), v.end());
//
v.erase(std::remove_if(v.begin(), v.end(), std::mem_fun_t<bool, Item>(&Item::a_retirer)), v.end());

Merci beacoups, c'est super... je vais essayer de bien la comprendre maintenant.
EDIT : Heu... "Error => 'remove_if' : is not a member of 'std'" ???

(On peut savoir pourquoi Item::a_retirer n'est pas const?)

ha oui.. c'est une bonne question, en fait je suis un peu faché avec les const, c'est une lacune de ma parts (ca faisait des années que je n'avais pas fait de C/C++, alors j'ai quelque peu oublié les subtilité des const du coups je suis perdu dans la syntaxe quand il faut que je mette un const)

[Jean-Marc.Bourguet]

mais dans ce cas precit, est-ce que la derniere solution (avec le swap) n'est pas préferable ?

Si l'ordre n'a pas d'importance, oui.

Merci beacoups, c'est super... je vais essayer de bien la comprendre maintenant.
EDIT : Heu... "Error => 'remove_if' : is not a member of 'std'" ???

Code :

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

1
2
3
 
#include <algorithm>
#include <functional>

[loufoque]

Il vaut mieux utiliser iter_swap pour échanger de place deux éléments d'un conteneur.
Ou swap_ranges s'il y en a plusieurs à échanger.

[hpfx]

Il vaut mieux utiliser iter_swap pour échanger de place deux éléments d'un conteneur.
Ou swap_ranges s'il y en a plusieurs à échanger.

super !

Code :

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

1
2
3
4
5
6
7
8
 
/* -- methode "iter_swap" -- */
 
	for(int j=vItem.size()-1;j>=0;j--)
		if(vItem[j]->a_retirer())
		{	iter_swap(vItem[j], vItem[vItem.size()-1]);
			vItem.pop_back();
		}

sinon Merci aussi a Jean-Marc

Code :

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

vItem.erase(std::remove_if(vItem.begin(), vItem.end(), AEffacer), vItem.end());

Pour l'instant je n'ai pris que la premiere ligne, apparement avec la deuxieme ligne on peut s'exonerer de la fonction AEffacer.

Merci a vous tous.
C'est excellent, je n'ai que l'embarras du choix maintenant !

[yan]

Code :

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

1
2
3
4
5
6
 
bool AEffacer(Item* ptr) {
   return ptr->a_retirer();
}
...
v.erase(std::remove_if(v.begin(), v.end(), AEffacer), v.end());

(On peut savoir pourquoi Item::a_retirer n'est pas const?)

ATTENTION ne pas faire cela avec des conteneur de pointeur car :
1 - les delete ne sont pas fait
2 - des fuites mémoires sont généré par remove_if

Avec des pointeurs, il faut faire en deux temps et utiliser std::partition

Code C++ :

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
bool NePasEffacer(Item* ptr)
{
   return  !ptr->a_retirer();
}

void delete_element(Item* ptr) 
{
   delete ptr;
}

std::vector<Item*>::iterator ittmp;
// regroupe les éléments à effacer à la fin
ittmp = std::partition(v.begin(), v.end(), NePasEffacer);
// détruit les éléments 
std::for_each(ittmp,v.end(),&delete_element);
// enlève les éléments 
v.erase(ittmp, v.end());

[hpfx]

ATTENTION ne pas faire cela avec des conteneur de pointeur car :
1 - les delete ne sont pas fait
2 - des fuites mémoires sont généré par remove_if

pour le "1" c'est juste, j'en ai fait une remaque dans mon post en fin de 1ere page. (je viens de comprendre que tu reponds au fur et a mesure, tu n'as donc pas encore vu ce post )

Mais il se peut que celà ne soit pas redibitoire, ca peut être un comportement voulu sans qu'il y ai de fuite memoire !
Par exemple, il se trouve que je gère un vecteur d'element a afficher (vDisp) ainsi qu'un vecteur d'element a deplacer (vDepl)...
ainsi qu'un vecteur de tous les elements (vElements)
de temps en temps je lance un "garbage collector" sur mes deux premiers vecteurs, par exemple si un element restera fixe et bien je le supprime du vecteur vDepl (sans pour autant le supprimer du vecteur vDisp par exemple)
pour ces deux opérations je ne fais pas de delete. (je le ferai en fin de tableau sur le vecteur général qui contiens tous les objets)
voilà c'était juste un exemple : il n'y a pas de fuite memoire si j'utilise erase pour vDisp et vDepl.

par contre pour le "2" (fuite memoire sur remove_if) je ne savais pas.
c'est quoi ? un bug dans le remove_if ? ou alors c'est des fuites du au fait que l'on ne fais pas de delete ?

Merci pour le coup du partition... tres interressant.

[yan]

pour le "1" c'est juste, j'en ai fait une remaque dans mon post en fin de 1ere page. (je viens de comprendre que tu reponds au fur et a mesure, tu n'as donc pas encore vu ce post )

Mais il se peut que celà ne soit pas redibitoire, ca peut être un comportement voulu sans qu'il y ai de fuite memoire !
Par exemple, il se trouve que je gère un vecteur d'element a afficher (vDisp) ainsi qu'un vecteur d'element a deplacer (vDepl)...
ainsi qu'un vecteur de tous les elements (vElements)
de temps en temps je lance un "garbage collector" sur mes deux premiers vecteurs, par exemple si un element restera fixe et bien je le supprime du vecteur vDepl (sans pour autant le supprimer du vecteur vDisp par exemple)
pour ces deux opérations je ne fais pas de delete. (je le ferai en fin de tableau sur le vecteur général qui contiens tous les objets)
voilà c'était juste un exemple : il n'y a pas de fuite memoire si j'utilise erase pour vDisp et vDepl.

Si tu ne veut pas les detruire alors y as pas problème . Mais faut mieux precisser

par contre pour le "2" (fuite memoire sur remove_if) je ne savais pas.
c'est quoi ? un bug dans le remove_if ? ou alors c'est des fuites du au fait que l'on ne fais pas de delete ?

Disons qu'il génère une fuite memoire car on va perdre des pointeurs.
- remove_if va mettre par un egale (si néssésaire bien sur) les élément un aprés l'autre qui ne doivent pas être enlevé. Y aura donc des doublons entre la zone à sauvegarder et la zone à enlever, ainsi que des éléments disparue

- partion va swapper les éléments de tel sorte que les éléments en tête valide la condition.

[hpfx]

Disons qu'il génère une fuite memoire car on va perdre des pointeurs.
- remove_if va mettre par un egale (si néssésaire bien sur) les élément un aprés l'autre qui ne doivent pas être enlevé. Y aura donc des doublons entre la zone à sauvegarder et la zone à enlever, ainsi que des éléments disparue

Tres interressant, ca serait pas mal peut être de mettre ce genre de piège dans la FAQ ? (je ne sais pas si d'autre sont intéressés, mais je sais que cette question de suppression d'éléments est souvent abordé,et que la methode erase est proposé dans la FAQ)

en tout cas, merci.

[yan]

bonjour, il y as des choses fauses

Code :

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

1
2
3
 
	for(int j=0;j<vItem.size();j++)
		if(vItem[j]->a_retirer()) vItem.erase(vItem.begin()+j);

tu as de forte chance doublier de éléments

Code :

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

1
2
3
4
5
6
7
8
9
 
//correction
for(int j=0;j<vItem.size();)
  {
    if(vItem[j]->a_retirer()) 
        vItem.erase(vItem.begin()+j);
   else
        ++j;
}

Code :

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

1
2
3
 
for (vector<Item*>::iterator it = vItem.begin(); it != vItem.end(); ++it)
	if((*it)->a_retirer()) 	vItem.erase(it);

pareil

Code :

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

1
2
3
4
5
6
7
8
9
 
//correction
for (vector<Item*>::iterator it = vItem.begin(); it != vItem.end(); )
  {
  if((*it)->a_retirer()) 	
        it =vItem.erase(it);
  else
    ++it;
  }

[hpfx]

bonjour, il y as des choses fauses

Code :

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

1
2
3
 
	for(int j=0;j<vItem.size();j++)
		if(vItem[j]->a_retirer()) vItem.erase(vItem.begin()+j);

tu as de forte chance doublier de éléments

Code :

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

1
2
3
4
5
6
7
8
9
 
//correction
for(int j=0;j<vItem.size();)
  {
    if(vItem[j]->a_retirer()) 
        vItem.erase(vItem.begin()+j);
   else
        ++j;
}

Merci mais justement, maintenant (voir mon post precedant) je travaille en décroissant

Code :

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

for(int j=vItem.size()-1;j>=0;j--)

ca me permet de ne plus avoir ce problème et aussi d'éviter de recalculer size() a chaque fois (optimisation).

les bout de cote que j'ai mis au debut (dans mes premiers post) etaient volontairement simplistes, je l'avais precisé dans mon premier post :

note2 : en fait il faudrait que je parcours les for a l'envers (de vItem.size()-1 à 0) pour traiter la suppression de deux elements consecutifs. bon, mais mis a part ce bug, vous en pensez quoi ?

en tout cas merci pour ton aide, et si t'as d'autre remarques ou suggestion je suis n'hésite surtout pas.

D'ailleurs ton code est interressant, travailler en decoirssant empeche de passer ma variable de compteur en unsigned (bon moi ca ne me gene pas)

[yan]

Et avec un vecteur de pointeur

Code :

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

1
2
3
4
5
6
7
8
9
10
11
for(int j=0;j<vItem.size();)
  {
    if(vItem[j]->a_retirer()) 
        {
        delete vItem[j];
        vItem.erase(vItem.begin()+j);
        }
   else
         ++j;
}

Code :

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

1
2
3
4
5
6
7
8
9
10
11
for (vector<Item*>::iterator it = vItem.begin(); it != vItem.end(); )
  {
  if((*it)->a_retirer()) 	
       {
        delete *it;
        it =vItem.erase(it);
        }
  else
    ++it;
  }

et ton code

Code :

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

1
2
3
4
5
6
7
8
9
10
for(int j=vItem.size()-1;j>=0;--j)
  {
    if(vItem[j]->a_retirer()) 
        {
        delete vItem[j];
        vItem.erase(vItem.begin()+j);
        }

}

[hpfx]

Et avec un vecteur de pointeur

Code :

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

1
2
3
4
5
6
7
8
9
10
11
for(int j=0;j<vItem.size();)
  {
    if(vItem[j]->a_retirer()) 
        {
        delete vItem[j];
        vItem.erase(vItem.begin()+j);
        }
   else
         ++j;
}

...

oui oui, je sais, tu as tout à fait raison.
Je n'ai pas axé mes posts la dessus, je ne voulais traiter que de la suppression d'éléments de vecteur. (mais c'est sur qu'en général on peu avoir besoin de supprimer les objets pointés aussi)
D'ailleur, la methode s'appelle "a_retirer" non pas "a_detruire" bon je chipote là