Un conteneur associatif qui conserve l'ordre d'insertion ?

Bonsoir

Je suis actuellement en train de créer une classe qui possède des instances d'une autre classe. Mon problème est que je dois pouvoir accéder à ces instances de deux manières qui semblent a priori contradictoires :
- accès par clé textuelle (comme pour une map)
- parcours des objets dans l'ordre dans lequel ils ont été insérés (comme pour un vector)

Pour faire ça, la seule solution que j'ai trouvée est de dénormaliser : j'ai une map et un vector qui évoluent en même temps. Le vector contient les objets eux-même, la map associe des clés textuelle à des pointeurs vers les objets contenus dans le vector. Je précise que seule l'opération push_back est utilisée sur le vecteur, les pointeurs vers ses objets restent donc valides (enfin je crois 8O )

J'aurais voulu savoir s'il existait une manière plus élégante (et moins risquée !) de faire ça, avec une seule et même classe ? Est ce que quelque chose est prévu pour ça dans la STL ?

Merci d'avance :)

Le sujet a déjà été débattu une ou deux fois sur ce forum, et en gros il n'y a pas de solution miracle.

Tu peux gerer une liste de paires <id, objet>, avec une petite fonction qui va bien pour retrouver l'objet qui correspond à un id donné rapidement.

Tu as aussi des variantes de ta solution : tu stockes non pas des pointeurs (car push_back les invalide, la mémoire peut être réallouée ailleurs s'il n'y a plus de place) mais des indices. Ou alors tu peux stocker dans ta map des paires <objet, ordre initial>.

A noter que tu peux utiliser std::list si tu ne veux pas que tes pointeurs soient invalidés, là tu pourras garder ta méthode.

Citation:

---

Envoyé par Loulou24

(car push_back les invalide, la mémoire peut être réallouée ailleurs s'il n'y a plus de place)

---

Argloups ! Mais c'est une trrrès mauvaise nouvelle que tu m'apprends là :)... bon en même temps je m'en doutais.

Bon... j'ai pas trop l'habitude de manipuler les pair et les sort, mais j'ai cherché un peu et si j'ai bien compris je dois définir ma map de cette façon :

Code:

---

1 2 3 4

typedef pair<MonObjet, map::size_type> pair_type; typedef map<string, pair_type> map_type   map_type maMap;

---

Suite à quoi, pour insérer un objet dans ma map en étant sûr d'incrémenter à chaque fois le nombre indiquant l'ordre, je peux faire :

Code:

---

maMap["une clé"] = pair_type(unObjet, maMap.size())

---

... vu que maMap.size() sera à chaque fois plus grand de 1... ça tient la route jusque là ? :roll:

Bon... si j'ai bien compris pour pouvoir faire un tri j'ai juste à définir l'opérateur de comparaison qui va bien :

Code:

---

inline bool operator< (const pair_type&, const pair_type&)

---

Là je commence vraiment à pas être sûr... pour faire le tri, j'ai plus qu'à faire ça ?

Code:

---

sort(maMap.begin(), maMap.end());

---

Et après hop je parcours de maMap.begin() à maMap.end() et j'ai mes objets dans l'odre ? :? :?
Grosse grosse incertitude là...

Boost fourni un conteneur pour ce genre de choses, mais je n'ai pas personnellement essayé, donc je ne peut pas en dire beaucoup plus. J'avais lu un article dessus dans un CUJ, et ça avait l'air pas mal.

http://www.boost.org/libs/multi_index/doc/index.html

OK merci pour l'info. On essaie d'éviter le plus possible les dépendances envers des librairies externes, mais ça fait plusieurs fois que Boost propose une classe qui pourrait nous aider. J'ajoute celle-ci à la liste et si elle devient imposante, peut-être adopterons nous cette librairie.

qu'est-ce qui empêche d'utiliser la solution vector / map ?
Tu utilises le vector quand tu veux accéder à un pointeur séquentiellement, et le map quand tu veux y accéder par clé...
Et pour l'insertion d'un nouvel objet, tu crées une fonction qui s'occupe de rajouter le pointeur dans le vector et le map, comme ça tu conserves la cohérence des deux. Si tu t'assures que ton vector et ton map sont en privé, tu es sûr que personne ne viendra bidouiller dedans, et donc passera par les fonctions d'accès que tu définies.

Qu'est-ce que tu veux dire Loulou par "la mémoire peut-être réallouée" ?
quand on déclare un vector sur des pointeurs, ça revient à faire une collection de nombres entiers, parce qu'après tout, un pointeur c'est juste un nombre entier ?
Je me trompe surement, mais j'aimerai bien comprendre...

Citation:

---

Envoyé par tut

Qu'est-ce que tu veux dire Loulou par "la mémoire peut-être réallouée" ?
quand on déclare un vector sur des pointeurs, ça revient à faire une collection de nombres entiers, parce qu'après tout, un pointeur c'est juste un nombre entier ?

---

Oui mais mon vector ne stocke pas des pointeurs mais les objets eux-mêmes. Tout simplement pour ne pas avoir à gérer la désallocation. Donc il faut stocker (si j'ai bien compris) des itérateurs dans la map plutôt que des pointeurs.

Cette solution me convient tout à fait, je ne sais pas encore laquelle des 2 je vais choisir mais j'aurais déjà voulu savoir si mon pseudo code pour la solution avec juste une map était correct ? Pour la solution map/vector je suis à peu près sûr de moi.

Citation:

---

Oui mais mon vector ne stocke pas des pointeurs mais les objets eux-mêmes. Tout simplement pour ne pas avoir à gérer la désallocation. Donc il faut stocker (si j'ai bien compris) des itérateurs dans la map plutôt que des pointeurs

---

Des indices, pas des itérateurs (itérateurs et pointeurs ce serait pareil dans ton cas). Ainsi même si l'élément numéro 50 est réalloué ailleurs, ce sera toujours l'élément numéro 50.

Citation:

---

Cette solution me convient tout à fait, je ne sais pas encore laquelle des 2 je vais choisir mais j'aurais déjà voulu savoir si mon pseudo code pour la solution avec juste une map était correct ? Pour la solution map/vector je suis à peu près sûr de moi.

---

Le tri n'est pas bon. La map est naturellement triée selon ses clés (et non ses valeurs), et de toute façon elle n'est pas prévue pour être utilisée avec std::sort. Une solution peut être de copier tes éléments dans un tableau (dimensionné correctement) à l'indice auquel ils sont associés. Ensuite tu parcours ton tableau dans l'ordre.

Citation:

---

Envoyé par Loulou24

Citation:

---

Oui mais mon vector ne stocke pas des pointeurs mais les objets eux-mêmes. Tout simplement pour ne pas avoir à gérer la désallocation. Donc il faut stocker (si j'ai bien compris) des itérateurs dans la map plutôt que des pointeurs

---

Des indices, pas des itérateurs (itérateurs et pointeurs ce serait pareil dans ton cas). Ainsi même si l'élément numéro 50 est réalloué ailleurs, ce sera toujours l'élément numéro 50.

---

Ah OK j'avais pas vu ça comme ça... J'avais à l'idée que les opérations sur des conteneur n'invalidaient pas les itérateurs obtenus au préalable.

Je vais opter pour cette méthode car celle qui consiste à passer par un tableau me semble moins élégante...

Merci pour l'aide ! ;)

Citation:

---

Ah OK j'avais pas vu ça comme ça... J'avais à l'idée que les opérations sur des conteneur n'invalidaient pas les itérateurs obtenus au préalable.

---

Il faut toujours avoir en tête ce que le conteneur fait en interne quand on lui fait faire telle ou telle opération. Pour agrandir un tableau il n'y a pas de miracle : il peut être nécessaire de l'allouer ailleurs si la place manque.

Par contre pour std::list aucun problème. Une fois qu'un noeud est alloué il ne bouge plus. A moins que tu aies vraiment besoin d'un accès indicé ?

Citation:

---

Envoyé par Loulou24

Il faut toujours avoir en tête ce que le conteneur fait en interne quand on lui fait faire telle ou telle opération. Pour agrandir un tableau il n'y a pas de miracle : il peut être nécessaire de l'allouer ailleurs si la place manque.

---

En fait je pensais naïvement qu'un mécanisme du style design pattern Observer existait en le vector et ses itérateurs... Mais c'est vrai que niveau perfs ce serait assez limite :)

Citation:

---

Envoyé par Loulou24

Par contre pour std::list aucun problème. Une fois qu'un noeud est alloué il ne bouge plus. A moins que tu aies vraiment besoin d'un accès indicé ?

---

OK je vais plutôt opter pour une list, en fait j'y pensais plus... ça ne pose pas de gros problème de perfs par rapport aux vector ? (sachant qu'on ne fait qu'ajouter, rien d'autre)

L'ajout en fin se fait aussi rapidement dans une liste que dans un vector (temps constant), donc no souci.