std::map : à quel moment les iterateur sont invalidés ?

Nicolas Castagne wrote:

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;

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).

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 )

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

Salut tous, salut Arnaud,

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?

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...

Nicolas Castagne wrote:
...
Ou plutôt std::map<std::string, Entite>
oué c'était une erreur :)

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 )

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

J'ai refait mes tests, puis inclu ça dans le programme, et tout semble
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

Salut tous, salut Arnaud,

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?

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...

Nicolas Castagne wrote:
...
Ou plutôt std::map<std::string, Entite>
oué c'était une erreur :)

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 )

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

Nicolas Castagne wrote:

Aurais-tu un pointeur sur la 'norme' à laquelle tu fais référence ?

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

Nicolas Castagne wrote:

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.

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.

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 ?

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: james.kanze@free.fr
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

Bonjour,

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;
...
}

J'ai refait mes tests, puis inclu ça dans le programme, et tout semble
se passer correctement.

Merci, donc !

Bien que fonctionnelle, je voudrai juste attirer ton attention sur le fait
que cette solution introduit un couplage entre le type stocké et le type de
conteneur.
En effet, lorsque le type Entite n'est pas stocké dans un conteneur ou qu'
il est stocké dans un conteneur d'un autre type, std::vector par exemple,
il y'aura une dépendance inutile avec map.Et que signifiera alors
"map<string, Entite *>::iterator name". Est-ce que cette optimisation est
primordiale par rapport à une meilleure conception ?
Si oui et si le type Entite sera toujours lié à un conteneur std::map, ne
faut-il pas reconsidérer la conception ?

Cordialement,
Ahmed




"Nicolas Castagne" <castagne@imag.fr> wrote in message
news:d3orn1$ude$1@trompette.imag.fr...

J'ai refait mes tests, puis inclu ça dans le programme, et tout semble
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

Salut tous, salut Arnaud,

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?

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...

Nicolas Castagne wrote:
...
Ou plutôt std::map<std::string, Entite>
oué c'était une erreur :)

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 )

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

Le Fri, 15 Apr 2005 14:07:55 +0200, Nicolas Castagne a écrit :

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.

Nota bene: std n'est pas une implémentation particulière de la STL,
c'est juste son espace de nom. Et ceci qu'on compile avec GCC, Sun CC ou
VC++. Quant à la STL de SGI, c'est précisément celle-ci qui est livré
avec la plupart des Linux, et c'est en tout cas celle qui est livrée
avec GCC.

Donc normalement, si tu compiles de C++ avec GCC, c'est bien àla STL de
SGI que tu fais appel.

Est-ce que tu avais un code qui démontrait l'invalidation de
l'itérateur ?

Curieusement,
Nowhere man

PS: est-ce que c'est aussi l'implémentation SGI de la STL qui est livrée
avec les autres compilos ?
--
nowhere.man@levallois.eu.org
OpenPGP 0xD9D50D8A

Pierre THIERRY <nowhere.man@levallois.eu.org> writes:

| Le Fri, 15 Apr 2005 14:07:55 +0200, Nicolas Castagne a écrit :
| > 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.

C'est exact. La portion de la bibliothèque standard est un
sous-ensemble de la STL de SGI. De fait, si j'en crois les paroles de
celui qui en a facilité son introduction dans la norme, il en a coupé
quelque chose comme les 2/3.
L'implémentation de GNU, même si elle était basée au départ sur celle
de SGI, s'en est substantiellement déviée pour se rapprocher de la
norme.

| Nota bene: std n'est pas une implémentation particulière de la STL,
| c'est juste son espace de nom. Et ceci qu'on compile avec GCC, Sun CC ou
| VC++. Quant à la STL de SGI, c'est précisément celle-ci qui est livré
| avec la plupart des Linux, et c'est en tout cas celle qui est livrée
| avec GCC.
|
| Donc normalement, si tu compiles de C++ avec GCC, c'est bien àla STL de
| SGI que tu fais appel.

Ce qui n'est pas vrai.

-- Gaby

Nicolas Castagne <castagne@imag.fr> writes:

| 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 ?

Oui.

| 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.

Oui mais non.

| Aurais-tu un pointeur sur la 'norme' à laquelle tu fais référence ?

§23.1.2/3

-- Gaby

Nicolas Castagne <castagne@imag.fr> writes:

| 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.

C'est un problème bien connu. Si la définition de <set> avait été
utile, tu pourrais juste écrire

std::set<Entite, EntiteCompareByName> nameSpace;

mais visiblement personnes n'a envie que ce soit utile.

| 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;
| ...
| }

Et le pointeur (valeur du mapping) viendrait d'où ?

| 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.

Exactement, qu'est-ce qui ne fonctionne pas ?

| 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.

Ah bon ?

| Qu'est-ce qu'en est-il exactement ?

Tu invalides uniquement ce qye tu as effacé -- il n'y a pas de
miracle.

-- Gaby