Probleme avec la methode erase de la STL

On Mon, 28 Jun 2004 13:31:12 +0200, Fabien Garcia <no@spam>:

- Suis je le seul a trouver ce comportement illogique ?

Euh... C'est plutôt ton approche du problème que je trouve bizarre.
Si tu veux avoir l'unicité des Ident, utilise set<Ident>.
Si tu veux garder le nombre d'occurences de chaque Ident quelque part,
utilise map<Ident,int>.


--
schtroumpf schtroumpf

Le Mon, 28 Jun 2004 19:51:43 +0200, Fabien LE LEZ <gramster@gramster.com>
a écrit:

On Mon, 28 Jun 2004 13:31:12 +0200, Fabien Garcia <no@spam>:

- Suis je le seul a trouver ce comportement illogique ?

Euh... C'est plutôt ton approche du problème que je trouve bizarre.
Si tu veux avoir l'unicité des Ident, utilise set<Ident>.
Si tu veux garder le nombre d'occurences de chaque Ident quelque part,
utilise map<Ident,int>.

Soit, mais je ne veux justement pas l'unicite des Ident, je souhaite
garder le nombre de chaque identifiant dans le vecteur.
En fait j'y ai travaille un peu plus cet apres midi et je pense avoir
trouve une faille qui est due a mon programme.
En effet, quand l'operateur = est appelle, on est cense s'occuper (quand
on l'a surcharge) de liberer les ressources tenues par la 'lvalue' ... et
je le faisais mal.

Merci en tout cas d'avoir lu mon post et d'y avoir repondu...
et desole que le probleme vienne de moi :/

Fabien Garcia

Fabien Garcia wrote:

Bonjour a tous,

Je me heurte a un petit probleme avec la methode erase sur un objet
vector de la STL, et je n'ai rien trouve dans les forums/tutorials qi
m'aide...

Voici le code qui me pose probleme :

int main(){
std::vector <Ident> ids;
Ident id;

ids.push_back(id);
ids.push_back(id);

ids[0].new_id();
ids[1].new_id();

ids.erase(ids.begin());

ids.clear();
return 0;
}


La classe Ident a pour burt de me donner un identifiant (non unique
pouisque je defini la copie et l'affectation) sous forme d'un int. Pour
ne pas avoir des identifiants qui augmentent const amment, j'ai
implemente via un membre statique de Idnet (Ident::vector<int> _all_ids)
un mecanisme qui garde trace du nombre de chaque identifiants assignes
(_all_ids[0] conetant le nombre d'identifiants 0 , ...). Quand je
detruit un objet de la classe Ident, je decremente le compteur associe a
son identifiant (_all_ids[_my_id]--).

Hors en ajouant des traces dans la classe Ident, il se passe la chose
suivante quand je fait le erase du premier element de ids ci dessus :
- utilisation de l'operateur = pour copier _all_ids[1] dans _all_ids[0]
- destruction de _all_ids[1]

Hors dans mon cas, cela pose probleme puisque l'objet detruit a un
l'identifiant 1 alors que je souhaitais detruire un objet avec
l'identifiant 0....

Ca m'a l'air normal. Les conteneurs de la STL manipulent les instances
contenues par valeur, donc il faut que tes propriétés d'unicité soient
conservées lors de la manipulation de Ident par valeur, ce que tu as
visiblement tenté de faire puisque tu dis avoir recodé la copie et
l'affectation.

std::vector<> est un tableau contigüe d'instances. Pour effacer une
partie d'un vector, on décale (copie) généralement les éléments suivants
la partie à effacer sur celle-ci, et on libère la partie décalée, à
moins qu'une réallocation soit réalisée. C'est ce qui se passe dans ton
cas :

v = {ident(0), ident(1)};

on veut effacer v[0], on fait :
v[0] = v[1] => v=={ident(1), ident(1)}
Suppression en fin => v=={ident(1)}

Le problème c'est que visiblement la redéfinition de l'affectation ne
fonctionne pas correctement. Ce qui devrait se passer c'est :

v[0] = v[1] => _all_ids[1]++, _all_ids[0]--, assert(_all_ids[0]==0)
Note que :
- Le destructeur de ident(0) n'est pas appelé.
- L'ordre des affectations a une grande importance, entre autres dans
des cas d'auto assignation, ou d'échange de valeurs ayant toute deux des
compteurs à 1).

Suppression en fin => ~ident(1), _all_ids[1]--

En bref, tu as commencé à faire un système de comptage de référence et
c'est pas complètement trivial.

En ce qui concerne la STL :
http://www.sgi.com/tech/stl/table_of_contents.html

Patrick Mézard

Fabien Garcia <no@spam> wrote in message
news:<opsaayaags1l58dj@news.free.fr>...

Je me heurte a un petit probleme avec la methode erase sur un objet
vector de la STL, et je n'ai rien trouve dans les forums/tutorials qi
m'aide...

Voici le code qui me pose probleme :

int main(){
std::vector <Ident> ids;
Ident id;

ids.push_back(id);
ids.push_back(id);

ids[0].new_id();
ids[1].new_id();

ids.erase(ids.begin());

ids.clear();
return 0;
}

La classe Ident a pour burt de me donner un identifiant (non unique
pouisque je defini la copie et l'affectation) sous forme d'un
int. Pour ne pas avoir des identifiants qui augmentent const amment,
j'ai implemente via un membre statique de Idnet (Ident::vector<int>
_all_ids) un mecanisme qui garde trace du nombre de chaque
identifiants assignes (_all_ids[0] conetant le nombre d'identifiants 0
, ...). Quand je detruit un objet de la classe Ident, je decremente le
compteur associe a son identifiant (_all_ids[_my_id]--).

Hors en ajouant des traces dans la classe Ident, il se passe la chose
suivante quand je fait le erase du premier element de ids ci dessus :

- utilisation de l'operateur = pour copier _all_ids[1] dans _all_ids[0]
- destruction de _all_ids[1]

Hors dans mon cas, cela pose probleme puisque l'objet detruit a un
l'identifiant 1 alors que je souhaitais detruire un objet avec
l'identifiant 0....

Ceci me donne donc a la fin dans _all_ids :
1 identifiant 0
-1 identifiants 1 !!!

J'en viens donc a mes questions :
- Est ce un comportement normal pour la STL ? (il semblerait, ce code a
ete teste avec g++ et VC++...)
- Suis je le seul a trouver ce comportement illogique ?
- Comment faire...

D'après les symptomes, tu as une classe qui n'est pas copiable ni
affectable. Les spécifications de la STL exige les deux. Tu as violé le
contrat ; c'est normal que la STL ne donne pas le résultat escompté.
Mais la STL n'y est pour rien. Qu'est-ce qui se passe si je fais quelque
chose comme :

Ident f() { Ident id ; id.new_id() ; return id ; }

Ident id ;
id.new_id() ;
id = f() ;

? Je parie que ça ne marche pas non plus.

Si j'ai bien compris, ta classe a une invariante qui concerne un objet
statique, externe à la classe. Si tu veux supporter la copie et
l'affectation, il faut que tu lui donne un constructeur de copie et un
opérateur d'affectation qui maintient ces invariantes. Systèmatiquement,
et indépendamment de la STL. (Si tu ne veux pas supporter la copie et
l'affectation, tu ne peux pas mettre les objets dans une collection de
la STL. En général, dans de tels cas, il est souhaitable d'interdire ces
opérations, en les déclarant privées, de façon à avoir une erreur à la
compilation, plutôt qu'un comportement aléatoire si quelqu'un les
utilise par erreur.)

Dans ton cas, par exemple, il te faudrait quelque chose comme :

Ident::Ident( Ident const& other )
: myId( other.myId )
{
++ ourAllIds[ myId ] ;
}

Idend&
Ident::operator=( Ident const& other )
{
++ ourAllIds[ other.myId ] ;
-- ourAllIds[ myId ] ;
myId = other.myId ;
return ;
}

Ton utilisation de new_id() me fait poser la question si tu as bien
établit l'invariante dans le constructeur par défaut, aussi. Il faut
absolument que 1) myId reçoive une bonne valeur, et 2) le compte pour
cette valeur soit incrémentée.

PS : Si quelqu'un a un pointeur sur une explication du fonctionnement
de erase, je suis preneur, je n'ai rien trouve de satisfaisant...

Le problème dans ton code n'a rien à voir avec erase. En fait, la
fonction erase est bien simple : l'itérateur que tu passes comme
paramètre spécifie un élément n, on a les post-conditions :

new.size() = old.size() - 1
forall i >= 0, i < n : new[ i ] equiv[ i ]
forall i >= n, i < new.size() : new[ i ] equiv[ i + 1 ]

C'est à toi de définir ce que tu entends par equiv, mais
l'implémentation des opérateurs de copie et de l'affectation doivent la
respecter, c-à-d que :
- après <code>Ident i( old ) ;</code> f$i equiv oldf$
et
- après <code>i = old ;</code> f$i equiv oldf$
(En format Doxygen, voir
http://www.stack.nl/~dimitri/doxygen/manual.html, mais aussi
http://www.fi.uib.no/Fysisk/Teori/KURS/WRK/TeX/symALL.html pour la
partie LaTex.)

Et évidemment, après n'importe quelle opération, il faut que les
invariantes de classe soient maintenues. C'est à vérifier pour toute
fonction non-const. Impérativement ; si ce n'est pas trivialement
évident, il faut un commentaire qui le démontre, de façon à ce que celui
qui lit ton code n'a pas à poser la question ; si la classe contient des
éléments mutable, il le faut pour toute fonction, const ou non.
(J'aurais tendance à dire que si ce n'est pas trivialement évident, les
invariantes sont trop compliquées, et qu'il faut simplifier. Mais je
sais que dans la pratique, ce n'est pas toujours possible.)

--
James Kanze GABI Software http://www.gabi-soft.fr
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