Salut,
 
J'ai un groupe d'objets individuels (environ 150 pour l'instant, leur nombre étant amené à augmenter au fil du temps), chacun défini par une "ID" comprise entre 0 et 2000. Je dois faire correspondre à chaque élément une paire d'entiers.
 
Ma question est : vaut-il mieux que j'utilise un tableau (ou un vector, sinon je vais encore me faire jeter...) de 2000 entrées dont la plupart seront initialisées à (-1,-1), ou une map dans laquelle seuls les éléments importants seront définis ? (A priori la map me semble plus logique, mais est-ce que les accès aux éléments d'une map sont aussi rapides qu'à ceux d'un tableau ? Et si le nombre d'éléments se rapproche des 2000, est-ce que le choix de la map est toujours aussi avisé ?)
 
Merci.  

c'est une question d'ensemble:
 
quelle est la nature de tes objets, comment seront-ils traités, quelle est la fréquence de recherche par un ID statique ?
 
si c'est une paire d'entier (coordonnées 2D), ça me paraitait plus efficace pour la suite de les mettre en vector si tu vas massivement les altérer, et faire "peu" de recherche par un ID.
 
enfin je sais pas il faudrait un peu plus de contexte.

Ils seront pas modifiés, ils servent juste à définir une position : le programme lit des données dans lesquelles tout est défini par rapport à l'ID, le vecteur ou la map en question ne servent qu'à faire du mapping justement, pour que les infos soient réorganisées de manière lisible par l'utilisateur.
 
En gros, j'ai des données concernant l'objet (physique, un détecteur) n°1608 (ID définie par l'électronique), le programme le transforme grâce à ce mapping pour qu'il devienne l'objet n°2-17 (représentation géométrique), ce qui est plus clair pour l'utilisateur. Le vecteur ou la map n'est donc écrit qu'une fois pour toutes au début, puis il y a un accès récursif en lecture sur tous les évènements du fichier de données.
 
J'espère que c'est plus clair... J'avoue que pour l'instant, même pour moi la manière dont je vais m'y prendre est un peu floue...  

alors a prori si tu as beaucoup de recherches par l'ID, une map<> ou hash_map peut faire l'affaire.

Ok, je vais m'engager dans cette voie alors. Merci.

std::tr1::unordered_map<>
 
Sinon t'as le droit de faire une petite surcouche qui fait en sorte que si la clef n'existe pas, ça te renvoit une valeur par défaut.

Pas beaucoup de doc pour unordered_map...  
 
Après réflexion, je pense que ce serait bien de pouvoir accéder à la fois à la valeur grâce à la clé, et à la clé grâce à la valeur. Une map réciproque quoi. Y'a un truc qui fait déjà ça tout seul ?

non.

Ok. Dernière question (je pense) :  
- mes trucs seront définis une fois pour toutes au début et souvent accédés en lecture
- je veux pouvoir accéder à une paire d'int (disons "Z" ) grâce à une ID
- je veux pouvoir accéder à une ID grâce à une paire d'int (à "Z" )
 
Est-ce qu'il vaut mieux :
- un multi_index genre <ID, Z, pair < ID, Z > > (désolé pour la syntaxe, j'ai pas encore trop lu la doc de multi_index, mais cette représentation me semble intuitive...)
- deux maps : <ID,Z> et <Z,ID>
- (autre chose ?)
 
Je pense qu'il vaut mieux deux maps. J'ai bon ?
 
Edit : Ouais, je vais faire comme ça, ça m'a l'air bien. Merci !  

 
J'ai cru comprendre que dans le cas du tableau l'ID était l'index de l'élément dans le tableau.
 
Si la mémoire n'est pas un problème, et avec 2000 éléments de 2 entiers ce n'est pas le cas, un tableau sera plus performant.  
 
La map garanti un acces constant en recherche (comme un tableau dont l'index correspond à la clé de la map) sauf que le traitement dans le cas de la map est plus lourd. Ce sera un temps constant genre de 1 instruction machine pour le tableau, 20 instruction machine pour la map voire peut être 100 pour la map.
 
Pour pouvoir accéder rapidement aux 2 données ils vaut mieux avoir 2 moyens d'accès (2 maps dans ton exemple).
 
 
Par contre si la performance n'est pas un problème critique pour toi, je commencerais à ta place par définir une classe encapsulant se service avec une fonction membre pour accéder à un objet par son ID et une fonction membre pour accéder à un objet par sa paire d'int (Z).
 
Tu prend ensuite l'implémentation la plus simple pour toi et voila.
 
Si jamais des problème de perfs surviennent tu peux toujours changer l'implémentation par la suite.

Un multi_index ça n'existe pas. Sauf si tu arrives à déterminer une fonction d'indexage qui donne le même index pour ta clef et sa valeur associée. Soit tu fais deux maps. Soit juste une seule et sur l'un des types d'accès, tu fais une recherche séquentielle.

Oui, c'est ça.
 

Ah... Dans ce cas, il vaudrait mieux deux vecteurs, non ? Un simple pour l'accès ID->Z et un double pour Z->ID.
 

Si si, ça l'est, et pas qu'un peu...  
 

http://www.boost.org/libs/multi_in [...] orial.html  
 

nan mais conceptuellement, tu ne peux pas indexer à la fois sur 2 trucs, sinon tu mélangerais 2 espaces de nommage. Après qu'il y a des implémentations pour faire comme si, je dis pas.

 
Le vecteur double fait gaffe, faut vraiment que tu ai un nombre de valeurs possible limité.
 
Sinon très rapidement ton tableau devient énorme.
 
Au fait c'est que pour de la lecture seule ? Aucune modification de tes données ?
 
 
Pour optimiser les performances, tu fait ton programme et tu mesure le temps qu'il met pour effectuer la tache que tu lui à confiée... Tu essaye alors une piste d'optimisation et tu mesure à nouveau pour les mêmes données et le même calcul. Tu continue itérativement jusqu'à obtenir des performances qui te conviennent. Mais on peut pas aller trop loin dans les suppositions sur les performances tant que l'on as pas codé effectivement le programme et testé. Une solution parraissant plus lente peut très bien être plus rapide dans la pratique car mieux optimisée par le compilateur ou exploitant mieux les capacité du processeur.

 
Conceptuellement un truc peut très bien être un objet composé et tu peux toujours indexer. Les seules choses dont tu as besoin c'est d'un moyen de tester l'égalité 2 valeur du même type et de définir des groupe disjoint qui regroupés constituent l'ensemble des valeurs possible de ton type.
 
Genre imaginons tu veux indexer un type dont les valeur possible sont A, B, C, D, E et F
 
tu crée trois groupe :  
 
groupe 1 : {A, F, C}  
groupe 2 : {D}  
groupe 3 : {E,B}
 
Tu indexe chaque valeur en fonction du groupe auquel elle appartient. C aura l'index 1 et E l'index 3.
 
C'est le principe sur lequel repose les maps justement. Bien sûr tout l'art est sur la méthode de regroupement. En général il faut choisir un façon rapide de calculer le groupe d'un élément mais aussi assurant une répartition intéressante de façon à ce que les éléments que tu place dans ta map soient répartis de façon à peu près homogène dans chaque groupe. Y'a même des thèse là dessus !
 
 

Dans ton appli, très simple puisque tes données sont fixées une fois pour toutes au démarrage, le vecteur de taille 2000 est de loin l'option la plus performante et ne pose pas de pb particulier: 1 instruction machine

Pour la réciproque, tu fais un tableau de pointeurs indexé par le 1er chiffre (2 dans ton exemple), le pointeur pointant sur le début d'un tableau pour lequel le 2e chiffre (17) te donne l'index qui contient l'ID, et voilà: 2 instructions machine.
Dans les 2 cas, tu ne pourras pas faire plus rapide que ça.