Discussion :

[Magon]

Bonjour à toutes et à tous, c'est mon premier message et je suis novice en C++, donc merci pour votre indulgence,

J'ai pour objectif d'optimiser l'espace mémoire occupé par mes structures de données. En même temps je veux créér un tableau associatif.

Je veux savoir si un map occupe plus d'espace qu'un vecteur si les cellules des deux structures contiennent un même type de données et que les indices du map sont de type int.

Si tel est le cas, est ce quedeux vecteurs, l'un contenant les indices et l'autres les données, occupent plus d'espace qu'une map.

Merci pour votre aide

[Swoög]

ça dépend de l'implémentation de la STL que tu utilises (propre à chaque compilateur)

cependant, dit-toi bien que les map ont étées optimisées pour être utilisées comme des tableaux associatifs, si tu as besoin de faire un tableau associatif, utilise une map...

[Magon]

Merci swoög,

J'utilise dev-c++ et donc gcc.

La taille occupée par la structure est primordiale pour moi.

En fait je suis entrain d'implémenter un arbre B+. La taille des noeuds internes doit être allignée sur la taille d'une ligne de cache. Un noeud contient un tableau associant une clé de recherche à un pointeur vers un noeud fils du niveau suivant. Si j'utilise une map et que celle-ci occupe deux fois la taille d'un simple tableau de clés, je préfère utiliser un tableau de clés et stocker les nouds fils du niveau suivant de manière contigu. De cette manière d'une part chaque noeud interne conteint deux fois plus de clés que si j'utilisai une map et d'autre part la recherche reste correcte puisque si une recherche doit se porsuivre dans le noeud fils numéro n, je me pointe sur le premier fils et je fais n sauts (à la manière se seek).

[Laurent Gomila]

A ta place j'utiliserais un std::vector<std::pair<int, Noeud*> > ; voire un std::set ou std::multiset si les noeuds sont triés.

Ensuite faut voir si la structure utilisée pour stocker les noeuds est conforme aux coûts logarithmiques des différentes opérations sur les arbres B+. Par exemple avec std::map ou std::set tu as une recherche en temps logarithmique pour les noeuds ; avec std::vector tu as une recherche linéaire.

[Swoög]

Si la taille est vraiment primordiale pour toi, alors il vaut mieux passer par des types que tu peux parfaitement controller (c'est à dire des classes perso, optimisée)... mais j'ai peur que ça soit alors moins optimisé que la STL...

ensuite à toi de voir... je pense qu'un vecteur prendra moins d'espace qu'un MAP... pour deux vecteurs, c'est pas sûr, mais je pense quand même que ce sera le cas... mais c'est à toi de voir si le rapport taille/temps de recherche est toujours aussi bon

[Luc Hermitte]

Si le contenu du vecteur est stable dans le temps, il y a toujours moyen de le trier une fois, et de faire ensuite les recherches avec std::equal_range.