Ordre des éléments d'une map<int, string>

Version imprimable

16/02/2011, 21h15
jamsgoodon

Ordre des éléments d'une map<int, string>

Bonjour,

Je souhaite associer à chaque clef d'une map l'ordre dans lequel il apparait dans l'ordre de la suite des clefs de la map.

Par exemple pour la première clef j'associe la valeur 1, pour la deuxième clef j'associe le valeur 2 etc...

Sachant que les clefs d'une map sont classées par ordre croissant, puis-je accéder directement à l'ordre de chaque clef ou dois je faire l'association?

Merci d'avance.

J'ai rien compris :koi:

Citation:

Je souhaite associer à chaque clef d'une map l'ordre dans lequel il apparait dans l'ordre de la suite des clefs de la map.

Désolé, pour moi c'est du charabia. "l'ordre dans lequel il apparait dans l'ordre de la suite des clefs de la map" !?? Déjà c'est qui ou quoi "il" dans cette phrase ?

Citation:

Par exemple pour la première clef j'associe la valeur 1, pour la deuxième clef j'associe le valeur 2 etc...

Dans une std::map<int, std::string> la clé c'est l'int, la valeur c'est la string. Tu ne peux pas affecter 1 ou 2 à une string...

Citation:

Sachant que les clefs d'une map sont classées par ordre croissant, puis-je accéder directement à l'ordre de chaque clef ou dois je faire l'association?

Qu'est-ce que ça veut dire "accéder directement à l'ordre de chaque clef" ?

Si tu veux accéder à la n-ième paire [clé, valeur] de la map alors il faut passer par les itérateurs :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <string> #include <map> #include <iostream> int main() { std::map<int, std::string> m; m[1] = "toto"; m[2] = "titi"; m[3] = "tutu"; int n = 3; // std::next dispo uniquement sur les compilateurs récents std::map<int, std::string>::iterator it = std::next(m.begin(), n -1); std::cout <<it->first << " : " << it->second << "\n"; // si std::next n'est pas présent il reste toujours std::advance std::map<int, std::string>::iterator it2 = m.begin(); std::advance(it2, n -1); std::cout <<it2->first << " : " << it2->second << "\n"; // les deux méthodes précédentes sont équivalentes à : std::map<int, std::string>::iterator it3 = m.begin(); for(int i = 0 ; i < n - 1; i++) { it3++; } std::cout <<it3->first << " : " << it3->second << "\n"; }
(Ce qui revient en fait à faire un parcours en profondeur de l'arbre binaire sous-jacent à std::map)

17/02/2011, 00h08
Invité

Tu as aussi la fonction distance(), qui renvoie le nombre d'éléments entre deux itérateurs sur un conteneur. Donc quelque chose comme

Code:

distance(mamap.begin(),monelement);

(monelement est un itérateur sur l'élément que tu veux...)

renverra 0 pour le premier élément, 1 pour le second, etc... En terme de code, c'est exactement comme ce qu'écrit Arzar, mais cela marchera avec n'importe quel conteneur (quel que soit le type de ses éléments).

Ceci appelle deux remarques :

1- l'appel à distance() parcourt la map, ce n'est donc pas une fonction très rapide
2- si tu ajoutes ou enleve des éléments, il faut appeler distance(), plutôt que stocker les "positions" dans un champ supplémentaire de la map. Car leurs valeurs seront invalidées à chaque ajout/suppression d'élément.

Francois
17/02/2011, 15h41
jamsgoodon

Merci pour les réponses et désolé de la qualité de l'explication.

Merci d'avoir essayé de comprendre, et du coup ce que vous avez pensez, c'était bien ça la question. Je voulais stocker les "positions" (rang) des clefs : c'est à dire faire une map qui associe à chaque clef son rang.

Le but du jeu c'est de considérer toutes mes clefs 2 à 2 et chercher à savoir si (en terme de rang) elles se succèdent ou pas?
Dit autrement, voir les quelles clefs sont adjacents.

Sachant que les valeurs de mes clefs n'ont pas de structure uniforme.
La seule manière de savoir si elles se suivent est de chercher la valeur absolue |rang clef1 - rang clef2|. Si cette valeur absolue est égale à 1 les deux clef se succèdent sinon elle ne se succèdent pas.

Bon en tout cas merci!!
:ccool:
17/02/2011, 15h49
Invité

Citation:

Envoyé par jamsgoodon

Le but du jeu c'est de considérer toutes mes clefs 2 à 2 et chercher à savoir si (en terme de rang) elles se succèdent ou pas?

Dans ce cas, tout mettre dans une map n'est pas une solution efficace... Le mieux est alors de garder les données dans un vecteur, et de l'indexer. Pour cela, tu fabriques un tableau d'index (vector<int>, contenant les rangs de 0 à n-1), et tu le tries (via sort) avec une fonction de comparaison qui compare les éléments de l'index sur la base des clefs (clef[idx[i]]<clef[idx[j], un truc comme ca).

A la fin, tu as dans ton index le rang de chaque clef. C'est O(n lg n), donc nettement plus rapide que distance() (si sera quadratique)

Francois
17/02/2011, 18h30
koala01
Salut,

De plus, il faut bien être conscient du fait que, typiquement, une std::map est en réalité... un arbre binaire de recherche...

Cela implique que, bien que les différents éléments soient affichés dans l'ordre, et que tu peux accéder à une clé particulière avec les crochets ( lamap[cle] ), les objet apparaissant dans l'ordre sont loins d'être contigus en mémoire, comme ca peut être le cas pour un vecteur.

Ainsi, alors que tu as la certitude pour un vecteur qu'un code proche de

Code:

type data = *(le_vecteur + N);

est équivalent à un code du genre de

Code:

type data = le_vecteur[N];

tu ne peux absolument pas partir d'un préavis similaire avec la map :aie:

Il y a de fortes chances pour que, si tu venais à écrire un code proche de
Code:

1 2 3 type * ptr = &la_map[key]; ++ptr; /*...*/
ptr vienne à pointer... vers les marguerites dans lesquelles tu ne tardera pas à tomber ;)

Citation:

Envoyé par fcharton

Dans ce cas, tout mettre dans une map n'est pas une solution efficace... Le mieux est alors de garder les données dans un vecteur, et de l'indexer. Pour cela, tu fabriques un tableau d'index (vector<int>, contenant les rangs de 0 à n-1), et tu le tries (via sort) avec une fonction de comparaison qui compare les éléments de l'index sur la base des clefs (clef[idx[i]]<clef[idx[j], un truc comme ca).

A la fin, tu as dans ton index le rang de chaque clef. C'est O(n lg n), donc nettement plus rapide que distance() (si sera quadratique)

Francois

Bonjour, je n'ai pas tout compris du message.
Le vecteur que tu me proposes de faire doit contenir quoi? les clefs et leur rang?

j'ai fais une map qui marche pour l'instant.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
 
                                for(map<int, string>::iterator EspDmFamElement = EspDmFam ->second.begin(); EspDmFamElement != EspDmFam ->second.end(); ++EspDmFamElement)
                                {
                                      string espece = EspDmFam -> first; // espece;
                                      int debut_marqueur = EspDmFamElement -> first; // début_marqueur;
                                      fam = EspDmFamElement -> second; //famille
 
                                      //Test écriture;
                                      fichier3 << EspDmFam -> first;
                                      fichier3 <<" "<< debut_marqueur << " : ";
                                      fichier3 << EspDmFamElement -> second << endl;
 
                                       map<int, int> rangs; // creer map associant à chaque dm son rang : par espèce;
                                       rangs.insert (pair< int, int> (crang, EspDmFamElement-> first));
                                       fichier2 << espece << " le Dm " << EspDmFamElement -> first << " au rang " << crang <<" de la famille " << fam << endl;
                                       crang++;
 
}

Bonjour,

Ton approche via une map va fonctionner, c'est probablement la façon la plus simple de régler ton problème en utilisant les conteneurs de base de la STL.

La version la plus simple est probablement quelque chose comme
Code:

1 2 3 4 5 6 7 8 map<string,int> TableDesRangs; for(int i=0;i<NbClefs;i++) TableDesRangs.insert(make_pair(Clef[i],0)); // à ce stade tes clefs sont triées map<string,int>::iterator it; int nb=1; // si tes rangs commencent à 1 for(it=TableDesRangs.begin();it!=TableDesRangs.end();it++) it->second=nb++;
A ce stade TableDesRangs[clef] renvoie le rang de la clef (en base d'indice 1).

Cette approche a plusieurs défauts :

1- en insérant tes clefs dans une map, tu les tries, mais aussi tu construis un arbre de recherche binaire. Sur de grosses tables, ce n'est pas très efficace.
2- si tu as plusieurs clefs de tri, il te faut autant de map que de clefs, c'est lourd
3- pour trouver l'index d'une clef, il faut chercher dans la map, c'est logarithmique, mais ca peut ralentir (sur une table de mille clefs, ca fait 10 comparaisons par clef)
4- (celui que signale Koala) une map, c'est moins pratique à gérer qu'un vector.

L'approche par les index consiste à fabriquer un tableau qui te permet de retrouver le rang d'un élement de ta table d'origine. Dans la version usuelle, idx[0] te donne l'indice de la première clef, idx[1] l'indice de la seconde, etc... Il est alors facile de construire un tableau donnant les rangs, en faisant pour tout i

Code:

rang[idx[i]]=i;

Pour calculer l'index, c'est très simple, tu vas avoir quelque chose comme
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 vector<string> Clefs; // les clefs à indexer vector<int> idx; // ton tableau d'index // ceci va trier tes index dans l'ordre des clefs (c'est ça l'astuce) bool mycomp(const int &l,const int &r) { return Clefs[l]<Clefs[r]; } // initialiser idx for(int i=0;i<NbClefs;i++) idx[i]=i; // l'indexation sort(idx.begin(),idx.end(),mycomp);
Voila, pour parcourir ton tableau dans l'ordre des clefs, tu utilises Clefs[idx[i]].

L'intérêt c'est que tu peux facilement manipuler plusieurs clefs différentes, des critères de tris compliqués, et que si tu n'as pas besoin de récopier tes clefs dans une map.

Francois

Oui finalement, je vais utiliser les index, c'est claire que c'est mieux!
Cependant pour mes Clefs ce ne sont pas des strings, ce sont des entiers. J'ai essayé d'adapter ce que vous m'avez dit mais en remplissant le vecteur Clefs, je reçois un message d'erreur:

Code:

1
2
 
no matching function for call to ‘std::vector<int, std::allocator<int> >::insert(int&)’|

voici mon code sans les opérations. Je passerai aux opérations plustard.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
 
 for(map<string, map<int, string> >::iterator curEspece = FamillesTrieesParEspece.begin(); curEspece!= FamillesTrieesParEspece.end(); ++curEspece)
  {
 
                         for(map<int, string>::iterator it2 = curEspece ->second.begin(); it2 != curEspece->second.end(); ++it2)
                         {
 
                            int rang;
                            int i;
                            vector<int> Clefs; // les clefs à indexer
 
                            string espece = curEspece -> first;
                            int debut_marqueur = it2 -> first;
                            fichier3 << espece;
                            fichier3 <<" "<< debut_marqueur << " : ";
                            Clefs.insert(debut_marqueur);
                            vector<int> idx; // tableau d'index
                            rang[idx[i]]=i;
 
                        // ceci va trier tes index dans l'ordre des clefs (c'est ça l'astuce)
                        bool mycomp(const int &l,const int &r)
                        {
                        return Clefs[l]<Clefs[r];
                        }
 
                        // initialiser idx
                        for(int i=0;i<NbClefs;i++) idx[i]=i;
                        // l'indexation
                        sort(idx.begin(),idx.end(),mycomp);
 
 
                         }
 
 
                    }

Aussi pour mes map d ça marche bien.
Le seul souci c'est que ma map contient environ 14 000 clefs (1000 clef par espece, donc 14 especes) et le rang je ne le veux pas sur les 14 000 clefs. Mais je le veux plutôt pour chaque 1000 clefs associées à une des 14 espèces.

En espérant que c'est pas lourd à comprendre tout ce que je raconte là!
Merci d'avance.

D'ailleurs voici le code.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
 for(map<string, map<int, string> >::iterator curEspece = FamillesTrieesParEspece.begin(); curEspece!= FamillesTrieesParEspece.end(); ++curEspece)
                    {
map<int, int> LocalDm2Rang;
            string curEspeceName = curEspece -> first;
 
            uint rang = 0; // rang des Dm dans chaque espèce;
            for(map<int, string>::iterator curDm = curEspece ->second.begin(); curDm != curEspece ->second.end(); ++curDm){
 
            LocalDm2Rang.insert(pair< int, int> (curDm->first, rang));
            rang++;
 
            Dm2rangParEspece.insert(pair <string, map<int, int> > (curEspeceName , LocalDm2Rang));
 
            }
 
                //Afficher la map associant Espèce Dm et Rang.
                for(map<string, map<int, int> >::iterator it1 = Dm2rangParEspece.begin(); it1!= Dm2rangParEspece.end(); ++it1){
 
                    for(map<int, int>::iterator it2 = it1->second.begin(); it2 != it1->second.end(); ++it2){
 
                          fichier3 << it1 -> first;
                          fichier3 <<" "<< it2 -> first << " : ";
                          fichier3 << it2-> second << endl;
 
 
 
                    }
 
                }
 
 
      }

Re Bonjour,

Finalement y a tout qui marche!
Et j'ai vérifié les résultats c'est logique, donc je pense que le mieux sereait d'en rester là avec mes map de map, qui sont tout de même géniales.

Merci en tout cas!
Voici le bout de code!

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
for(map<string, map<int, string> >::iterator curEspece = FamillesTrieesParEspece.begin(); curEspece!= FamillesTrieesParEspece.end(); ++curEspece)
        {
            map<int, int> LocalDm2Rang;
            string curEspeceName = curEspece -> first;
            unsigned int rang=0; // rang des Dm dans chaque espèce;
           // cout << " mise à zéro" << rang << endl;
 
                for(map<int, string>::iterator curDm = curEspece ->second.begin(); curDm != curEspece ->second.end(); ++curDm){
                LocalDm2Rang.insert(pair< int, int> (curDm->first, rang));
                rang++;
                //cout << " Le rang est " << rang << endl;
                Dm2rangParEspece.insert(pair <string, map<int, int> > (curEspeceName , LocalDm2Rang));
 
                  fichier3 << curEspece -> first;
                  fichier3 <<" "<< curDm  -> first << " : ";
                  fichier3 << rang  << endl;
                }
 
        }