STL : Vector, Deque ou Map ?

Signaler
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011
-
jul39dole
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011
-
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 !

7 réponses

Messages postés
14851
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
6 avril 2020
91
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
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011

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)).
Messages postés
14851
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
6 avril 2020
91
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
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011

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" ?
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
5
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.
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011

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 ?
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011

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;

?