Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

parcours d'une std::list avec déletion éventuelle d'éléments

9 réponses
Avatar
meow
Tout est dit dans le sujet, je cherche la mani=E8re =E9l=E9gante de
parcourir une liste en supprimant =E9ventuellement certains =E9l=E9ments.
Mon probl=E8me r=E9side essentiellement dans la mauvaise compr=E9hension
que j'ai de la validit=E9 des iterateurs lors d'une d=E9l=E9tion...

Voil=E0 donc ce que j'avais =E9crit et qui me semble =E0 la fois fumeux et
faux (si le premier iterateur v=E9rifie unCrit=E8re on va dans le mur,
non ?) :

std::list<Cell_handle> i;
.=2E.
std::list<Cell_handle>::iterator i,erase_me;
while (i!=3Din.end()) {
for (int j=3D0;j<4;j++)
if ( unCritere(*i, autres trucs) ){
(*i)->info().setDepth(1);
erase_me=3Di;--i;
in.erase(erase_me);
break;
}
++i;
}

Depuis, j'ai appris l'existence de remove_if, n=E9anmoins, ne serait-ce
que pour approfondir ma compr=E9hension des iterateurs de liste, je me
demande s'il existe une m=E9thode propre de type boucle (i.e. avec un
while ou un for).

9 réponses

Avatar
Fabien LE LEZ
On 28 Feb 2006 01:54:46 -0800, "meow" :

std::list<Cell_handle> i;
...
std::list<Cell_handle>::iterator i,erase_me;
while (i!=in.end()) {


Groumpf ? J'avoue que je ne comprends rien à ton code. Tu as un
std::list qui s'appelle i, puis un itérateur qui s'appelle i aussi,
mais que tu n'as pas initialisé...

for (int j=0;j<4;j++)


... puis une boucle dont je n'arrive pas à voir le sens.


ne serait-ce
que pour approfondir ma compréhension des iterateurs de liste, je me
demande s'il existe une méthode propre de type boucle


for (list<Machin>::iterator i= liste.begin(); i != liste.end();)
{
if (on_doit_effacer)
i= erase (i);
else
++i;
}

Avatar
meow
J'avoue que je ne comprends rien à ton code
oups, oui, c'est vrai... Comme d'hab je modifies mon code à la volée

pour le rendre plus simple et j'y introduit des erreurs

for (int j=0;j<4;j++)
Une autre illustration de ce que je disais au dessus... Dans mon code

je traites des tetrahedres (4 voisins à tester, etc...).

i= erase (i);
Ah, bein oui tiens... Je n'avais pas fait attention à la valeur de

retour de erase.
Merci beaucoup Fabien.

Avatar
folays
"meow" writes:

Tout est dit dans le sujet, je cherche la manière élégante de
parcourir une liste en supprimant éventuellement certains éléments.
Mon problème réside essentiellement dans la mauvaise compréhension
que j'ai de la validité des iterateurs lors d'une délétion...

[...]

Depuis, j'ai appris l'existence de remove_if, néanmoins, ne serait-ce
que pour approfondir ma compréhension des iterateurs de liste, je me
demande s'il existe une méthode propre de type boucle (i.e. avec un
while ou un for).



Bonjour,

J'ai eu besoin de faire ca aussi, je ne suis pas sur de ma methode
mais pour l'instant elle marche:

En gros je sauvegarde l'iterator dans un 2eme iterator fait pour ca,
et j'increment l'iterator que j'utilise dans la boucle
Apres cela je supprime l'iterator de sauvegarde selon une condition,
et je peux quand meme continuer a "iterer" puisque j'ai juste supprime
une sauvegarde.

Je suis neanmoins pas sur que ce code soit sur :)

<code>
class Module
{
HMODULE hinstLib;
FARPROC hProcLoad, hProcFree;
public:
static list <Module *> linked;
basic_string <char> name;

Module(basic_string <char> mod);
~Module();

static void Free(basic_string <char> mod);
};

void Module::Free(basic_string <char> mod)
{
list <Module *>::iterator it;
list <Module *>::iterator save;
it = Module::linked.begin();
while (it != Module::linked.end())
{
cout << *it << endl;
save = it++;
if ((*save)->name == mod)
delete *save;
}
}
</code>

Pour le background, Module::linked est une liste statique
a la class Module qui contient une liste des .dll chargees
pendant l'execution, et cette fonction membre permet d'en
decharger a partir du nom (le delete cause l'appel du
destructeur qui se charge de faire ce qu'il faut)

--
folays

Avatar
kanze
folays wrote:
"meow" writes:

Tout est dit dans le sujet, je cherche la manière élégante
de parcourir une liste en supprimant éventuellement certains
éléments. Mon problème réside essentiellement dans la
mauvaise compréhension que j'ai de la validité des
iterateurs lors d'une délétion...

[...]

Depuis, j'ai appris l'existence de remove_if, néanmoins, ne
serait-ce que pour approfondir ma compréhension des
iterateurs de liste, je me demande s'il existe une méthode
propre de type boucle (i.e. avec un while ou un for).


J'ai eu besoin de faire ca aussi, je ne suis pas sur de ma
methode mais pour l'instant elle marche:

En gros je sauvegarde l'iterator dans un 2eme iterator fait
pour ca, et j'increment l'iterator que j'utilise dans la
boucle.


Tu veux dire quelque chose comme :

while ( current != end ) {
std::list<X>::iterator tmp = current ++ ;
if ( aSupprimer( tmp ) ) {
liste.erase( tmp ) ;
}
}

Ça marche aussi. Si la seule chose dans la boucle, c'est le test
et la suppression, je préfère la version de Fabien (mais c'est
vraiment une question de goût -- il n'y a pas de motivation
technique). S'il y a d'autre chose aussi dans la boucle, tout
dépend -- ta version a l'avantage de ne faire l'incrémentation
que dans un seul endroit.

Apres cela je supprime l'iterator de sauvegarde selon une
condition, et je peux quand meme continuer a "iterer" puisque
j'ai juste supprime une sauvegarde.

Je suis neanmoins pas sur que ce code soit sur :)

<code>
[...]

void Module::Free(basic_string <char> mod)
{
list <Module *>::iterator it;
list <Module *>::iterator save;
it = Module::linked.begin();


Pourquoi séparer l'initialisation de la déclaration ? Et
pourquoi déclarer la variable save ici, et non dans la boucle ?

while (it != Module::linked.end())
{
cout << *it << endl;
save = it++;
if ((*save)->name == mod)
delete *save;


Ce qui supprime l'objet, mais laisse le pointeur (invalid) dans
la liste. Ce qui est formellement un comportement indéfini, tout
de suite, et risque fort de ne pas marcher réelement dès le
prochain parcours de la liste, puisque tu n'as aucun moyen à
savoir quels pointeurs sont valides.

}
}
</code>


--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


Avatar
folays
"kanze" writes:

[...]
void Module::Free(basic_string <char> mod)
{
list <Module *>::iterator it;
list <Module *>::iterator save;
it = Module::linked.begin();


Pourquoi séparer l'initialisation de la déclaration ? Et
pourquoi déclarer la variable save ici, et non dans la boucle ?


C'etait hier ma premiere utilisation des iterator, et j'etais
deja content que ca marche, j'ai pas encore les bons reflexes.

while (it != Module::linked.end())
{
cout << *it << endl;
save = it++;
if ((*save)->name == mod)
delete *save;


Ce qui supprime l'objet, mais laisse le pointeur (invalid) dans
la liste. Ce qui est formellement un comportement indéfini, tout
de suite, et risque fort de ne pas marcher réelement dès le
prochain parcours de la liste, puisque tu n'as aucun moyen à
savoir quels pointeurs sont valides.

}
}
</code>



Si tu veux parler du pointeur dans la liste pointant vers le "Module *"
qui vient de se faire delete, non, car le destructeur de cet object
se charge de faire un FreeLibrary et de s'enlever lui-meme de la
liste :)

Et Module::Free() est statique donc l'objet qu'on delete ne peut pas
etre le contexte dans lequel est apelle cette fonction membre
puisqu'il y n'y a pas de "this" :)

<code>
Module::~Module()
{
cout << this << " Module::~Module()" << endl;
cout << name << ": freeing..." << endl;
if (hProcFree)
hProcFree();
FreeLibrary(hinstLib);
linked.remove(this);
}
</code>

Si tu parles de l'invalidite d'un autre pointeur explicite plus stp :)

Merci

--
folays


Avatar
kanze
folays wrote:
"kanze" writes:


[...]
while (it != Module::linked.end())
{
cout << *it << endl;
save = it++;
if ((*save)->name == mod)
delete *save;


Ce qui supprime l'objet, mais laisse le pointeur (invalid)
dans la liste. Ce qui est formellement un comportement
indéfini, tout de suite, et risque fort de ne pas marcher
réelement dès le prochain parcours de la liste, puisque tu
n'as aucun moyen à savoir quels pointeurs sont valides.

}
}
</code>



Si tu veux parler du pointeur dans la liste pointant vers le
"Module *" qui vient de se faire delete, non, car le
destructeur de cet object se charge de faire un FreeLibrary et
de s'enlever lui-meme de la liste :)


D'accord, mais c'est subtile. Et c'est probable que std::list<>
ne soit pas la structure qu'il te faut -- comment faire un
erase() de l'objet dans la liste sans en avoir l'itérateur ? (Ou
est-ce que le constructeur fait l'insértion (avec insert, et non
avec push_back) et sauve l'itérateur.

Pour ce genre d'application, il me semble que std::set est tout
indiqué. (J'imagine qu'en fait, tu n'aurais jamais plusieurs
Module avec le même nom. Sinon, il y a aussi std::multi_set.)

Et Module::Free() est statique donc l'objet qu'on delete ne
peut pas etre le contexte dans lequel est apelle cette
fonction membre puisqu'il y n'y a pas de "this" :)

<code>
Module::~Module()
{
cout << this << " Module::~Module()" << endl;
cout << name << ": freeing..." << endl;
if (hProcFree)
hProcFree();
FreeLibrary(hinstLib);
linked.remove(this);
}
</code>

Si tu parles de l'invalidite d'un autre pointeur explicite
plus stp :)


Non, c'était bien le pointeur qui trainait dans la liste.
N'empèche que je verrais plutôt un std::set ou un std::map. Je
ne crois pas que ce soit un problème ici (parce que la liste ne
contiendra jamais des milliers d'entrées), mais list<>::remove()
a une compléxité O(n), où n est le nombre d'éntrées dans la
liste. Ce qui fait que ta fonction Free est quadratique.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34



Avatar
folays
"kanze" writes:

D'accord, mais c'est subtile. Et c'est probable que std::list<>
ne soit pas la structure qu'il te faut -- comment faire un
erase() de l'objet dans la liste sans en avoir l'itérateur ? (Ou
est-ce que le constructeur fait l'insértion (avec insert, et non
avec push_back) et sauve l'itérateur.


La liste est statique publique donc on peut toujours avoir un
iterateur sur elle, ou la parcourir avec un for et delete les objets

Le constructeur fait effectivement l'insertion, mais avec push_back:
new Module((basic_string <char>)"mod_test.dll");

Quelle est la difference de vitesse entre push_back et insert?
J'ose esperer que la class maintient un pointeur vers le dernier
et premier element vu que ces operations sont a priori courantes
J'ose supposer que la liste est doublement chainee vu qu'il y'a
des iterators bidirectionnel

Pour ce genre d'application, il me semble que std::set est tout
indiqué. (J'imagine qu'en fait, tu n'aurais jamais plusieurs
Module avec le même nom. Sinon, il y a aussi std::multi_set.)

[...]

N'empèche que je verrais plutôt un std::set ou un std::map. Je
ne crois pas que ce soit un problème ici (parce que la liste ne
contiendra jamais des milliers d'entrées), mais list<>::remove()
a une compléxité O(n), où n est le nombre d'éntrées dans la
liste. Ce qui fait que ta fonction Free est quadratique.


Globalement les insert/remove se font qu'au lancement et a la fin
du serveur et y'aura en effet peu d'entree
Mais j'ai besoin que ca soit une liste non triee (bien que l'on puisse
apparament specifier la fonction de tri pour std::set et donc simuler
un tri qui ne trie pas)
Le projet est en fait un apache-like, sans bien sur en avoir la
pretention (projet d'etudiant), et il est important de conserver
l'ordre des modules comme dans apache, car des hooks sont contenus
a l'interieur desdits modules et certains doivent agir avant ou
apres d'autres (ils sont appeles dans l'ordre de la liste).

En fait le plus important c'est qu'au final la liste soit parcourue
en lecture seule le plus rapidement possible, et la je ne sais pas
quel est la classe la plus adaptee ?

--
folays

Avatar
Fabien LE LEZ
On 01 Mar 2006 11:45:46 +0100, folays :

list <Module *>::iterator it;
list <Module *>::iterator save;
it = Module::linked.begin();


Pourquoi séparer l'initialisation de la déclaration ? Et
pourquoi déclarer la variable save ici, et non dans la boucle ?


C'etait hier ma premiere utilisation des iterator, et j'etais
deja content que ca marche, j'ai pas encore les bons reflexes.


Note que c'est indépendant de la notion d'itérateur. S'il s'était agi
d'entiers, les remarques de James resteraient valides.



Avatar
kanze
folays wrote:
"kanze" writes:

D'accord, mais c'est subtile. Et c'est probable que
std::list<> ne soit pas la structure qu'il te faut --
comment faire un erase() de l'objet dans la liste sans en
avoir l'itérateur ? (Ou est-ce que le constructeur fait
l'insértion (avec insert, et non avec push_back) et sauve
l'itérateur.


La liste est statique publique donc on peut toujours avoir un
iterateur sur elle, ou la parcourir avec un for et delete les
objets

Le constructeur fait effectivement l'insertion, mais avec
push_back: new Module((basic_string <char>)"mod_test.dll");

Quelle est la difference de vitesse entre push_back et insert?


Dans le cas de std::list, aucune. La différence, c'est que
insert peut se faire n'importe où (push_back, c'est l'équivalent
à liste.insert( liste.end(), nouveauElement )), et que insert
renvoie un itérateur à l'élément inséré. Et aussi, qu'insert est
toujours présente, quelque soit la collection, tandis que
push_back n'est présente que s'il peut être implémenté en temps
amorti constante.

Dans ton cas, l'intérêt d'insert, c'est l'itérateur qu'il te
renvoie. Si tu garde l'itérateur dans l'objet, tu peux
l'utiliser avec erase dans le destructeur. Et erase, c'est
beaucoup plus rapide que remove : O(1) contre O(n).

J'ose esperer que la class maintient un pointeur vers le
dernier et premier element vu que ces operations sont a priori
courantes. J'ose supposer que la liste est doublement chainee
vu qu'il y'a des iterators bidirectionnel


En effet, c'est quasiment impossible à remplir les contraits de
complexité autrement.

Pour ce genre d'application, il me semble que std::set est
tout indiqué. (J'imagine qu'en fait, tu n'aurais jamais
plusieurs Module avec le même nom. Sinon, il y a aussi
std::multi_set.)

[...]

N'empèche que je verrais plutôt un std::set ou un std::map.
Je ne crois pas que ce soit un problème ici (parce que la
liste ne contiendra jamais des milliers d'entrées), mais
list<>::remove() a une compléxité O(n), où n est le nombre
d'éntrées dans la liste. Ce qui fait que ta fonction Free
est quadratique.


Globalement les insert/remove se font qu'au lancement et a la
fin du serveur et y'aura en effet peu d'entree. Mais j'ai
besoin que ca soit une liste non triee (bien que l'on puisse
apparament specifier la fonction de tri pour std::set et donc
simuler un tri qui ne trie pas). Le projet est en fait un
apache-like, sans bien sur en avoir la pretention (projet
d'etudiant), et il est important de conserver l'ordre des
modules comme dans apache, car des hooks sont contenus a
l'interieur desdits modules et certains doivent agir avant ou
apres d'autres (ils sont appeles dans l'ordre de la liste).


Entendu. C-à-d qu'il faut que la collection soit triée, mais sur
l'ordre d'insertion, et non sur l'ordre alphabètique des noms
des modules ni sur l'ordre de leur adresse en mémoire:-).

S'il t'arrive un jour à avoir à charger plusieurs milliers de
modules, tu peux toujours penser à ajouter une indice
sécondaire. Mais j'imagine que ce ne serait pas un problème
immédiate:-).

En fait le plus important c'est qu'au final la liste soit
parcourue en lecture seule le plus rapidement possible, et la
je ne sais pas quel est la classe la plus adaptee ?


Parcourue, problement std::vector. Mais il faudrait d'abord
reflechir sur la durée de vie de ces itérateurs ; effacer un
élément d'un std::vector invalide tous les itérateurs à des
éléments suivants. Ta boucle ne marchera plus. En revanche :
est-ce que tu as besoin de continuer la boucle une fois
l'élément trouvé ? C-à-d est-ce que tu peux avoir plusieurs
modules du même nom ? Sinon, je verrais bien un Free à peu
près :

void
Module::free(
std::string const& name )
{
std::list< Module* >::iterator
elem
= std::find_if( linked.begin(), linked.end(),
boost::bind( &Module::name, _1 ) == name ) ;
if ( elem != linked.end() ) {
delete *elem ;
}
}

(Ceci suppose que tu as une fonction, Module::name(), plutôt que
d'accéder directement aux données membre. C'est AMHA une bonne
idée de toute façon -- il est raisonable que de non-membres
veuille lire le nom, mais non qu'ils le modifient.)

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34