Discussion :

[StingerBell]

Bonjour,

j'ai une erreur sur le code suivant :

Code :

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

1
2
3
4
5
6
7
8
 
for(Object::iterator it =  list.begin(); it !=  list.end(); it++)
            {
                if ((*it)->getValue()==testValue)
                {
                it = list.erase(it);
                }
            }

voila apres le list.erase cela fait n'importe quoi et l'iterateur continue apres la fin de la liste. J'ai regarde partout et j'ai pas du tout trouve la solution du probleme :

- D'abord j'utilisais des std::vector plutot que des std::list puisque j'ai cru comprendre que l'ajout/suppression d'element est plus efficace
- Puis avec les std::vector la fonction .erase a l'air de "casser" l'iterateur et j'ai cru comprendre que la structure de liste corrigeait cela.
- j'avais au depart juste list.erase(it) au lieu de it = list.erase(it); car j'ai cru comprendre qu'il faut cette structure pour allouer l'iterateur au prochain element
- j'ai aussi essayer d'ajouter une ligne it = list.end() a la fin pour sortir de la boucle

Mais malgres tout cela, j'ai toujours un probleme. La boucle ne s'arrete pas a la fin de ma liste comme elle devrait s'arreter !

Merci d'avance pour votre aide

[ternel]

Et si tu utilisais <algorithm>? il existe ce qu'on appelle l'idiome erase-remove:

Code :

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

1
2
#include <algorithm>
    liste.erase(std::remove(liste.begin(), liste.end(), testvalue), liste.end());

(exemple tiré de http://en.cppreference.com/w/cpp/alg...preference.com

Edit:
En lisant la page attentivement, il y a liste::remove

le code devient simplement liste.remove(testvalue);

[StingerBell]

merci pour ta réponse,

en fait la condition ne porte pas sur la valeur de l'objet de la liste en lui même mais sur un argument de cette classe.

Comment puis-je adapter std::remove pour que cela marche ? J'ai essaye ainsi en utilisant remove_if :

Code :

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

list.remove_if(getValue()==testValue);

mais cela ne semble pas marcher ?

Sinon en utilisant mon code d'origine avec un iterateur il n'y a pas moyen de le faire marcher par hasard ? Cela m'arrangerait bien de garder cette forme pour mon code dans son ensemble ...

Merci !

[ternel]

La fonction attend soit une valeur, soit une fonction (enfin, un pointeur de fonction ou une lambda)
regarde bien les liens que j'ai donné.

Par ailleurs, on doit avoir quelque chose dans la faq.

[jblecanard]

Attention, le choix de la liste est rarement une bonne idée : le temps de parcours que tu dépenses pour trouver l'élément à supprimer domine le gain réalisé sur la suppression. Voir:

[StingerBell]

dsl mais j'ai encore un probleme . Je suis le template de l'example pour creer la fonction mais il n'accepte pas le passage de "b" en parametre pour ma fonction (dans l'example il utilise une valeur en dur). Comment faire pour passant des arguments a la fonction test ?

Code :

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

1
2
3
 
   int b = valueTest;
    list.remove_if([](Object* a){ return (a->getValue() == b); });

vraiment merci pour ton aide !

Attention, le choix de la liste est rarement une bonne idée : le temps de parcours que tu dépenses pour trouver l'élément à supprimer domine le gain réalisé sur la suppression. Voir:

Dans ce cas la, peux-tu peut-etre me dire quel est le probleme avec mon code original et comment je pourrais le regler ?

[foetus]

Code :

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

1
2
3
4
5
6
7
8
 
for(Object::iterator it =  list.begin(); it !=  list.end(); it++)
            {
                if ((*it)->getValue()==testValue)
                {
                it = list.erase(it);
                }
            }

Object::iterator


Pourquoi Object?

[StingerBell]

en faite Object désigne juste une liste d'éléments de ma classe, donc un truc de genre :

Code :

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

typedef std::list"Class" = Object

[foetus]

Ton histoire me semble bizarre, j'ai donc sorti mon gcc favori
Et il y a une erreur simple: lorsque tu supprimes, ton itérateur est incrémenté 2 fois (1 fois par la méthode erase 1 autre fois par la boucle)

Voici mon 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
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
#include<vector>
#include<iostream>
 
using namespace std;
 
class A {
public:
 
    A(int init_a = 0): a(init_a) {}
 
    int get_a() const { return a; }
 
 
private:
 
    int a;
};
 
#define PRINT \
    cout << endl << endl; \
     \
    for(it = vec.begin(); it != vec.end(); ++it) { \
        cout << it->get_a() << endl; \
    }
 
 
int main()
{
    vector<A> vec;
    vec.push_back( A(4) );
    vec.push_back( A(6) );
    vec.push_back( A(4) );
    vec.push_back( A(5) );
    vec.push_back( A(4) );
    vec.push_back( A(4) );
    vec.push_back( A(3) );
    vec.push_back( A(2) );
    vec.push_back( A(4) );
    vec.push_back( A(4) );
    vec.push_back( A(4) );
    vec.push_back( A(1) );
 
    vector<A>::iterator it;
 
    PRINT
 
//  Remove all 4
//  Dirty -> voir le post de @jblecanard en dessous :-)
//  for(it = vec.begin(); it != vec.end(); it++) {
//      if (it->get_a() == 4) {
//          it = vec.erase(it);
//          it--;
//      }
//  }
 
    it = vec.begin();
    while(it != vec.end()) {
        if (it->get_a() == 4) {
            it = vec.erase(it);
        } else {
            ++it;
        }
    }
 
    PRINT
 
    return 0;
}

Édit: Merci @jblecanard pour cette correction .

Et effectivement j'ai oublié de préciser qu'en utilisant soit std::vector soit std::list, cela fonctionne

[jblecanard]

C'est exact foetus, cela dit, c'est dangereux de décrémenter l'itérateur pour le réincrémenter juste après. Si le premier élément rencontre la condition, la décrémentation ne passera pas. De même, si tu utilises une forward_list, elle ne passe pas non plus. Rien ne vaut un bon vieux while.

Code :

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

1
2
3
4
5
6
7
it = vec.begin();
while( it != vec.end()) {
  if ((*it).get_a() == 4)
    it = vec.erase(it);
  else
    ++it;
}

@StingerBell ce code a été fait sur un vector mais il fonctionne aussi sur une liste.

[JolyLoic]

Faire une série d'erase est en O(n²), là où un O(n) est possible avec erase-remove.

[StingerBell]

merci pour vos reponses,

Faire une série d'erase est en O(n²), là où un O(n) est possible avec erase-remove.

je comprends pas bien pourquoi un erase serait en n^2 alors qu'un erase remove serait en n. Basiquement ce sont les memes operations qui sont faites non ? Pour un vecteur on retire un element puis on deplace ce qui suit et pour une liste on parcourt la liste jusque la position pour retirer un element et on change les pointeurs non ?

[jblecanard]

Voir ceci et ceci. Ce n'est pas valable si tu utilises la fonction membre remove de la liste, puisqu'on ne parle pas du même algo.

[JolyLoic]

je comprends pas bien pourquoi un erase serait en n^2 alors qu'un erase remove serait en n. Basiquement ce sont les memes operations qui sont faites non ? Pour un vecteur on retire un element puis on deplace ce qui suit et pour une liste on parcourt la liste jusque la position pour retirer un element et on change les pointeurs non ?

Si on enlève un élément unique, la complexité sera en O(n) dans les deux cas. La différence vient du fait que si on enlève plusieurs éléments, avec un erase dans une boucle, on répète plusieurs fois le fait d'enlever un élément (donc O(n²)), alors qu'avec erase/remove, on parcours une seule fois la liste en décalant au fur et à mesure du bon nombre les éléments :
- avant le premier élément à supprimer, on ne décale pas
- à partir du premier et jusqu'au second, on décale d'une case vers la gauche les éléments
- à partir du second et jusqu'au trosiième, on décale de deux cases vers la gauche les éléments
- ...

Donc en une seule passe, on a supprimé tous les éléments (d'où O(n))

[jblecanard]

Je ne vois pas trop en quoi ce raisonnement s'applique sur une liste chaînée, puisqu'on ne décale aucun élément. C'est plus pertinent sur un vector, non ?

[ternel]

Parce qu'avec la liste chainée, tu parcoure depuis le début systématiquement, vu que tu n'as plus d'itérateur valide.
exactement comme pour le vecteur.

[white_tentacle]

Parce qu'avec la liste chainée, tu parcoure depuis le début systématiquement, vu que tu n'as plus d'itérateur valide.
exactement comme pour le vecteur.

Tu peux garder un itérateur valide tout le long de ton itération.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
// de mémoire
std::list<int> list;
for(auto it = list.begin(); it != list.end(); /* rien ici */)
{
  if(*it == 2)
    it = list.erase(it);
  else
    ++it;
}

Il me semble aussi que std::remove ne fonctionne pas pour un std::list (il lui faut un random access container).

edit : dans tous les cas, pour une liste mieux vaut utiliser la méthode remove ou remove_if