Discussion :

[SteelBox]

Bonjour, je cherche quelques éléments sur les performances des structures de la STL, notamment la map. Savez vous quelle strcture de données elle utilise et connaissez vous la compléxité spatiale et temporelle de cette structure. J'ai vu sur internet qu'elle serait implémentée avec une structure de hashing...

Autre question, pour stocker des éléments en vrac (c'est à dire que je ne fais aucune opération dessus à part des insertions dans la structure), le mieux est il un sac ou un vecteur ?

Merci :-)

PS : si vous avez des adresses internet, je suis fortement intéressé...

[Laurent Gomila]

Salut

Les détails d'implémentation des conteneurs ne sont pas précisés par la norme, mais la complexité requise pour leurs différentes opérations limite le champ d'investigation : typiquement les std::map sont implémentées sous forme d'arbre binaire, de type rouge et noir par exemple sous VC7.

Je n'ai pas de lien en tête, mais je pense que tu peux trouver sur le net des documents indiquant les spécifications (niveau complexité) pour chaque conteneur et ses opérations.

Pour ta seconde question, qu'est-ce qu'un sac exactement ? Sinon il faut voir où tu vas insérer tes éléments. N'importe où : std::list, en fin : std::vector, en début et fin : std::deque.

[SteelBox]

En fait, je viens de me rendre compte que je les insérais dans l'ordre. il faut donc que la structure me resorte les éléments dans l'ordre ou j'ai inséré, ce que fais le sac par exemple qui pourrait convenir. Dans ce cas, le sac doit être plus adapté que le vector, non ?

Pour les pages, je vais essayer de chercher à nouveau mais ma première recherche n'avait pas donnée grand chose (y'a pas mal de choses sur les mêmes types de structures en java par contre...)

[mat.M]

Si tu veux accéder à un élément particulier , je pense que std::vector est plus adapté que std::list.
Parce que avec std::list il faut boucler pour atteindre un élément particulier contrairement à std::vector
Si tu dois parcourir les éléments par boucle std::list est plus adapté par contre.
Faut voir

Dans ce cas, le sac doit être plus adapté que le vector, non ?

Sac je ne connais pas ; veux-tu parler de std::stack ?
http://www.sgi.com/tech/stl/stack.html
stack en anglais c'est pile ; une pile ça marche premier entré premier sorti ( First In Fisrt Out ) ou bien dernier entré premier sorti ( Last In First Outc)

[SteelBox]

Non, je ne parle pas de stack. Je connais cette structure. Je parle d'un sac, qui est un multiset avec la STL il me semble
En tout cas, je dois bien parcourir la strcture pour faire un affichage, donc list, vector ou multiset sachant qu'il n'y a que 2 opérations très simples :
- je fais des insertions à la suite et que des insertions
- ensuite j'affiche tout dans l'ordre d'insertion

[JolyLoic]

Non, le sac n'existe tout simplement pas avec la STL. Pour ce que tu décris, si tu veux conserver l'ordre d'insertion, tu dois te baser sur une séquence (vector, deque ou list, ou les versions décorées que sont stack ou queue).

Vu la description du besoin, vector me semble le plus simple.

[SteelBox]

D'accord, merci beaucoup :-)
Si quelqu'un a une page internet sur les différentes implémentations des structures de la STL (notamment la MAP), je suis preneur, car je n'ai toujours rien trouvé de vraiment intéressant.

[Laurent Gomila]

La documentation de chez SGI fournit les contraintes de complexité pour les fonctions et les conteneurs de la STL.

http://www.sgi.com/tech/stl/

En ce qui concerne les détails d'implémentation, comme je te l'ai dit cela dépend de ta STL, donc peut-être trouveras-tu des infos en allant jeter un oeil du côté de là d'où elle vient.

Sinon, avec Google et les bons mots-clés on peut trouver des choses interessantes, genre un comparatif de performance / complexité entre vector et deque sur CodeProject.

[SteelBox]

Merci, j'ai trouvé une page pas mal (c'est pas sur la map mais c'est déjà bien...)
:-)

[JolyLoic]

Même si rien n'est spécifié, tout le monde fait pareil. En gros :
vector -> Tableau alloué dynamiquement avec une taille plus grande
list -> Liste doublement chainée
deque -> Liste chainée de tableaux
Le reste -> Red/black tree