Trier un vecteur selon le nombre d'occurence de ses éléments

Salut tout le monde,

Je dispose d'un vecteur d'entiers et je veux effectuer un tri selon le nombre d'occurrence de ces éléments.Par exemple le vecteur contient les éléments suivants:
<1,3,5,6,1,3,5,6,1,3,5,1,3,6,1,3,6>
On a donc:
5 occurences de 1
5 occurences de 3
3 occurences de 5
4 occurences de 6
Si on trouve deux occurrences égales,on tri selon le contenu de l'élément:ici le cas se présente avec 1 et 3.Donc l'ordre qu'on va suivre est 1,3,6,5
Ainsi le 1:première position,
3:deuxième position,
6:troisième position,
5:quatrième position
Le vecteur résultat sera comme suit:
<1,2,4,3,1,2,4,3,1,2,4,1,2,3,1,2,3>
je ne sais pas si je me suis bien expliquée mais je me trouve bloquée et je n'est pas su comment procéder.Merci d'avance

Salut,

Pas tout compris comment tu arrives à ce vector résultat, j'ai juste compris comment tu arrives à déduire que 1 est en première position etc...

Sinon pour ton problème, tu pourrais utiliser un conteneur associatif comme map, qui contiendrait les éléments de ton vector en tant que valeur clé, puis le nombre d'occurrences de celui-ci. Tu boucles sur tous les éléments de ton vector, si cet élément n'est pas déjà dans la map, tu l'ajoutes et tu initialises le nombre d'occurrences à 1, et s'il y est déjà, tu incrémentes simplement le nombre occurrence.

Ensuite tu reprends ta map, tu prends l'élément ayant le plus d'occurrences, tu l'ajoutes à ton vector résultat (push_back()), et ainsi de suite...

J'ai pas testé, c'est juste une idée qui m'ait passé par la tête, si elle peut être une piste tant mieux :)

Merci pour ta réponse mais je ne t'ai pas trop comprise.j'ai essayé d'utiliser le map mais je n'ai pas comment l'exploiter pour mon problème.
A propos du vecteur résultat ce que je fait c'est que par exemple pour le numéro "3" puisqu'il est en deuxième position dans le nombre d'occurrence,tout les "3" de mon vecteur initial deviennent "2" dans le vecteur initial.
Pour le numéro"6" puisqu'il est 3ème position,tout les "6" de mon vecteur initial deviennent "3" et ainsi de suite.stp explique moi encore plus ton idée elle parait intérenssante parce que je suis débutante en C++ et merci d'avance

Le conteneur map est un conteneur associatif, ça veut dire qu'il y a une valeur-clé associé à une autre valeur.
Cette valeur clé pourrait être un élément de ton vector, et la valeur associé le nombre d'occurrences.
Ainsi tu aurais pour chaque élément distincts de ton vector, le nombre d'occurrences.

Après cela, tu a toutes les informations nécessaires pour résoudre ton problème je pense :)

Si tu ne comprend toujours pas je te laisse te renseigner sur le conteneur map, mais là je dois partir et je re pas avant ce soir.

Bonne chance !

Salut,
Merci d'avoir répondu.J'ai essayé de suivre ta méthode mais j'y arrive pas.J'ai cherché de la doc sur les map mais je n'ai pas compris leurs fonctionnement.Je n'ai pas su comment accéder au éléments que j'ai stocké(cad comment je fais la différence entre les élément du vecteur et leur occurrence...).J'ai essayé de faire ça avec des vecteurs mais j'y arrive non plus.

Bonjour,
Bon, la solution n'est certes pas instantanée, mais avec un peu de méthode on y arrive.
Ma solution :
1)
D'abord on crée une structure qui contient toute les informations dont on aura besoin pour ordonner les éléments. Je n'ai pas beaucoup d'imagination, alors je l'ai nommé Info, mais on doit pouvoir trouver mieux.

Code:

---

1 2 3 4 5 6 7 8 9 10 11

struct Info { int value; // valeur de l'élément int occurrence; // nombre d'ocurrence de l'élément int position; // position que doit avoir l'élement à la fin du tri   // constructeur. On fait partir occurence et position à 1 pour // avoir une écriture comme en math Info(value):value(value), occurrence(1), position(1){} };

---

2) Ensuite on définit le type des deux objets que l'on va utiliser pour le tri. Une map pour relier un élément à l'information le concernant et un un vecteur que l'on pourra trier selon la méthode que tu as donné dans ton premier post.

Code:

---

1 2	typedef std::map<int, Info*> InfoMap; typedef std::vector<Info*> InfoVec;

---

A noter qu'Info* est un pointeur, pour pouvoir partager une Info entre la map et le vecteur.

3) On définit le prédicat de tri.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

bool SortByOccurrence(Info* info1, Info* info2) { if(info1->occurrence > info2->occurrence) { return true; } else if(info1->occurrence == info2->occurrence) { return info1->value < info2->value; } else { return false; } }

---

4) Une petite fonction d'aide pour visualiser ce qui se passe à chaque étape

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

void PrintInfo(InfoMap& infoMap) { for(InfoMap::iterator it = infoMap.begin(); it != infoMap.end() ; ++it) { Info* info = it->second; std::cout << " " << info->value << " " << info->occurrence << " " << info->position << std::endl; } std::cout << std::endl; }

---

5) La création de l'information attaché à chaque élément. C'est ce passage qu'il faut que tu examines soigneusement car il concentre les difficultés dans l'utilisation des map.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

void BuildInfo(InfoMap& map, InfoVec& vec, int value) { // cherche l'info pour cet élément InfoMap::iterator found = map.find(value); if(found == map.end()) // première fois qu'on rencontre l'élément { // on crée une nouvelle Info // par défaut le nombre d'occurence est un. Info* info = new Info(value); map[value] = info; vec.push_back(info); } else // l'élément a déjà été rencontré { // on récupère l'info attaché à cet élément Info* info = found->second;   // une occurence de plus. info->occurrence++; } }

---

5) Une fois qu'on a tout ça, le main est assez simple

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

int main() { int tab[] = { 1,3,5,6,1,3,5,6,1,3,5,1,3,6,1,3,6 }; std::vector<int> vec(tab, tab + 17); InfoMap infoMap; InfoVec infoVec;   for(unsigned int i = 0; i < vec.size() ; i++) { BuildInfo(infoMap, infoVec, vec[i]); }   PrintInfo(infoMap);   std::sort(infoVec.begin(), infoVec.end(), SortByOccurrence); for(unsigned int i = 0; i < infoVec.size(); i++) { infoVec[i]->position = i + 1; }   PrintInfo(infoMap);   return 0; }

---

Voilà ! Plus qu'à utiliser la map d'information pour construire le vecteur final et à nettoyer toutes les informations utilisées (avec des delete sur les pointeurs). Ce n'est surement pas la plus belle des implémentations, mais bon ça marche. :D

Merci énormément pour ta réponse précise.Je suis en train de le tester.Le compilateur me ramène une erreur au niveau de la déclaration

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

struct Info { int value; // valeur de l'élément int occurrence; // nombre d'ocurrence de l'élément int position; // position que doit avoir l'élement à la fin du tri   // constructeur. On fait partir occurence et position à 1 pour // avoir une écriture comme en math Info(value):value(value), occurrence(1), position(1){} }; Faut il enlever le constructeur ou quoi??

---

error C2629: unexpected 'struct Info ('

error C2334: unexpected token(s) preceding ':'; skipping apparent function body
Error executing cl.exe.

Oui, il y a une petite erreur :aie:

Code:

---

1 2 3 4 5 6 7 8 9 10

struct Info { int value; // valeur de l'élément int occurrence; // nombre d'ocurrence de l'élément int position; // position que doit avoir l'élement à la fin du tri // constructeur. On fait partir occurence et position à 1 pour // avoir une écriture comme en math Info(int value):value(value), occurrence(1), position(1){} };

---

C'est bizarre, j'ai pourtant fait un copier-coller direct depuis l'IDE...

Merciiiiiiiiiii c très gentil de ta part.Il me reste juste cette erreur au niveau de la fonction suivante :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

void BuildInfo(InfoMap& map, InfoVec& vec, int value) { // cherche l'info pour cet élément InfoMap::iterator found = map.find(value); if(found == map.end()) // première fois qu'on rencontre l'élément { // on crée une nouvelle Info // par défaut le nombre d'occurence est un. Info* info = new Info(value); map[value] = info; vec.push_back(info); } else // l'élément a déjà été rencontré { // on récupère l'info attaché à cet élément Info* info = found->second;   // une occurence de plus. info->occurrence++; } }

---

error C2955: 'map' : use of class template requires template argument list
c:\program files\microsoft visual studio\vc98\include\map(140) : see declaration of 'map'

Ben décidément... :aie:
Je ne comprends pas trop l'erreur "use of class template requires template argument list"

Deux hypothèses :
1) Tu as oublié d'inclure le header <map>
2) Le paramètre InfoMap& map entre en conflit avec les std::map classiques. Essaye de remplacer par InfoMap& infoMap. Ce n'était pas une très bonne idée d'appeler une variable "map" ou "vector" de toute façon.

Edit : chez moi, le code compile. :koi: (avec VS2008)

impeccable,ça marche!!!! merci vraiment un très grand merciiiiiiii