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.