Suppression d'un element dans une liste

Version imprimable

1 pièce(s) jointe(s)

Bonjour,

J'ai un problême avec les std::list du c++ lors de la suppression d'un élément de la liste.

Mon but est de pouvoir insérer/supprimer/rechercher rapidement **toutes** les entrées avec des coordonnées (i,j) spécifiques

J'arrive bien à retrouver ces entrées sans pb avec une boucle qui itère du premier au dernier élément de la liste, mais lorsque je supprime cette entrée, le programme plante juste après :(

=> je me retrouve donc pour l'instant bloqué à devoir mettre un break immédiatement après la première suppression afin que ce petit programme de test ne plante pas ... alors que je voudrais qu'il continue l'itération afin de supprimer les autres occurences qui correspondent à ce type d'entrée :(

Le morceau de code qui crée pb est celui-ci :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 void Destroy(int i, int j) { std::list<entry_t>::iterator iter; int step = 0; printf("Destroy entries (%d,%d,xxxx)\n", i, j); for( iter = LIS.begin() ; iter != LIS.end() ; ++iter, ++step) { printf(" Test entry %d (%d,%d,%d) with (%d,%d,xxxx): ", step, iter->i, iter->j, iter->coef, i, j ); if( (iter->i == i) && (iter->j == j) ) { LIS.erase(iter); printf("erased \n"); break; } else { printf("no erased \n"); } } }
=> si je supprime le break après le LIS.erase(iter), ça plante

Qu'est-ce qui ne va pas dans ce boût de code ?

J'ai mis en pièce jointe un exemple de code qui crée le pb

Sous Linux, ça se compile via g++ test.cpp -o test -std=c++11
(j'y ai mis le -std=c++11 car sinon g++ me sort tout un tas de warnings)

@+
Yannoo

25/11/2012, 04h23
yannoo95170
J'ai touvé la solution sur http://stackoverflow.com/questions/5...om-an-stl-list

Il suffit tout simplement de post-incrémenter la valeur de l'itérateur au niveau du erase() ...
Code:

1 2 LIS.erase(iter);
devient
Code:

1 2 LIS.erase(iter++);
@+
Yannoo
25/11/2012, 12h50
koala01
Salut,

En fait, en créant le foncteur "qui va bien" sous la forme de
Code:

1 2 3 4 5 6 7 8 9 10 struct MyEqual { MyEqual(int i, int j):i(x),j(y){} int i; int j; bool operator()(entry_t const & e1) const { return e1.i==i && e1.j == i; } };
tu pourrais t'en sortir avec un ligne de code aussi simple que
Code:

1 2 3 4 5 #include <algorithm> // pour avoir std::remove_if void destroy(int i, int j) { LIS.erase(std::remove_if(LIS.begin(),LIS.end(),MyEqual(i,j)),LIS.end() ); }
std::remove_if va en effet déplacer tous les éléments qui correspondent au prédicat indiqué à la fin de la collection dont ils font partie et renvoyer un itérateur le premier élément déplacé.

Tu peux donc décider de supprimer en une seule fois tous les éléments qui existent entre l'itérateur renvoyé par std::remove_if et la fin de ta collection avec la fonction membre erase de celle-ci ;)

Cette manière de travailler est souvent préférable pour la raison bien simple qu'elle est applicable à tous types de collection, et que certaines (les vecteurs, par exemple) invalident les itérateurs qui suivent celui sur l'élément supprimé.

Ainsi, si tu en viens un jour à décider de remplacer (sans doute pour une raison de performances au niveau de l'accès aux éléments) ta liste par un vecteur, le code utilisé n'aura même pas besoin d'être modifié, et tu pourras te contenter de remplacer ton std::list<entry_t> LIS; par un std::vector<entry_t> LIS; sans avoir à craindre de "tout casser" ;)

Au passage: contrairement au C, lorsque tu définis une structure, une classe, une énumération ou une union en C++, tu crées automatiquement le type associé, et tu n'as donc pas besoin d'utiliser typedef.

Ton code
Code:

1 2 3 4 5 typedef struct { int i, j; int coef; }entry_t;
qui dénote clairement une habitude issue du C serait avantageusement remplacé par
Code:

1 2 3 4 5 struct entry_t { int i, j; int coef; };
J'en profite d'ailleurs pour rappeler une fois de plus que, bien que C++ ne renie pas ses origines et sa filiation avec C, il s'agit bel et bien de deux langages totalement différents, et qu'il est vraiment conseillé, dans un premier temps, d'éviter toutes les techniques issues du C, car elles sont bien souvent beaucoup moins sécurisantes que les techniques équivalentes qui existent en C++ ;)

1 pièce(s) jointe(s)

Merci, Koala01

Je viens de faire les modifs que tu viens de m'indiquer mais ça ne marche pas :(

Ca c'est trivialement passé pour la modif de la fonction Destroy() que j'ai remplacé par le simple

Code:

1
2
3
4
5
6
 
void Destroy1(int i, int j)
{
    printf("Destroy entries (%d,%d,xxxx)\n", i, j);
    LIS.erase(std::remove_if(LIS.begin(),LIS.end(),MyEqual(i,j)),LIS.end() );
}

Pour la structure MyEqual, j'ai dû y faire une très légère modif pour que ça se compile
(MyEqual(int x, int y):i(x),j(y){} à la place de MyEqual(int i, int j):i(x),j(y){} car bien sûr le compilo se plaignait de ne pas trouver x et y + j'ai mis le constructeur juste après les variables i et j pour "que ça fasse plus beau")

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
struct MyEqual
{
    int i;
    int j;
 
    MyEqual(int x, int y):i(x),j(y){}
 
    bool operator()(entry_t const & e1) const
    {
        return e1.i==i && e1.j == i;
    }
};

Par contre, j'ai des tas d'erreurs de la part du compilo si je ne met pas les typedef devant la definition de structure entry_t :(

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
struct
{
	int i, j;
	int coef;
}entry_t;
 
yannoo@Ubuntoo:~/Wavelet$ make
g++ test.cpp -o test -std=c++11 -Wwrite-strings
 
test.cpp:19:21: erreur: ‘entry_t’ is not a type
test.cpp: In member function ‘bool MyEqual::operator()(const int&) const’:
test.cpp:21:19: erreur: request for member ‘i’ in ‘e1’, which is of non-class type ‘const int’
test.cpp:21:30: erreur: request for member ‘j’ in ‘e1’, which is of non-class type ‘const int’
test.cpp: At global scope:
test.cpp:26:18: erreur: type/value mismatch at argument 1 in template parameter list for ‘template<class _Tp, class _Alloc> class std::list’
test.cpp:26:18: erreur:   expected a type, got ‘entry_t’
test.cpp:26:18: erreur: patron de l'argument 2 est invalide
test.cpp:26:23: erreur: invalid type in declaration before ‘;’ token
test.cpp:27:18: erreur: type/value mismatch at argument 1 in template parameter list for ‘template<class _Tp, class _Alloc> class std::list’
test.cpp:27:18: erreur:   expected a type, got ‘entry_t’
test.cpp:27:18: erreur: patron de l'argument 2 est invalide
test.cpp:27:23: erreur: invalid type in declaration before ‘;’ token
test.cpp:28:18: erreur: type/value mismatch at argument 1 in template parameter list for ‘template<class _Tp, class _Alloc> class std::list’
test.cpp:28:18: erreur:   expected a type, got ‘entry_t’
test.cpp:28:18: erreur: patron de l'argument 2 est invalide
test.cpp:28:23: erreur: invalid type in declaration before ‘;’ token
test.cpp: In function ‘void Test0()’:
test.cpp:34:6: erreur: request for member ‘push_back’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:36:6: erreur: request for member ‘push_front’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:38:6: erreur: request for member ‘insert’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:38:19: erreur: request for member ‘begin’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:40:6: erreur: request for member ‘push_back’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:42:6: erreur: request for member ‘push_back’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:44:6: erreur: request for member ‘insert’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:44:19: erreur: request for member ‘end’ in ‘LIS’, which is of non-class type ‘int’
test.cpp: In function ‘void PrintLIS()’:
test.cpp:50:19: erreur: type/value mismatch at argument 1 in template parameter list for ‘template<class _Tp, class _Alloc> class std::list’
test.cpp:50:19: erreur:   expected a type, got ‘entry_t’
test.cpp:50:19: erreur: patron de l'argument 2 est invalide
test.cpp:50:31: erreur: expected initializer before ‘iter’
test.cpp:53:10: erreur: ‘iter’ was not declared in this scope
test.cpp:53:21: erreur: request for member ‘begin’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:53:43: erreur: request for member ‘end’ in ‘LIS’, which is of non-class type ‘int’
test.cpp: In function ‘void Destroy0(int, int)’:
test.cpp:62:19: erreur: type/value mismatch at argument 1 in template parameter list for ‘template<class _Tp, class _Alloc> class std::list’
test.cpp:62:19: erreur:   expected a type, got ‘entry_t’
test.cpp:62:19: erreur: patron de l'argument 2 est invalide
test.cpp:62:31: erreur: expected initializer before ‘iter’
test.cpp:66:10: erreur: ‘iter’ was not declared in this scope
test.cpp:66:21: erreur: request for member ‘begin’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:66:43: erreur: request for member ‘end’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:71:8: erreur: request for member ‘erase’ in ‘LIS’, which is of non-class type ‘int’
test.cpp: In function ‘void Destroy(int, int)’:
test.cpp:84:9: erreur: request for member ‘erase’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:84:34: erreur: request for member ‘begin’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:84:46: erreur: request for member ‘end’ in ‘LIS’, which is of non-class type ‘int’
test.cpp:84:70: erreur: request for member ‘end’ in ‘LIS’, which is of non-class type ‘int’

=> si je rajoute le typedef devant, aucun pb de compil

Code:

1
2
3
4
5
6
7
8
9
10
 
typedef struct
{
	int i, j;
	int coef;
}entry_t;
 
yannoo@Ubuntoo:~/Wavelet$ make
g++ test.cpp -o test -std=c++11 -Wwrite-strings
yannoo@Ubuntoo:~/Wavelet$

Mais ça ne marche pô pour autant :(

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
30
31
32
 
yannoo@Ubuntoo:~/Wavelet$ make
g++ test.cpp -o test -std=c++11 -Wwrite-strings
yannoo@Ubuntoo:~/Wavelet$ ./test
 
PrintLIS() : 
1 2 3 
4 5 6 
7 8 9 
10 11 12 
4 5 6 
13 14 15 
 
Destroy entries (4,5,xxxx)
 
PrintLIS() : 
1 2 3 
4 5 6 
7 8 9 
10 11 12 
4 5 6 
13 14 15 
 
Destroy entries (4,5,xxxx)
 
PrintLIS() : 
1 2 3 
4 5 6 
7 8 9 
10 11 12 
4 5 6 
13 14 15

A la place du code original qui detruisait bien les entrées commencant par (4,5,qqchose)

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
30
31
32
33
34
35
36
 
yannoo@Ubuntoo:~/Wavelet$ make
g++ test.cpp -o test -std=c++11 -Wwrite-strings
yannoo@Ubuntoo:~/Wavelet$ ./test
 
PrintLIS() : 
1 2 3 
4 5 6 
7 8 9 
10 11 12 
4 5 6 
13 14 15 
 
Destroy entries (4,5,xxxx)
  Test entry 0 (1,2,3) with (4,5,xxxx): no erased 
  Test entry 1 (4,5,6) with (4,5,xxxx): erased 
  Test entry 2 (10,11,12) with (4,5,xxxx): no erased 
  Test entry 3 (4,5,6) with (4,5,xxxx): erased 
 
PrintLIS() : 
1 2 3 
7 8 9 
10 11 12 
13 14 15 
 
Destroy entries (4,5,xxxx)
  Test entry 0 (1,2,3) with (4,5,xxxx): no erased 
  Test entry 1 (7,8,9) with (4,5,xxxx): no erased 
  Test entry 2 (10,11,12) with (4,5,xxxx): no erased 
  Test entry 3 (13,14,15) with (4,5,xxxx): no erased 
 
PrintLIS() : 
1 2 3 
7 8 9 
10 11 12 
13 14 15

C'est normal que ça plante ton itérateur pointe sur element que tu supprime
et la méthode erase retourne l'élément suivant

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
 
void Destroy(int i, int j)
{
	std::list<entry_t>::iterator iter  = LIS.begin();
	int step = 0;
 
	printf("Destroy entries (%d,%d,xxxx)\n", i, j);
   	while (iter != LIS.end())
   	{
		printf("  Test entry %d (%d,%d,%d) with (%d,%d,xxxx): ",  step, iter->i, iter->j, iter->coef, i, j );	
		if( (iter->i == i) && (iter->j == j) )
		{
			iter = LIS.erase(iter);
			printf("erased \n");
		}
		else
		{
                        ++iter, ++step
			printf("no erased \n");
		}
   	}
}

essaye ça, ça devrait marcher

25/11/2012, 17h29
yannoo95170

1 pièce(s) jointe(s)

Là, ça marche :)
(rien qu'un petit ; à rajouter à la ligne "++iter, ++step")

A noter c'est bien le type de truc que préconisait le lien que j'ai donné avant
(en gros, remplacer le for par un while et faire le ++iter à l'intérieur de la boucle si l'élément n'est pas trouvé, pour que ce soit compatible avec tout)

M'enfin ce n'était qu'une tout petite brique que je voulais utiliser dans un bien plus gros projet qui est une implementation de EWT/SPIHT
(c'est une "compression progressive d' ondeletes par arbres de zeros")
[c'est carrément buggé pour l'instant mais j'espère que j'arriverais assez vite à implémenter ça correctement]

@+
Yannoo
25/11/2012, 17h38
jouana

Ouais enfaîte c'est plus à cause des traitement dans ta boucle

quand tu erase un élément c'est normal que ça plante vu que tu incrémente sur un item supprimé.

Ce qui faut retenir c'est que quand tu supprime sur un iterator, tu récupère la valeur de retour qui est l'élément suivant d'ou le pb avec le for vu que tu incrémente ton iterateur 2 fois quand supprime un élément.

bonne soirée
25/11/2012, 17h43
yannoo95170

Merci, Jouana

"Ce qui faut retenir c'est que quand tu supprime sur un iterator, tu récupère la valeur de retour qui est l'élément suivant d'ou le pb avec le for vu que tu incrémente ton iterateur 2 fois quand supprime un élément."

=> expliqué comme ça, c'est maintenant clair comme de l'eau de roche pour moi :)

@+
Yannoo
25/11/2012, 18h51
koala01
Citation:
Envoyé par yannoo95170

Merci, Koala01

Je viens de faire les modifs que tu viens de m'indiquer mais ça ne marche pas :(

Ca c'est trivialement passé pour la modif de la fonction Destroy() que j'ai remplacé par le simple

Code:

1 2 3 4 5 6 void Destroy1(int i, int j) { printf("Destroy entries (%d,%d,xxxx)\n", i, j); LIS.erase(std::remove_if(LIS.begin(),LIS.end(),MyEqual(i,j)),LIS.end() ); }

Pour la structure MyEqual, j'ai dû y faire une très légère modif pour que ça se compile
(MyEqual(int x, int y):i(x),j(y){} à la place de MyEqual(int i, int j):i(x),j(y){} car bien sûr le compilo se plaignait de ne pas trouver x et y + j'ai mis le constructeur juste après les variables i et j pour "que ça fasse plus beau")

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 struct MyEqual { int i; int j; MyEqual(int x, int y):i(x),j(y){} bool operator()(entry_t const & e1) const { return e1.i==i && e1.j == i; } };
Au temps pour moi, une mauvaise vérification d'un copier coller foireux :aie:

Par contre, j'ai des tas d'erreurs de la part du compilo si je ne met pas les typedef devant la definition de structure entry_t :(
Code:

1 2 3 4 5 6 struct { int i, j; int coef; }entry_t;
Mais regarde le code que je te donne pour entry_t!!!
ce n'est ni
Code:

1 2 3 4 5 typedef struct { int i, j; int coef; }entry_t;
ni
Code:

1 2 3 4 5 6 struct { int i, j; int coef; }entry_t;
mais
Code:

1 2 3 4 5 6 struct entry_t { int i, j; int coef; };
Tu verras, ca va tout de suite beaucoup mieux pour la compilation ;)
Les autres erreurs de compilation se résoudront d'elles-même, car il est logique, à partir du moment où le compilateur a généré une erreur "parce qu'il ne reconnaissait pas la déclaration d'un type" qu'il refuse systématiquement tout ce qui peut avoir trait à ce type ;)

Autrement, je t'assure que cela devrait fonctionner ;)

Pour le reste, je t'assure bel et bien qu'un code du genre de

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <iostream>
#include <list>
#include <algorithm>
struct MyStruct
{
    MyStruct(int x, int y):x(x),y(y){}
    int x;
    int y;
};
struct MyFunctor
{
    MyFunctor(int i, int j):i(i), j(j){}
    int i;
    int j;
    bool operator()(MyStruct const & s) const
    {
        return s.x == i && s.y == j;
    }
};
int main()
{
    std::list<MyStruct> list;
    for(int x=0;x<3;++x)
    {
        for(int i = 0; i<4; ++i)
        {
            for(int j = 0 ; j <4; ++j)
            {
                list.push_back(MyStruct(i+1,j+1));
            }
        }
    }
    std::cout<<"number of element after filling "<<list.size()<<std::endl;
    for(auto const & it : list)
        std::cout<<it.x<<" "<<it.y<<std::endl;
    std::cout<<"removing elements with i = 3 and j  = 2"<<std::endl;
    list.erase(std::remove_if(list.begin(),list.end(),MyFunctor(3,2)),list.end());
    std::cout<<"after erasure, left  "<<list.size()
             <<" in the list"<<std::endl;
    for(auto const & it : list)
        std::cout<<it.x<<" "<<it.y<<std::endl;
}

qui remplis la liste avec trois occurences de chaque valeur (ma structure MyStruct correspondant à ta structure entry_t, au coefficient près ;) compile parfaitement et fournit le résultat auquel on est en droit de s'attendre, à savoir

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
number of element after filling 48
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
removing elements with i = 3 and j  = 2
after erasure, left  45 in the list
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 3
3 4
4 1
4 2
4 3
4 4
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 3
3 4
4 1
4 2
4 3
4 4
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 3
3 4
4 1
4 2
4 3
4 4

dans lequel on se rend effectivement compte que les trois éléments dont les valeurs étaient 3 pour i et 2 pour j ont bel et bien été retirés ;)

1 pièce(s) jointe(s)

Effectivement, ça passe de suite beaucoup mieux en prefixant le nom de la structure plutôt qu'en là postfixant :)

J'en ai même profité pour rajouter une option permettant de fixer le nombre maximum d'occurences à supprimer
[via la fonction DestroyFirstEntries(int i, int j, int nitems) qui sert de support pour les fonctions DestroyFirstEntry(int i, j) et DestroyEntries(i,j) ]
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 30 31 32 33 34 void DestroyFirstEntries(int i, int j, int nitems) { std::list<entry_t>::iterator iter = LIS.begin(); int deleted = 0; printf("Destroy first %d entries (%d,%d,xxxx)\n", nitems, i, j); while (iter != LIS.end()) { printf(" Test entry %d (%d,%d,%d) with (%d,%d,xxxx): ", nitems, iter->i, iter->j, iter->coef, i, j ); if( (iter->i == i) && (iter->j == j) ) { iter = LIS.erase(iter); printf("erased \n"); if( ++deleted == nitems) return; } else { ++iter; printf("no erased \n"); } } } void DestroyFirstEntry(int i, int j) { DestroyFirstEntries(i,j,1); } void DestroyEntries(int i, int j, int nentries=1000) { DestroyFirstEntries(i,j, nentries); }
J'ai aussi une fonction DestroyAllsEntries(int i, int j) qui utilise le std::remove_if pour voir la différence
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 struct EntryFunctor { int i, j; EntryFunctor(int i, int j):i(i), j(j){} bool operator()(entry_t const &e) const { printf("Test entry (%d,%d,%d) with (%d,%d,xxxx) : ", e.i, e.j, e.coef, i, j); if( e.i == i && e.j == j) { printf("erased \n"); return true; } else { printf("no erased \n"); return false; } } }; void DestroyAllsEntries(int i, int j) { printf("Destroy all entries (%d,%d,xxxx)\n", i, j); std::remove_if(LIS.begin(),LIS.end(),EntryFunctor(i,j)); }
=> c'est clair que c'est bien plus générique et que ça peut faire gagner pas mal de lignes de code car pas besoin de gérer les itérations en dur dans le code
==> même si au début les STL paraissent assez compliqué à utliser et qu'on a l'impression que ça fait plutôt rajouter pleins de class/struct qu'autre chose, au final c'est vraiment très fort ces STL ...

@+
Yannoo