[map] constance des itérateurs à l'insertion

Salut,

Je me posais la question de savoir si les itérateurs dans les maps, principalement, mais cela pourrait être généralisé à l'ensemble des conteneurs, restaient constant lors d'une insertion.

Il se fait que j'ai plusieurs classes qui devraient faire référence à une (et parfois même, à plusieurs) éléments qui se trouvent dans des conteneurs de la STL, et l'une des solutions envisageables seraient, tout simplement, de déclarer un membre comme étant un itérateur de la map dans laquelle apparait cet élément (étant entendu que les éléments présents dans le conteneur ne seront jamais retirés).

La question est donc:

Citation:

---

si je défini un membre comme étant un itérateur sur l'élément correspondant dans la map et que, par la suite, la map subit une insertion, l'itérateur précédemment défini restera-t-il valide et correct, ou risque-t-il de subir une modification quelconque (pointer vers un autre élément ou, carrément, pointer sur un endroit invalide) :question:

---

Merci d'avance

La réponse dépend du conteneur. Pour une map, c'est bon, le seul point étant la suppression qui invalide l'itérateur de l'élément supprimé.

Pour un vecteur, n'importe quelle insertion invalide les itérateurs sauf si un bon reserve a été fait avant, et une suppression invalide les itérateurs arrivant après l'élément supprimé.

Pour une liste, même principe qu'une map.

Citation:

---

Envoyé par JolyLoic

Pour une map, c'est bon, le seul point étant la suppression qui invalide l'itérateur de l'élément supprimé.

---

Mais le seul itérateur invalidé serait donc l'élément supprimé :question:

Si oui, cela signifie qu'il n'y aurait que les instances qui utilisent cet itérateur bien précis qui deviendraient invalides...

A l'extrème limite, en passant par un DP proche de l'observer, on pourrait alors veiller à ce que les instances concernées soient correctement détruites ;):D

Citation:

---

Envoyé par JolyLoic

Pour un vecteur, n'importe quelle insertion invalide les itérateurs sauf si un bon reserve a été fait avant, et une suppression invalide les itérateurs arrivant après l'élément supprimé.

---

je m'en serais douté, du fait des réallocations qui risquent de survenir à l'insertion...

Si je devais utiliser un vecteur, j'utiliserais plutot comme référence simplement... l'index dans le tableau, en interdisant l'ajout ailleurs qu'en fin de tableau :D

Encore une fois, tu te montres digne de ta réputation :D:chin:

Citation:

---

Envoyé par koala01

Mais le seul itérateur invalidé serait donc l'élément supprimé :question:

Si oui, cela signifie qu'il n'y aurait que les instances qui utilisent cet itérateur bien précis qui deviendraient invalides...

---

Je serais partisant de dire que seul l'itérateur pointant sur l'élément supprimé serait invalide : je ne pense pas qu'à chaque insertion la map réorganise sa mémoire.
Un moyen simple de vérifier serait de tester avec deux itérateurs : un sur l'entrée que tu veux supprimer, l'autre sur l'entrée qui suit.
Comme erase te renvoie un itérateur sur l'élément qui suit directement celui qui vient dêtre supprimé, tu n'as qu'à vérifier si ce retour est égal à celui qui tu avais sauvegardé.

Je sais pas si j'ai été très clair...:aie:

Citation:

---

Envoyé par koala01

Mais le seul itérateur invalidé serait donc l'élément supprimé :question:

---

Oui

[QUOTE=spoutspout;2670956]<snip>
Comme erase te renvoie un itérateur sur l'élément qui suit directement celui qui vient dêtre supprimé, tu n'as qu'à vérifier si ce retour est égal à celui qui tu avais sauvegardé./QUOTE]

Ah, non... la méthode erase d'une map renvoie, au mieux, le nombre d'éléments supprimés, et encore, à condition d'utiliser la synthaxe eras(iterator first, iterator last), qui est de type size_t... Et vouloir utiliser ce retour comme base de définition d'un itérateur (par exemple, en utilisant le nombre comme la clé de la map) revient à s'élancer vers un mur :P

Quoi qu'il en soit, cette "question subsidiaire" avait plus pour but de m'assurer de la bonne compréhension des écrits de JolyLoic, car, comme je l'ai signalé, il ne devrait normalement pas y avoir de suppression dans les map utilisées (mais bon, quelques tests seront peut être tentés, si besoin est)...

Bien plus que la suppression, c'était surtout le comportement des itérateurs lors de l'insertion qui m'intéressaient (m'inquiétaient :P)

@JolyLoic: merci de cette précision :D

Citation:

---

Envoyé par koala01

Ah, non... la méthode erase d'une map renvoie, au mieux, le nombre d'éléments supprimés, et encore, à condition d'utiliser la synthaxe erase(iterator first, iterator last), qui est de type size_t...

---

Euh, je suis pas d'accord, à moins qu'on parle pas de la même chose! Moi j'ai ça comme doc.

En théorie, il n'y a pas de valeur de retour sur un erase prenant un itérateur en paramètre. Certaines implémentations ont décidé d'ajouter une valeur de retour par rapport à la norme.

Citation:

---

Envoyé par JolyLoic

La réponse dépend du conteneur. Pour une map, c'est bon, le seul point étant la suppression qui invalide l'itérateur de l'élément supprimé.

Pour une liste, même principe qu'une map.

---

Pour une liste ok (et encore...), Mais pour la map (comme tout contener associatif), cela ne va pas dépendre de son implémentation?
Par exemple, une map pourrai bien être un vector sous forme de heap où le tri se fait en fonction de la clef.
non?

Citation:

---

Envoyé par Mongaulois

Pour une liste ok (et encore...), Mais pour la map (comme tout contener associatif), cela ne va pas dépendre de son implémentation?
Par exemple, une map pourrai bien être un vector sous forme de heap où le tri se fait en fonction de la clef.
non?

---

Pourquoi, dans le sens où la clé reste fortement liée à... la valeur... :question:

Si la clé suit correctement les déplacements de la valeur à laquelle elle est associée, pourquoi l'itérateur ne pourrait pas rester "constant" au même titre que si on avait affaire à une liste :question:

Citation:

---

Envoyé par koala01

Pourquoi, dans le sens où la clé reste fortement liée à... la valeur... :question:

Si la clé suit correctement les déplacements de la valeur à laquelle elle est associée, pourquoi l'itérateur ne pourrait pas rester "constant" au même titre que si on avait affaire à une liste :question:

---

Dans le cas que je donne, l'iterateur correspondrai a un endroit du vecteur et lorsqu'il y as une suppression ou un ajout, il se peut que l'endroit pointer par l'iterateur ai changé et il est donc invalidé

Citation:

---

Envoyé par Mongaulois

Par exemple, une map pourrai bien être un vector sous forme de heap où le tri se fait en fonction de la clef.
non?

---

On pourrait peut-être faire un conteneur semblable à une map ainsi, mais ce ne serait pas un std::map. Dans la définition d'un std::map, il y a plusieurs niveaux :
- une spécification de l'interface fournie par ce template (le .h en gros) ;
- une spécification d'ordre plus sémantique (quelle opération invalide un itérateur, en particulier, mais aussi les effet d'un insert sur size, par exemple) ;
- des contraintes d'algorithmique (l'insertion est en O(log n)).

Une std::map doit respecter les trois niveaux.

Citation:

---

Envoyé par JolyLoic

- une spécification d'ordre plus sémantique (quelle opération invalide un itérateur, en particulier, mais aussi les effet d'un insert sur size, par exemple) ;

---

C'est dans ses spec??? alors c'est cool :D
Tu serait ou il y aurait un site qui explique cela?? j'ai pas trouvé

Je lis directement la norme.
http://cpp.developpez.com/faq/cpp/?p...tenir_standard

(Message à un gestionnaire de la FAQ qui passerait dans le coin : Il pourrait être pas mal d'ajouter un lien vers le draft de C++0x sur cette page, non ?)


Elle ne décrit pas forcément les opérations qui conservent, mais elle décrit toutes les opérations qui invalident. Par exemple :

Citation:

---

Envoyé par La norme §23.1.2.8

[Associative containers]
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.

---

Citation:

---

Envoyé par Mongaulois

Dans le cas que je donne, l'iterateur correspondrai a un endroit du vecteur et lorsqu'il y as une suppression ou un ajout, il se peut que l'endroit pointer par l'iterateur ai changé et il est donc invalidé

---

Outre que JolyLoic a donné les raisons qui font que, il faut bien penser au fait qu'un tableau associatif travaille réellement sur deux valeurs distinctes: la clé (qui sert pour le tri) et la valeur associée (quel qu'en soit le type)...

L'itérateur d'un tableau associatif est géré sur base... de la clé :P

Le seul cas dans lequel l'itérateur serait invalidé "parce qu'on a retiré un élément dans le tableau de valeurs" serait la conséquence du fait... que l'association clé/valeur a changé... ce qui est pour le moins contraire à l'idée que l'on se fait d'un tableau associatif, non :question::D

Ok pour la norme, mais ce serait bien d'avoir cela dans la FAQ par exemple :D. Si quelqu'un est motivé

Citation:

---

Envoyé par koala01

Le seul cas dans lequel l'itérateur serait invalidé "parce qu'on a retiré un élément dans le tableau de valeurs" serait la conséquence du fait... que l'association clé/valeur a changé... ce qui est pour le moins contraire à l'idée que l'on se fait d'un tableau associatif, non :question::D

---

Dans mon exemple non. Un vector de pair trié par la valeur représentant la clef (donc bien comme tu l'explique) et que l'iterateur est tout simplement un pointeur sur un element donnera un comportement indéfinie au iterateur apres un ajout ou un retrait. Même cas par trie par heap ou autre methode. Mais bon cette exemple ne suis pas la norme.
C'est dommage que se soit des comportements qui dépende du conteneur.