[STL] vector/list de structures, recherche d'elements de la structure

vector/list de structures, recherche d'elements de la structure [STL] - C++ - Programmation

Marsh Posté le 13-01-2003 à 12:14:58    

voila je veux faire un ptit prog en c++ pour manipuler des logs
 
 
pour simplifier, mes interrogations sont les suivantes
 
je pense que c'est possibles, avec les iterators ou autres, mais la stl est un peu complexe et si je sais utiliser un vecteur simple, les operations plus puissantes sont un peu compliquees
 
j'ai essaye de lire le cours de christian casteyde, mais c un peu chaud quand meme
 

Code :
  1. typedef struc { string User ; int Score ;} Log;
  2. vector<Log> MesLogs;


 
 
je voulais savoir comment rechercher directement si possible dans le vecteur, avec les fonctions de la stl, par exemple le n de la structure qui contient un User si je passe en argument un string (pour incrementer son score par exemple), quitte ensuite a utiliser des fonctions d'insertion, de tri ( ordre alphabetique, ou classement, etc...)
 
 
c'est pas les iterateurs ou un truc dans le genre qui permettent de faire ca ?
 
 
bref, ++Taz, et autres integristes du char * ;) bienvenus ;-)


Message édité par farib le 13-01-2003 à 12:40:53
Reply

Marsh Posté le 13-01-2003 à 12:14:58   

Reply

Marsh Posté le 13-01-2003 à 16:55:23    

Une suggestion : remplacer la structure par une classe (c++)
 
 
 

Code :
  1. class Log
  2. {
  3. private:
  4.    string User;
  5.    int Score;
  6. public:
  7. // accès aux éléments de la classe (méthodes publiques)
  8.    string GetUser(){ return User;}
  9.    int GetScore(){ return Score;}
  11.    PutUser( string AnotherUser ){ User = AnotherUser; }
  12.    PutScore( int NewScore ) { Score = NewScore; }
  13. };
  15. typedef vector<Log> vectorOfLog;
  16. typedef vector<Log>::iterator vectorOfLogIterator;

 
 
 
Sinon, pour l'algo de recherche :
exemple:
 
 

Code :
  1. vectorOfLog MyVector;
  2. vectorOfLogIterator it; // iterateur pour vectorOfLog
  4. // on passe xxx comme string (argument)
  5. for (it=MyVector.begin() ; it!=MyVector.end() ; it++)
  6. {
  7.    if ( (*it).GetUser() == xxxx)
  8.       (*it).PutScore( (*it).GetScore()+1 );
  10.    //[...]
  11. }
  12. // j'ai utilisé une boucle for mais utiliser une boucle while est meilleur ici (lorsque l'on a trouvé le User, on sort...)

 
 
A réfléchir  :D  
 
:hello:
 
kason


---------------
Seul le calme paisible d'un lac peut endiguer la force furieuse d'un torrent.
Reply

Marsh Posté le 13-01-2003 à 17:07:25    

merci de ta réponse
 
 
je me demandais plutot si c'était possible en fait d'utiliser l'algo
 
iterator find(key_type clef)  
 
tjrs avec ces hisoires d'itérateur (que je conceptualise pas tjrs tres bien, même si ton exempel m'éclaire tres bien , en + c génial de pouvoir incrémenter les itérateurs, qui s'incrément comme il faut :) ), plutot que mon (ton) pseudo algo de recherche,
 
et sans définir de classe
 
(par exemple, en passsant une sorte d'argument spécial a la fonction recherche, un itérateur subliminial, que sais-je....


Message édité par farib le 13-01-2003 à 17:08:18

---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 13-01-2003 à 18:42:57    

le code de std::find est trivial, mais puisqu'il existe déjà autant pas le retaper
 
 
 
petites corrections  

Code :
  1. // j'espere que y a un  
  2. using namespace std;
  4. class Log
  5.   {
  6.     private:
  7.        string User;
  8.        int Score;
  9.     public:
  10.     // accès aux éléments de la classe (méthodes publiques)
  11.        string GetUser(){ return User;}
  12.        int GetScore(){ return Score;}
  13.    
  14. // une const & c'est mieux       
  15. PutUser( const string &AnotherUser ){ User = AnotherUser; }
  16.        PutScore( int NewScore ) { Score = NewScore; }
  17.     // unconstructeur ne ferait pas de mal  
  18.     Log(const string &aUser, int aScore)
  19.      : User(aUser), Score(aScore)
  20.     {}
  21.   };
  22.  
  23.   typedef vector<Log> vectorOfLog;
  24.   //typedef vector<Log>::iterator vectorOfLogIterator;
  25.   // inutile
  28. vectorOfLog MyVector;
  29. vectorOfLog::iterator it; // iterateur pour vectorOfLog
  31. // on passe xxx comme string (argument)
  32. // mieux vaut ne calculer ::end() qu'une seule fois
  34. const vectorOfLog::iterator MyVector_end(MyVector.end());
  36. for (it=MyVector.begin() ; it!=MyVector_end ; ++it)
  37. // la préincrémentation est plus performante que la post, surtout pour les itérateur
  38. {
  39.   if ( (*it).GetUser() == xxxx)
  40. // ou it->
  41.      (*it).PutScore( (*it).GetScore()+1 );
  42. /* peut etre prévoir une méthode renvoyant une référence pour pouvoir ecrire simplement ++it->Score()
  44.   //[...]
  45. }


 
 
quant à ta question, à toi de définir operator== et operator< par la meme occasion (et tous les autres)
 
apres

Code :
  1. VectorOfLog::iterator result=std::find(MyVector.begin(), MyVector.end(), aLog);
  3. if (result!=MyVector.end())
  4. {
  5.   // trouvé!
  6. }


 
sinon, si tu veux rechercher un élément obéissant à une certaine regle, le mieux c'est de faire

Code :
  1. class VectorOfLogFinder
  2. {
  3.   const string User2find;
  4.  
  5.   public:
  7.   VectorOfLogFinder(const string &user)
  8.   : User2find(user)
  9.   {}
  10.  
  11.   bool operator()(const Log &log)
  12.   {
  13.      return log.GetUser()==User2find;
  14.   }
  15. };
  17. // et  
  19. VectorOfLogFinder tofind("xxxx" );
  21. VectorOfLog::iterator result=std::find_if(MyVector.begin(), MyVector.end(), tofind);
  23. // etc


 
ça devrait marcher


Message édité par Taz le 13-01-2003 à 18:47:58
Reply

Marsh Posté le 13-01-2003 à 18:54:27    

au fait: tes methodes "accessor" qui ne modifient pas l'objet doivent etre déclarer const
 
void MaClasse::fonction() const;

Reply

Marsh Posté le 13-01-2003 à 18:54:34    

un iterateur c'est une abstraction de pointeur (pour resumer)
ou plutot un pointeur c'est une implementation particuliere
d'un iterateur aleatoire.
 
Il y a quatre types d'iterateurs:
name ou reference: qui te permet de lire la valeur avec *
forward iterateur: qui te permet de lire la valeur avec *
et d'avancer dans ta structure avec ++.
bidirectional iterator: qui te permet de lire la valeur
avec * et d'avancer avec ++ et reculer dans ta structure avec --.
random iterator: qui te permet de lire la valeur avec * et d'avancer et reculer dans ta structure avec ++, -- ainsi que + n et - n.
Il manque une abstraction supplementaire qui permettrait d'avancer dans une structure en profondeur et en largeur mais peut-etre que ca existe je n'en sais pas plus :).
 
find te renvoie l'iterateur qui pointe sur la premiere occurrence de l'element que tu as passe en parametre. Evidemment il est sous-optimal pour un vector trie..
 
Ce que tu cherches a faire toi c'est plutot un map
donc autant utiliser la map existante:
map<string, int>
permet d'associer l'entier n a une chaine de caractere.
 
Si tu as une version adaptee de la STL (non standard)
tu peux utiliser une hash_map egalement.
 
LeGreg


Message édité par LeGreg le 13-01-2003 à 18:56:14
Reply

Marsh Posté le 13-01-2003 à 18:54:54    

Je prefere comme ça :
 

Code :
  1. struct EqualUser:
  2. std::binary_function<const Log &, const string &, bool>
  3. {
  4. bool operator()(const Log &log, const string & User2Find) const
  5. { 
  6.     return log.GetUser()==User2find;
  7. }
  8. };
  10. // et   
  12. VectorOfLog::iterator result=std::find(MyVector.begin(), MyVector.end(), bind2nd(EqualUser(),"xxx" ));


 
Mais faut connaitre l'utilisation de bind2nd et bind1st ;)
 
Edit : petite erreur d'ecriture


Message édité par Kristoph le 13-01-2003 à 19:00:27
Reply

Marsh Posté le 13-01-2003 à 18:55:22    

merci (de ta réponse )de vous réponses , mais je suis un peu dépassé la  
 
l'idée qui est la mienne serait plus proche d'une mini base de données
 
alors la je fais une classe MaFiche avec mes différents champs et méthodes, mais ensuite, mon esprit s'embrouille.... :pt1cable:


Message édité par farib le 13-01-2003 à 18:56:11

---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 13-01-2003 à 18:58:38    

si je comprend bien le find_if permet de passer l'argumetn regle pour la recherche ???


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 13-01-2003 à 18:59:09    

Kristoph a écrit :

Je prefere comme ça :
 

Code :
  1. struct EqualUser
  2. {
  3. bool operator()(const Log &log, const string & User2Find)
  4. { 
  5.     return log.GetUser()==User2find;
  6. }
  7. };
  9. // et   
  11. VectorOfLog::iterator result=std::find(MyVector.begin(), MyVector.end(), bind2nd(EqualUser(),"xxx" ));


 
Mais faut connaitre l'utilisation de bind2nd et bind1st ;)
 


 
find_if
 
mais l'ecriture est aussi courte ave cmon exemple
 
VectorOfLog::iterator result=std::find(MyVector.begin(), MyVector.end(), VectorOfLogFinder("xxxx" ))
 
 
le problème des bind, c'est que ça ne fonctionne que pour les fonctions binaires. si la recherche doit s'effectuer sur plus d'un critere, on est obligé de passer par un objet fonction comme j'ai montré

Reply

Marsh Posté le 13-01-2003 à 18:59:09   

Reply

Marsh Posté le 13-01-2003 à 18:59:53    

farib a écrit :

si je comprend bien le find_if permet de passer l'argumetn regle pour la recherche ???

oui, cet argument est un prédicat qui renvoie vrai si l'élément courant correspond au critere de recherche

Reply

Marsh Posté le 13-01-2003 à 19:02:11    

Code :
  1. // unconstructeur ne ferait pas de mal   
  2.         Log(const string &aUser, int aScore)
  3.          : User(aUser), Score(aScore)
  4.         {}

 
 
les deux pts c pour quoi faire déja  :??:  
 
(dsl, je repose ma question)


Message édité par farib le 13-01-2003 à 19:19:44

---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 13-01-2003 à 19:03:56    

c'est pour construire les membres. sinon, ils sont construit avec leur constructeur par défaut, puis  affecter dans le corps du constructeur, ce qui est bien plus couteux
 
 
edit: a pas peur
 
http://www.sgi.com/tech/stl/


Message édité par Taz le 13-01-2003 à 19:04:30
Reply

Marsh Posté le 13-01-2003 à 19:04:12    


Citation :

VectorOfLog::iterator result=std::find(MyVector.begin(), MyVector.end(), bind2nd(EqualUser(),"xxx" ));


 
tu voulais dire find_if non ;) ?
 
LeGreg
 

Reply

Marsh Posté le 13-01-2003 à 19:05:05    

legreg a écrit :


Citation :

VectorOfLog::iterator result=std::find(MyVector.begin(), MyVector.end(), bind2nd(EqualUser(),"xxx" ));


 
tu voulais dire find_if non ;) ?
 
LeGreg
 
 

toi t'es ultra grillaid

Reply

Marsh Posté le 13-01-2003 à 19:08:11    

++Taz a écrit :

c'est pour construire les membres. sinon, ils sont construit avec leur constructeur par défaut, puis  affecter dans le corps du constructeur, ce qui est bien plus couteux
 
 
edit: a pas peur
 
http://www.sgi.com/tech/stl/


 
chuis content, g fais venir tous les gros boss de c++  :sol:
 
donc pour effectuer une recherche, il convient de définir le critere de recherche, et également la regle de comparaison (operator =) mais pourquoi l'opérateur () ?


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 13-01-2003 à 19:10:32    

operator== c'est la comparaison et pas =
oui, il convient
 
voire les objets fonctions. le test est alors réalisé comme ça  
 
trucfinder("xxx" )
 
if(trucfinder(MyVector[0]))
 
qui n'est pas un constructeur mais operator()
 

Reply

Marsh Posté le 13-01-2003 à 19:20:04    

Code :
  1. // unconstructeur ne ferait pas de mal   
  2.         Log(const string &aUser, int aScore)
  3.          : User(aUser), Score(aScore)
  4.         {}

 
 
les deux pts c pour quoi faire déja  :??:  
 
(dsl, je repose ma question)


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 13-01-2003 à 19:24:47    

++Taz a écrit :

c'est pour construire les membres. sinon, ils sont construit avec leur constructeur par défaut, puis  affecter dans le corps du constructeur, ce qui est bien plus couteux

Reply

Marsh Posté le 13-01-2003 à 20:24:48    

enfin bon, la construction par défaut, la c juste une déclaration de int et string....   ;)


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 13-01-2003 à 21:57:11    

pour un int, peut etre pas, pour une string un peu moins: mais prenons un exemple.
 
 
on a un objet avec un constructeur par défaut, un constructeur par recopie et un opérateur d'affectation
 
- ta méthode:
  1) le constructeur par défaut alloue des ressources pour construire l'objet. ce n'est pas parce qu'il sagit d'un contructeur par défaut que l'objet construit est vide, loin de là.
  2) l'affectation: l'opérateur d'affectation doit nettoyer les ressources acquises par l'objet, puis en réallouer, et recopier (ou une autre opération selon) les données.
 
- ma méthode:
  1) le constructeur par recopie alloue les ressources nécessaires et effectue la copie de donnée
 
prends des bonnes habitudes.
 
d'autant plus qu'appeler les constructeurs est souvent indispensables.
 
taiste:  

Code :
  1. class Foo
  2. {
  3.   std::vector<int> vecteur;
  4. public:
  5. Foo();
  6. Foo(unsigned size, int init);
  7. };


 
implémentes moi ces 2 constructeurs: le par défaut donne à vecteur une taille de 100 éléments. le second, lui donne une taille de size éléments initialisés à init.
 
enjoy!
 

Reply

Marsh Posté le 13-01-2003 à 23:07:31    

et par défaut c de combien la taille d'un vector a sa création ?


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 07:10:25    

farib a écrit :

et par défaut c de combien la taille d'un vector a sa création ?

0, mais la je veux qu'à la sortie du constructeur il fasse soit 100 soit size  :sol:

Reply

Marsh Posté le 14-01-2003 à 08:01:54    

derniere série de question avant de mettre en application, si je veux utiliser les fonctions de tri de la STL sur ma structure/classe, ca marche un peu sur le même principe, il faut que je définisse mes critères de comparaison ?


Message édité par farib le 14-01-2003 à 08:13:32
Reply

Marsh Posté le 14-01-2003 à 10:35:09    

La valeur par defaut des fonctions de tri utilise l'opérateur < s'il est défini. Mais tu peux toujours passer en paramètre une fonction de comparaison custom.
 
Attention, tu dois passer une comparaison stricte "<" et non pas du type "<=".

Reply

Marsh Posté le 14-01-2003 à 14:29:38    

j'ai un pb avec find_if
 
 

Code :
  1. template <class InputIterator, class Predicate>
  2. InputIterator find_if(InputIterator premier, InputIterator dernier, Predicate p);

 
 
Si vous désirez effectuer une recherche sur un autre critère que l'égalité de valeur, vous devrez utiliser l'algorithme find_if. Celui-ci prend un prédicat en paramètre à la place de la valeur. C'est la valeur de ce prédicat, appliqué à l'élément courant dans le parcours des éléments de la séquence définie par les itérateurs premier et dernier, qui permettra de déterminer si cet élément est celui recherché ou non. La valeur retournée est l'itérateur dernier si aucun élément ne correspond au critère de recherche. La complexité de cet algorithme est linéaire en fonction du nombre d'éléments de la séquence d'éléments dans laquelle la recherche se fait.  
 
 
supair, et si le l'element trouvé est en derniere position on fait comment pour savoir s'il est trouvé ou si c'est la fin (g pas tt compris la :/)
 
a moisn que "dernier"  soit plsu un délimiteur que le dernier élément de mon vector (dans mon cas)


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 14:33:20    

C'est comme en C. Le premier est inclus et le dernier est exclus. En gros, v.end() correspond à un iterateur qui pointe juste après la fin du tableau. Mais v.begin() pointe vraiment sur le premier element du tableau.

Reply

Marsh Posté le 14-01-2003 à 14:48:38    

Code :
  1. $ g++ prog.cpp -o prog
  2. prog.cpp: In method `bool VectorOfLogFinder::operator ()(const Log &)':
  3. prog.cpp:44: passing `const Log' as `this' argument of `class string Log::GetUse
  4. r()' discards qualifiers


 
 
 

Code :
  1. class VectorOfLogFinder
  2. {
  3.   const string User2find;
  4.  
  5.   public:
  7.   VectorOfLogFinder(const string &user)
  8.   : User2find(user)
  9.   {}
  10.  
  11.   bool operator()(const Log &log)
  12.   {
  13.      return log.GetUser()==User2find;
  14.   }
  15. };
  17. // et  
  19. VectorOfLogFinder tofind("xxxx" );
  21. VectorOfLog::iterator result=std::find_if(MyVector.begin(), MyVector.end(), tofind);
  23. // etc


 
 
++Taz ! t mauvais  :ange:  :ange:  :ange: je comprend petit a petit, masi surement
 
 
blague a part, pkoi des passages par référence ?


Message édité par farib le 14-01-2003 à 15:04:07

---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 15:20:54    

arf, je dé-conste dans  

Code :
  1. bool operator()(const Log &log)


 
et ca compile   :heink:  :heink:


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 15:21:22    

++Taz a écrit :

au fait: tes methodes "accessor" qui ne modifient pas l'objet doivent etre déclarer const
 
void MaClasse::fonction() const;


 
si tu lisais tu n'aurais pas autant de problème. find_if travaille sur des objets constants, donc pas question d'executées de fonctions membre non-const, dou le problème avec Log::GetUse
r()
 
si tu y arrives pas j'ai ton exemple qui compile, demandes et je te maile
 
passé une const &, ça évite de passer une copie

Reply

Marsh Posté le 14-01-2003 à 15:33:20    

bah je retire le const dans ta déclaration de l'opérateur (), ca compile....


Message édité par farib le 14-01-2003 à 15:33:33

---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 15:36:00    

réparé, en effet, merci
 
 
pkoi utiliser encore en c++ des passages par non référence alors ?


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 15:49:02    

tout baigne, Da C++ P0w3r R0x0r


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 16:09:19    

Code :
  1. template <class RandomAccessIterator, class Compare>
  2. void sort(RandomAccessIterator premier, RandomAccessIterator dernier,
  3.     Compare c);

 
 
 
c c'est un pointeur de fonctrion ?
 
 
je fais

Code :
  1. bool Comparaison ( const Log & log1, const Log & log2)
  2. {return log1.GetScore() < log2.GetScore();}
  5. puis
  7. sort ( MyVector.begin(), MyVector.end(), Comparaison);

 
 
ca marche  :sol:  
 
je commence a capter
 
 
par contre, y'a t-il un moyen de faire la même chose, en surchargeant l'opérateur < ?


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 16:42:55    

farib a écrit :

bah je retire le const dans ta déclaration de l'opérateur (), ca compile....

:fou:  :fou:  :fou:  :fou:  :fou:  
 
pas la. il faut que tu en rajoutes un à tes fonctions observatrices  de Log (genre getuser, etc)
 
 
 :bounce:  :bounce:  :bounce:  :bounce:  :bounce:
 
edit: le "ça compile", evite ce genre de truc, sinon la prochaine fois que t'as un problème, je te donnerai seulement un truc qui "compile"  :D


Message édité par Taz le 14-01-2003 à 16:46:33
Reply

Marsh Posté le 14-01-2003 à 16:45:23    

farib a écrit :

tout baigne, Da C++ P0w3r R0x0r

va pas trop vite padawan
 
 
Compare c c'est pas un pointeur de fonction, c'est un argmuent de type de template. donc ca peut marcher avec une fonction mais surtout avec un un objet-fonction (functor, c'est à dire un objet qui implémentes l'operator())

Reply

Marsh Posté le 14-01-2003 à 16:51:09    

++Taz a écrit :

va pas trop vite padawan
 
 
Compare c c'est pas un pointeur de fonction, c'est un argmuent de type de template. donc ca peut marcher avec une fonction mais surtout avec un un objet-fonction (functor, c'est à dire un objet qui implémentes l'operator())


 
donc en surchargeant l'opérateur <


---------------
Bitcoin, Magical Thinking, and Political Ideology
Reply

Marsh Posté le 14-01-2003 à 16:51:38    

Faites un tour du cote de mem_fun ptr_fun et autres choses de ce genre dans la STL. C'set utilisé pour convertir des fonction "normales" en fonctions utilisables dans certaines parties plus exigentes de la STL.

Reply

Marsh Posté le 14-01-2003 à 16:54:52    

Kristoph a écrit :

Faites un tour du cote de mem_fun ptr_fun et autres choses de ce genre dans la STL. C'set utilisé pour convertir des fonction "normales" en fonctions utilisables dans certaines parties plus exigentes de la STL.

vas pas l'embrouiller

Reply

Marsh Posté le 14-01-2003 à 16:56:22    

farib a écrit :


 
donc en surchargeant l'opérateur <  

à ce moment la plus besoin de predicat. donc soit tu crées un prédicat, soit tu surcharge operator<.
 
si tu veux en discuter, contacte moi sur ICQ.
 
edit: je crois qu'avant de t'avancer dans STL tu devrais maitriser les templates et toutes les bases du langage, ça te rendra moins con (pas plus intelligent :D )et apres tu comprendras le fonctionnement de STL et son implémentation rapidement


Message édité par Taz le 14-01-2003 à 16:57:53
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed