Discussion :

[koala01]

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:

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)

Merci d'avance

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

[koala01]

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é

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

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

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

[Spout]

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

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

[koala01]

[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

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 )

@JolyLoic: merci de cette précision

[Spout]

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.

[JolyLoic]

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

Oui

[yan]

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?

[koala01]

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

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

[yan]

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

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

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é

[koala01]

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é

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

[JolyLoic]

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.

[yan]

- 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
Tu serait ou il y aurait un site qui explique cela?? j'ai pas trouvé

[JolyLoic]

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 :

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