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 !

[hpfx]

pour résumer, en espérant que cela servent a d'autres, voici donc deux implémentations (a priori sans bug) qui gèrent la suppression d'éléments dans un vecteur.

Methode de la FAQ :

Code :

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

1
2
3
4
5
6
7
8
 
/* une fonction dans laquelle on peut faire un test pour savoir 
si on efface l'objet ou pas */
bool AEffacer(Item* ptr) {
   return ptr->a_retirer(); // ou tout autre test...
}
// le code :
vItem.erase(std::remove_if(vItem.begin(), vItem.end(), AEffacer), vItem.end());

rien a dire, super propre.

Autre Méthode :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
/* efficace pour retirer quelques items d'un vecteur
 sans tout décaller! */
template <typename T> 
void SupprItem(T& v) 
{ 	for(int j=v.size()-1;j>=0;j--)
		if(v[j]->a_retirer()) // ou tout autre test
		{	swap(v[j], v[v.size()-1]);
			v.pop_back();
		}
}
// le code
SupprItem(vItem);

bien que la version FAQ soit niquel, j'ai un petit faible pour l'autre qui permet (en plus de ne pas tout decaller a chaques suppressions) de recuperer l'item du pop_back si on veux en faire qqchose... (comme un delete par exemple).
Mais son gros defaut, est que le vecteur est désordonné apres.
stdout :

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

donc voilà quoi.
ca depend du contexte...

Merci.

[loufoque]

Tu n'as pas compris du tout comment s'utilise iter_swap. Il est évident que tu n'as pas lu la doc.

[hpfx]

Tu n'as pas compris du tout comment s'utilise iter_swap. Il est évident que tu n'as pas lu la doc.

ben non, j'ai pas de "DOC" sur la question, google ne m'a pas beaucoups aidé en fait (*), j'ai essayé (remplacé swap par iter_swap), ca a compilé et même donnée le resultat excompté.
dans VC6, quand je fais "go to definition of iter_swap" ben ca ne menne a rien.
dans la FAQ je n'ai pas vu ou on parlais de de iter_swap.
(j'avoue qu'apres ca je ne suis pas allé plus loin : ca compile, rien dans la faq, pas de ressources en francais, aucun resultat dans la recherche sur le forum, rien de special avec VC6, pas d'exemple ou de lien dans ton post, ca semble marcher, j'y ai cru, mea culpa.)

Mais, si tu veux bien me donner un lien vers "une doc" ça serait super. (edit : ou carrément la syntaxe... la bonne ligne, là c'est le rêve )

merci.

(*) avec google, http://wwwasd.web.cern.ch/wwwasd/lhc...r/ite_4254.htm donne une syntaxe similaire a ce que j'utilise.

[Jean-Marc.Bourguet]

http://wwwasd.web.cern.ch/wwwasd/lhc...r/ite_4254.htm donne une syntaxe similaire a ce que j'utilise.

On passe des itérateurs à iter_swap, pas les éléments. Comme tes éléments sont des pointeurs ça à l'air de passer mais tu fais en fait

Code :

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

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

[hpfx]

On passe des itérateurs à iter_swap, pas les éléments. Comme tes éléments sont des pointeurs ça à l'air de passer mais tu fais en fait

Code :

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

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

donc iter_swap(truc,truc) est equivalent à swap(*truc,*truc)...
Ok, bon.. si je comprends bien (pas taper si je me plante, hein) c'est un peu le même cas que dans mon 1er post (methode "curieuse")... il faut que je remplace &v[i] par un iterateur : v.begin()+i
donc si j'ai tout bon, le code est :

Code :

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

1
2
3
4
5
6
7
void SupprItem(T& v) 
{ 	for(int j=v.size()-1;j>=0;j--)
		if(v[j]->a_retirer()) // ou tout autre test
		{	iter_swap(v.begin()+j, v.end()-1);
			v.pop_back();
		}
}

c'est bon ?

[Mat007]

Salut,

Je ramène juste ma fraise pour dire que

Code :

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

v[v.size()-1]

s'écrit plus simplement

Code :

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

v.back()

MAT.

[hpfx]

Re bonjour,
me revoilà juste pour conclure le sujet, j'ai donc retenu 3 bouts de code pour effectuer cette operation de suppression d'elements de vecteur.
et j'ai effectué un benchmark
voilà le code :

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
29
30
 
#include <vector>
#include <algorithm>
using namespace std;
//-- classe de test :
class Item
{
public :
	int a;
	Item(int x):a(x) { } // constructeur
	const bool a_retirer() const {return a%10==0; } // test bidon pour l'exemple.
};
//-- fonction pour l'un des algo :
 bool AEffacer(Item* ptr)  {
   return ptr->a_retirer(); // ou tout autre test...
}
//-- le test :
void test1()
{
	vector<Item*> vItem;
	for (int i=0;i<1000000;i++) vItem.push_back (new Item(i));
	Uint32 t=SDL_GetTicks();
 
/*
 * ici mettre l'un des 3 algo ...
 */
 
fprintf(stdout,"TEST1 : %ld\n",SDL_GetTicks()-t);
exit(0);
}

et voilà les nominés :
algo avec erase

Code :

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

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

algo avec "iter_swap"

Code :

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

1
2
3
4
5
6
for(int j=vItem.size()-1;j>=0;j--)
 if(vItem[j]->a_retirer())
 {
   iter_swap(vItem.begin()+j,vItem.end()-1);
   vItem.pop_back();
 }

et enfin, algo avec "swap"

Code :

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

1
2
3
4
5
6
for(int j=vItem.size()-1;j>=0;j--)
 if(vItem[j]->a_retirer())
 {
   swap(vItem[j], vItem.back());
   vItem.pop_back();
 }

et d'apres mes bench (depends du compilo, chez moi VC6) le winer is : "iter_swap".
a titre indicatif, iter_swap donne 27,6 (milisecondes)
swap donne 28,5
et remove donne 30,4
a noter qu'en debug l'ordre d'arrivé n'est pas le même. test effectué sur 10 lancés.

Merci pour tous vos conseils.

PS : oui je sais je ne désalloue rien du tout à la fin (ni le vecteur ni les objets) c'était juste pour faire un test hein.

PPS: bien que très classe, la solution avec "erase" me gêne un peut car je ne peux pas ajouter un "delete vItem.back();" comme je peux le faire avec les 2 autre solutions

[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]

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());

[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]

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.