std::map : à quel moment les iterateur sont invalidés ?
Le
Nicolas Castagne
Bonjour à tous,
dans mon appli, j'ai besoin à la fois de :
1 - accéder rapidement à des entités (classe Entite) par nom (string -
le nom est unique)
2 - récupérer le nom de ces entités lorsque je manipule une Entitie
Le 1- tend à ce qu'une std::map soit utilisée, par exemple :
map<const string , Entite*, ltstr> nameSpace;
Le 2- tend à ce que le nom soit stoqué dans les objets Entite, par exemple :
class Entite {
string name;
}
Mais dans ce cas, il y a la duplication de donnée.
Mon programme est ammené à manipuler un grand nombre d'entité, et par
suite un grand nombre de noms. Les noms peuvent être longs.
Je cherche donc à optimiser ces deux actions, sans dupliquer l'info.
Une solution consisterait à stoquer dans Entite un iterator sur la map :
class Entite {
map<string, Entite *>::iterator name;
}
Dans la STL de SGI, cela semble possible, puique la doc de stl::map
précise :
> Map has the important property that inserting a new element into a map
> does not invalidate iterators that point to existing elements. Erasing
> an element from a map also does not invalidate any iterators, except,
> of course, for iterators that actually point to the element that is
> being erased.
(from : http://www.sgi.com/tech/stl/Map.html )
J'ai essayé avec la map de std mais ca semble ne pas fonctionner.
Aucune des docs que j'ai lu qui présentent std::map ne présente
d'information quant aux conditions dans lesquelles un iterator sur une
std::map devient invalide.
Qu'est-ce qu'en est-il exactement ?
Y a t il une différence sur l'invalidation des itérator pour les map
entre la stl de SGI et std ?
Plus généralement, quel solution de conception 'typique' proposeriez
vous pour traiter ce problème, à savoir : optimiser à la fois l'accès
par nom à une entité et l'accès au nom d'une entité donnée, sans
dupliquer les données ?
Merci d'avance !!!
Nicolas
dans mon appli, j'ai besoin à la fois de :
1 - accéder rapidement à des entités (classe Entite) par nom (string -
le nom est unique)
2 - récupérer le nom de ces entités lorsque je manipule une Entitie
Le 1- tend à ce qu'une std::map soit utilisée, par exemple :
map<const string , Entite*, ltstr> nameSpace;
Le 2- tend à ce que le nom soit stoqué dans les objets Entite, par exemple :
class Entite {
string name;
}
Mais dans ce cas, il y a la duplication de donnée.
Mon programme est ammené à manipuler un grand nombre d'entité, et par
suite un grand nombre de noms. Les noms peuvent être longs.
Je cherche donc à optimiser ces deux actions, sans dupliquer l'info.
Une solution consisterait à stoquer dans Entite un iterator sur la map :
class Entite {
map<string, Entite *>::iterator name;
}
Dans la STL de SGI, cela semble possible, puique la doc de stl::map
précise :
> Map has the important property that inserting a new element into a map
> does not invalidate iterators that point to existing elements. Erasing
> an element from a map also does not invalidate any iterators, except,
> of course, for iterators that actually point to the element that is
> being erased.
(from : http://www.sgi.com/tech/stl/Map.html )
J'ai essayé avec la map de std mais ca semble ne pas fonctionner.
Aucune des docs que j'ai lu qui présentent std::map ne présente
d'information quant aux conditions dans lesquelles un iterator sur une
std::map devient invalide.
Qu'est-ce qu'en est-il exactement ?
Y a t il une différence sur l'invalidation des itérator pour les map
entre la stl de SGI et std ?
Plus généralement, quel solution de conception 'typique' proposeriez
vous pour traiter ce problème, à savoir : optimiser à la fois l'accès
par nom à une entité et l'accès au nom d'une entité donnée, sans
dupliquer les données ?
Merci d'avance !!!
Nicolas
Poser une question
Ou plutôt std::map<std::string, Entite> (le const est inutile sur la
clé, et à moins d'avoir une bonne raison de faire autrement, autant
stocker directement les objets dans le conteneur, ca évite de devoir
te coltiner la gestion de la mémoire à la main).
C'est une garantie donnée par la norme, et que toute implémentation
doit respecter. Sur quelle implémentation as tu observé un
comportement différent?
Arnaud
Sur std de gcc, Linux, RedHat Enterprise. Rien que du très commun.
Es-tu sur que la norme relative aux conteneurs de la librairie standard
std garantisse la non-invalidation des iterator des map en cas d'ajout
et de suppression ?
Parce que la STL de SGI le garantit, mais ce n'est pas une 'norme'...
A priori, sauf erreur, rien n'indique que std respectent les choix fait
pour la STL.
Aurais-tu un pointeur sur la 'norme' à laquelle tu fais référence ?
Sinon, bien sur, il est possible que ma série de tests soit bugguée. Je
vais verifier ça.
Nico
Sinon...
se passer correctement.
Merci, donc !
(au cas où, je suis toujours preneur d'info sur les liens entre les
specifs des conteneurs de la std et celles de la stl !)
Nico
La norme ISO elle-même : 23.1.2/8 :
[A propos des conteneurs associatifs] : The insert members shall not affect
the validity of iterators and references to the container, and the erase
members shall invalidate only iterators and references to the erased
elements.
Un bon bouqin de référence sur le sujet est le Josuttis
Arnaud
La solution « consacrée », c'est d'utiliser un std::set< Entite,
EntityNameComparer >, avec le code dans EntityNameComparer qui
va bien. Cette solution est préconcisée par plusieurs experts,
même dans le cas où on veut pouvoir modifier les autres champs
des éléments (ce qui implique un const_cast, parce que std::set
ne va te donner que des références const aux éléments).
Si je mets le mot « consacrée » en guillemets, c'est que je ne
suis pas complètement convaincu moi-même. Formellement, la façon
correcte de modifier un élément d'un set, c'est de l'extraire,
le modifier, puis de le réinsérer. Dans toutes les applications
que j'ai eu jusqu'ici, c'était aussi une façon acceptable, y
compris de point de vue des performances. (C'était même souvent
la seule solution valable, parce que mes modifications portaient
sur la clé.)
Un autre alternatif serait std::map< std::string const*,
Entite*, ComparePointedTo >, avec des pointeurs. Et évidemment,
tu t'arranges pour que la clé pointe à la chaîne dans Entite. Ça
marche, mais ça introduit un problème de gestion de la durée de
vie. En revanche, si les objets de type Entite ont de toute
façon leur propre durée de vie, c'est une solution simple et
efficace.
La plupart du temps, la duplication de la chaîne ne m'a pas posé
de problème. Donc, std::map< std::string, Entite > avec aussi la
chaîne dans Entite. (Mais même quand la duplication en soi n'est
pas un problème, ça peut poser des problèmes de cohérence -- il
n'y a rien formellement qui empèche une différence entre la
chaîne clé et la chaîne dans Entite.)
--
James Kanze mailto:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34