map :
- temps d'accès en log2(n) * K
- ordonnée (par le critère que tu veux sur les clés)
- nécéssite une relation d'ordre stric sur les clés (typiquement l'operateur< ), ayant une complexité de K (typiquement O(1))
- ne déplace pas ses nodes (ajouter/supprimer un élément n'invalide pas les autres iterateurs)
hash_map (ou unordered_map, c'est pareil)
- temps d'accés en O(1) * K en général mais O(n) dans le (rare) pire des cas.
- pas ordonnée (d'où son nom)
- nécéssite une fonction de hashage ET une fonction de comparaison (typiquement l'operateur==), ayant une complexité de K (typiquement O(1))
- peut déplacer ses nodes, ça dépend de l'implémentation. Certaines version de STLPort déplacent les nodes, mais pas celles de microsoft. Donc ajouter/supprimer un élément invalide tous les itérateurs. Le futur standard C++0x imposera de ne pas déplacer ses nodes, mais c'est pas encore appliqué.
J'introduis la compléxité K car elle est souvent négligée, mais pas négligeable. Pour une map de std::string par exemple, comparer 2 strings (avec < ou ==) est en compléxité O(m), avec m la longueur des strings. Ca peut être grand devant log2(n), et d'autant plus devant O(1). D'où l'intérêt de bien optimiser les fonctions de comparaison et de hashage. La fonction de hashage doit à la fois être performante et ne pas provoquer trop de collisions.