STL : Vector, Deque ou Map ?

Question

Bonjour,

Je ne sais pas trop quoi choisir comme conteneur... Voici mon problème : j'utilise un vector, chaque case du vector contient un set. Le problème est que je n'utilise pas toutes les cases du vecteur de manière contigu : par exemple, je peux utiliser la case 0, 1, 2, 3, puis passer à 15, 16, puis 112... par exemple. Utiliser un vecteur reviendrai à réserver 112 cases pour seulement 7 utilisées ? Un Deque fait-il cela ? Une Map semble intéressante, mais l'accès est moins rapide (en log(n) je crois, contre n pour un vecteur).

Autre question, dans le cas où j'utiliserai un Vector, si j'ai besoin de réserver énormément de mémoire (par exemple quelques centaine de  Mo), est-ce que la fonction peut échouer s'il n'y a pas assez d'espace contigu en RAM, ou est-ce qu'il y a découpage automatique (ce qui serait plutôt la fonction d'un Deque...) ?

Enfin, est-ce qu'un Set vide utilise beaucoup de mémoire ?

D'avance merci !

BunoCS · Answer

Yop!
Quel est ton besoin exactement? Est-il vraiment nécessaire d'avoir des "trous"?
Si tu veux faire le lien entre un index et un set, je te conseille d'utiliser une map.

Pour info, log(n) < n 

Buno
----------------------------------------
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
Le site de mon mariage

jul39dole · Answer

Oui il y aura forcément des trous, en fait, l'indice correspond au temps, et le contenu à un évènement. Et il n'y arrive pas tout le temps des évènements... d'où les trous!
En effet, log(n) < n, mais je me suis trompé, un vecteur est en ordre 1... et O(1) < O(log(n)).

BunoCS · Answer

Je ne suis pas trop pour un vecteur avec des trous car c'est source de bugs, je préfère la map.

Buno
----------------------------------------
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
Le site de mon mariage

jul39dole · Answer

D'accord merci. Au pire je pourrai faire des tests de performances si avec la Map c'est beaucoup trop lent... Je préfère sacrifier de la mémoire plutôt que du temps de calcul !

Et le Deque ne permet pas une bonne gestion du genre "vector avec des trous" ?

luhtor · Answer

Tu as aussi les stdext::hash dans les extensions de la STL qui sont bcp plus rapides que les std::map. Mais attention, ca risque de consommer plus de mémoire.

jul39dole · Answer

Ah oui une hash peut être intéressante. Mais il me semble qu'il faut une fonction de hashage pour les éléments contenus. J'espère qu'il en existe une pour les set<...>. Par hasard, aurais-tu un lien de documentation au sujet des stdext:hash ?

jul39dole · Answer

Soit une classe Evenement. A votre avis, l'accès à un élément via la fonction find est plus rapide dans le cas :
1- map> evt;

ou dans ce cas là :
2- multimap evt;

?

STL : Vector, Deque ou Map ?

7 réponses

Votre réponse

Discussions similaires