Discussion :

[Invité]

Tout est dans le titre...

Pour moi un multimap, c'est soit un multiset de paires, soit un vecteur trié de paires... (on pourrait d'ailleurs s'interroger sur l'utilité du multiset, soit dit en passant, mais bon...)

L'intérêt de la map, qui est la capacité de récupérer par [] est absente du multi map, et les interfaces et leurs garanties sont les mêmes que pour le multiset, et pour le vecteur + algorithmes sur conteneurs triés.

Alors, à votre avis, les multimaps, ca sert à quoi (sinon à préserver la symétrie avec les set...)?

Francois

[Klaim]

Naivement, je dirais que la recherche sur une clée dans une map est globalement plus efficace que dans le cas des alternatives que tu donnes?

[Laurent Gomila]

Quand la valeur est séparée de sa clé, on peut la modifier sans risquer d'invalider l'ordre dans le conteneur (donc sans avoir à retirer l'élément, le modifier puis le réinsérer).

[Invité]

Quand la valeur est séparée de sa clé, on peut la modifier sans risquer d'invalider l'ordre dans le conteneur (donc sans avoir à retirer l'élément, le modifier puis le réinsérer).

Ca ne serait pas pareil avec un vector de paires?

Imaginons qu'on ait un vector<pair<clef,valeur> >, trié par clefs, avec des ex aequos (comme un multimap). Je peux à tout moment modifier les valeurs (v[i].second) sans remettre en cause l'ordre des clefs. En terme de complexité, c'est exactement le même travail que pour un multimap : une recherche "triée" (lg(N)+M, M nb d'ex aequos) pour trouver l'élément, et une affectation.

Pour un multiset, je suis d'accord. Pour avoir une structure équivalente, il faudrait ajouter aux éléments du multiset un pointeur vers une "zone valeur" modifiable.

Francois

[Laurent Gomila]

vector et multimap ne représentent pas la même structure de donnée, même si on peut avoir une recherche en ln(n) avec un vector trié il reste des différences sur les autres opérations, comme l'insertion ou la suppression par exemple.

[camboui]

Petit aperçu des containers de la stl ici http://www.cplusplus.com/reference/stl/
Il y en a un autre dans la faq du forum.

Je n'utilise pas l'operator[] avec std::map mais il est vrai qu'on peut se demander pourquoi il n'a pas été laissé aussi dans (multi)set et multimap.

[Invité]

Petit aperçu des containers de la stl ici http://www.cplusplus.com/reference/stl/

Cette table est un peu trompeuse, car elle fait abstraction des algorithmes de la stl, qui sont à la base de l'utilisation des vector triés.

Je n'utilise pas l'operator[] avec std::map mais il est vrai qu'on peut se demander pourquoi il n'a pas été laissé aussi dans (multi)set et multimap.

Ca, je sais...

Pour les sets : comme le conteneur ne contient que la clef, [] n'a aucun intéret : set[element] renverrait ... element. Et modifier un élement par
set[element]=nouvel_element serait très étrange.

Pour les multimap : le problème serait ce que devrait renvoyer [] puisque par définition il peut y avoir plusieurs valeurs d'une même clef. multimap[i]=j; ca donnerait quoi?

En gros, l'opérateur [] renvoie une référence sur un élément, que l'on trouve à partir d'une "clef". Dans un vector<>, la clef est la position (le rang dans le vector), dans une map<>, la clef est ... la clef.

Dans une list<>, il n'y a pas de clef, dans un set<>, il n'y a rien à renvoyer d'autre que la clef, et dans un multimap<> l'élement à renvoyer n'est pas forcément unique...

Francois

[3DArchi]

Salut,
Juste un complément pour (re)contextualiser : cette discussion fait suite à la fin de celle-ci.
@camboui: [] dans un multimap retournerait quoi lorsque tu as des doublons ? J'aurais presque tendance à me demander pourquoi il y a encore un find dans multimap alors que dans la plus part des cas on aura besoin d'un equal_range. Le find joue juste un rôle de type : existe-t-il au - une clé avec cette valeur.

@françois : je dirais que l'intérêt de map/multimap n'est peut être pas à rechercher dans la performance mais tout simplement dans le service fourni. Certes un vecteur sur une paire et trié peut avoir les mêmes ou de meilleurs perfs qu'un map, mais si on ne les cherche pas, alors le map offre une abstraction clé en main (si j'ose dire). Pour parler strictement du multimap, ben, je suis sec. Car j'avoue n'avoir jamais eu ce besoin.

[Invité]

Salut,

@françois : je dirais que l'intérêt de map/multimap n'est peut être pas à rechercher dans la performance mais tout simplement dans le service fourni. Certes un vecteur sur une paire et trié peut avoir les mêmes ou de meilleurs perfs qu'un map, mais si on ne les cherche pas, alors le map offre une abstraction clé en main (si j'ose dire). Pour parler strictement du multimap, ben, je suis sec. Car j'avoue n'avoir jamais eu ce besoin.

Map, je vois bien son utilité (je pense qu'elle est souvent utilisée à tort, mais ce n'est pas la question). C'est multimap qui m'intéresse ici.

En fait, à chaque fois que je l'ai utilisé, c'était comme "conteneur auto triant", en gros, tu ajoutes des éléments dans le multimap, et tu es sur qu'en fin de compte ils seront triés par clef croissante. Après, tu peux récupérer par lower_bound() ou equal_range(), ou simplement énumérer pour parcourir dans l'ordre.

Maintenant, l'apport vs un vector<> de paires triées n'est pas clair pour moi. En fait, à chaque fois que j'ai utilisé multimap en situation "sérieuse" (avec de gros volumes de données), j'ai fini par le remplacer par un vector (parce qu'il n'y avait pas photo en vitesse, on parle d'un facteur au moins 30%, parfois davantage si les volumes sont très gros et flirtent avec la mémoire disponible)

Le seul cas que j'imagine serait celui où l'on a effectivement besoin d'un conteneur toujours trié pour des recherches, mais où celui ci se construit par petits bouts, au fil de l'exécution du programme, comme une sorte de cache, si tu veux. Ca me parait une utilisation assez exceptionnelle surtout dans le cas d'un conteneur ayant des doublons, comme multimap.

Francois

[Lavock]

Les avantages claires d'une multimap sont :
Les insertion/suppression unitaire;
Les insertion/suppression de champs contigu (trié pour l'insertion).


Ou, en gros, tout les truc ou il n'est pas nécessaire de faire plusieurs tris recherches. De plus, il y a une petite optimisation intéressante au cas ou tu as déjà un itérateurs pas trop loin de la zone d'arriver pour l'insertion.

[edit] oula, fatigué moi Oo

[camboui]

@camboui: [] dans un multimap retournerait quoi lorsque tu as des doublons ? J'aurais presque tendance à me demander pourquoi il y a encore un find dans multimap alors que dans la plus part des cas on aura besoin d'un equal_range. Le find joue juste un rôle de type : existe-t-il au - une clé avec cette valeur.

Arf, je savais pas ce que faisait l'operator[]... ben oui puisque je l'ai jamais utilisé
Je pensais naïvement que operator[] prenait un size_t comme paramètre pour permettre un accès ordinal. Du coup, puisque ce n'est pas le cas, je me dis que ça manque peut-être dans les set/map.

Sinon, ben ça pourrait faire l'équivalent d'un find ou d'un lower_bound (ces deux font d'ailleurs la même chose me semble-t-il).

[Arzar]

Bon, allez, je me dévoue pour consacrer une fois de plus la Grande Loi "Plus une discussion sur Developpez.Forum.C++ dure longtemps, plus la probabilité d'y trouver une mention de boost s'approche de 1"

@françois : je dirais que l'intérêt de map/multimap n'est peut être pas à rechercher dans la performance mais tout simplement dans le service fourni. Certes un vecteur sur une paire et trié peut avoir les mêmes ou de meilleurs perfs qu'un map, mais si on ne les cherche pas, alors le map offre une abstraction clé en main (si j'ose dire).

Boost::flat_map !
Une abstraction "clé en main" d'un vecteur de paire, avec toute la commodité de l'interface d'une map et toute l'efficacité de la contiguïté d'un vecteur.

Pour ce qui est de l'utilité des multimap... ben, c'est vrai que je ne suis jamais trouvé dans un cas où une multimap conviendrait parfaitement. Elles ont peut-être été ajouté au standard surtout dans un souci d'exhaustivité ?

[Invité]

Sinon, ben ça pourrait faire l'équivalent d'un find ou d'un lower_bound (ces deux font d'ailleurs la même chose me semble-t-il).

Pas tout à fait...

Si la valeur recherchée existe dans la multimap, find() renvoie un itérateur vers "un des" éléments ayant cette clef, lower_bound() vers la première occurence de la clef.

Si la valeur recherchée n'est pas dans la multimap, find renvoie l'itérateur end(), lower_bound() le première valeur supérieure à l'élément (et donc le point d'insertion si l'on veut ajouter la valeur)

lower_bound() en fait donc "un peu plus" que find(), et find() est un peu plus rapide (quelques comparaisons en moins).

Francois

[Emmanuel Deloget]

Salut,

Map, je vois bien son utilité (je pense qu'elle est souvent utilisée à tort, mais ce n'est pas la question). C'est multimap qui m'intéresse ici.

En fait, à chaque fois que je l'ai utilisé, c'était comme "conteneur auto triant", en gros, tu ajoutes des éléments dans le multimap, et tu es sur qu'en fin de compte ils seront triés par clef croissante. Après, tu peux récupérer par lower_bound() ou equal_range(), ou simplement énumérer pour parcourir dans l'ordre.

Maintenant, l'apport vs un vector<> de paires triées n'est pas clair pour moi. En fait, à chaque fois que j'ai utilisé multimap en situation "sérieuse" (avec de gros volumes de données), j'ai fini par le remplacer par un vector (parce qu'il n'y avait pas photo en vitesse, on parle d'un facteur au moins 30%, parfois davantage si les volumes sont très gros et flirtent avec la mémoire disponible)

Je ne me premetrais pas de dire que tu as tort, principalement parce que tu as probablement raison, mais j'avoue que je suis perplexe : Supposons que j'ai une multimap de 2,00,000 éléments et un vecteur trié de paires contenant les même éléments. Il me parait évident que l'insertion d'un élément dans la multimap sera plus rapide que l'insertion dans le vecteur de paires - la complexité algorithmique est la même, mais une insertion au milieu du vecteur risque de provoquer une copie des données.

Ah oui - tu traite ce point juste en dessous (promis, j'ai même pas pris le temps de lire le post en entier ; tu as le droit de me flageller...)

Le seul cas que j'imagine serait celui où l'on a effectivement besoin d'un conteneur toujours trié pour des recherches, mais où celui ci se construit par petits bouts, au fil de l'exécution du programme, comme une sorte de cache, si tu veux. Ca me parait une utilisation assez exceptionnelle surtout dans le cas d'un conteneur ayant des doublons, comme multimap.

Francois

Pas tout à fait d'accord sur l'exceptionalité (mot compte triple) du cas d'utilisation : à mon avis, il n'est pas plus rare que ton cas d'utilisation. Certains programmes doivent traiter des monceaux de donnée qui vont en grandissant. C'est (par exemple) le cas pour toute une classe de simulateurs industriels, des logiciels d'analyse en temps réel, etc.

De fait, la structure des map<> et multimap<> ont un intérêt - personnellement, j'utilise des std::map<> comme si il en pleuvait.

J'ajouterais que si tu est dans un cas d'utilisation où toutes tes données sont renseignées dans ton conteneur avant de faire des requêtes sur ces données, tu es dans un cas ou il serait peut-être plus intéressant d'utiliser un allocator spécifique plutôt que de redévelopper un adapteur map/multimap autour de std::vector<>. Tu peut ainsi avoir le meilleur des deux mondes (contiguité des données), sans pour autant passer trop de temps à débugger tes algorithmes. Je pense qu'en termes de temps de développement / debug, il y a un gain certain à voir du coté des allocator plutot qu'à redévelopper des algorithmes qui peuvent, pour certains, être relativement complexes (enfin bon, peut être pas dans ce cas précis ; mais tu vois où je veux en venir...).

[Invité]

J'ajouterais que si tu est dans un cas d'utilisation où toutes tes données sont renseignées dans ton conteneur avant de faire des requêtes sur ces données, tu es dans un cas ou il serait peut-être plus intéressant d'utiliser un allocator spécifique plutôt que de redévelopper un adapteur map/multimap autour de std::vector<>.

Je me rends maintenant compte que j'aurais du commencer par là...

En fait, il n'y a rien à redévelopper. Les algorithmes de la STL fournissent tout ce qu'il faut pour travailler sur des vecteurs triés. Voire, leur interface est plus complète que celle des multimaps.

Tu disposes ainsi :
- d'une recherche d'existence "binary search"
- de recherches d'éléments lower_bound, upper_bound, equal_range, qui déterminent la position d'insertion dans le cas d'absence du conteneur

Bref, tout ce qui manque (tant qu'on n'a ni insertions ni suppressions), c'est la simplicité de l'expression [] pour les maps, mais comme elle n'existe pas pour les multimaps.

Mais on dispose en échange d'un conteneur contigu, donc des iterateurs à accès aléatoire, un calcul de distance() instantané, moins d'empreinte mémoire...

Je suis partiellement d'accord avec toi pour les maps. Mon problème demeure pour les multimaps...

Francois

[camboui]

Pour ceux qui cherchent la performance des vector triés sans sacrifier l'insertion/suppression le B+tree mérite le coup d'oeil http://idlebox.net/2007/stx-btree/
Je pense qu'il n'y a pas mieux comme conteneur générique sur disque. Ici on a voulu transposer son efficacité en bénéficiant de la pagination de la mémoire en cache CPU. D'après son auteur avec succès.

[Invité]

Pour ceux qui cherchent la performance des vector triés sans sacrifier l'insertion/suppression le B+tree mérite le coup d'oeil http://idlebox.net/2007/stx-btree/
Je pense qu'il n'y a pas mieux comme conteneur générique sur disque. Ici on a voulu transposer son efficacité en bénéficiant de la pagination de la mémoire en cache CPU. D'après son auteur avec succès.

Ca c'est une réimplémentation des map et des set, utilisant un système d'arbre différent des habituels Red-Black trees. On se retrouve avec les mêmes garanties algorithmiques, mais, si j'en crois l'auteur, une empreinte mémoire et un coefficient dominant plus faible. Je n'ai pas (encore) lu le papier, mais ca ressemble de loin aux arbre n-aires (généralement ternaires) balancés décrits dans la littérature (Knuth ou Sedgewick). On améliore marginalement les performances (pour des valeurs de N assez grandes) en échange d'une implémentation plus complexe.

Il y a pas mal de possibilités d'implémentations pour les composants triés de la STL. On utilise traditionnellement les RB tree, mais je ne crois pas que ce soit une obligation.

Maintenant, ca reste un arbre on n'a pas la contiguité, ni l'accès aléatoire d'un vector. Et, en terme de vitesse, je crois que la présence d'un arbre (et donc la nécessité de le parcourir lors de toute recherche) plombera les performances (par rapport au vector)

La question que je me pose, ce sont les tables de hachage... A priori c'est plus efficace qu'un vector et qu'une map en recherche (temps constant, ou quasiment), c'est plus rapide qu'une map en insertion/suppression. Par rapport au vector, ca prend un peu plus de place (encore que, si les données sont vraiment mortes, on pourrait imaginer un hachage parfait sans overhead), mais probablement moins qu'un arbre.

Ce qu'on sacrifie, c'est la possibilité de le parcourir "dans l'ordre", c'est à dire la notion de tri.

Francois