Trouver max et min dans un vecteur

Version imprimable

06/05/2009, 11h43
Elstak

Trouver max et min dans un vecteur
Bonjour,

voici mon vecteur actuel :
Code:

1 2 3 4 for(std::vector<Hara *>::iterator it = vectExt->begin(); it!=vectExt->end();it++) { fichierApprent << (*it)->param1<< ... << (*it)->paramx<<std::endl; }
il contient plusieurs objets de type Hara, un objet Hara a plusieur parametre et je cherche à trouver le min et le max de chaque param... j'ai vu les fonctions min et max mais je n'arrive pas concretement à écrire le code qui conviendrait...

ce serait un truc du style (je pense):

Code:

std::min(std::vector<HaralickVecteur *>::begin(),std::vector<HaralickVecteur *>::end());

mais pour chacun des parametres... au final je voudrais avoir :

Code:

float MinParam1 = std::min(hara->Param1);

j'espère être clair. Merci d'avance

EDIT: je pense que min et max font juste une comparaison pour renvoyer le min ou le max de 2 valeurs, mais n'existe t-il pas une autre fonction pour trouver le min/max d'un vecteur (en utilisant les itérateurs peut etre...) ?
06/05/2009, 12h14
Arzar

Bonjour,
La fonction que tu cherches se nomme std::max_element.

Edit : Tiens ! Dans le prochain standard, on aura aussi droit à std::minmax_element, qui renverra une paire d'itérateur sur le min et le max. Chouette.

Salut,

Si tu as plusieurs valeurs à comparer, n'oublie pas qu'il faudra prévoir un foncteur pour chaque valeur...

Par exemple, pour une structure du type de

Code:

1
2
3
4
5
6
struct MyStruct
{
    int x;
    int y;
    int z;
};

il faudra prévoir les foncteurs sous la forme de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct lessX
{
    bool operator()(Mystruct const& s1, MyStruct const& s2) const
    {return s1.x<s2.x;}
};
struct lessY
{
    bool operator()(Mystruct const& s1, MyStruct const& s2) const
    {return s1.y<s2.y;}
};
struct lessZ
{
    bool operator()(Mystruct const& s1, MyStruct const& s2) const
    {return s1.z<s2.z;}
};

et utiliser la fonctionmax_element sous la forme de

Code:

1
2
3
std::max_element(collection.begin(),collection.end(),lessX); /* pour max X */
std::max_element(collection.begin(),collection.end(),lessY); /* pour max Y */
std::max_element(collection.begin(),collection.end(),lessZ); /* pour max Z */

ok merci beaucoup pour le code. J'aurais une autre question.

Est que ca vaut le coup d'utiliser ces fonctions (std::max_element...) car apparemment, je devrai créer beaucoup de structures intermédiaires et j'ai 9 paramètres donc je dois faire 9 struct Less et 9 Struct More?

Ma question est, réellement est-ce que ca donne un gain de temps ou si je fais un code dans ce genre :
Code:

1 2 3 4 5 6 7 //j'initialise avant mes valeurs de chaque param avec la première valeur du vector for(std::vector<HaralickVecteur *>::iterator it = vectInt->begin(); it!=vectInt->end();it++) { if((*it)->param1 < plusPetitParam1) plusPetitParam1 = param1; //etc... }
ca donnera un temps de calcul du meme ordre?

Salut,
Une solution est de passer par boost pour faire un bind :

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
37
 
#include <vector>
#include <functional>
#include <algorithm>
#include <boost/bind.hpp>
 
struct A
{
   A(int i1,int i2,int i3,int i4,int i5)
      :m1(i1),m2(i2),m3(i3),m4(i4),m5(i5)
   {}
   int m1;
   int m2;
   int m3;
   int m4;
   int m5;
};
 
 
 
int main()
{
   std::vector<A> vect;
   vect.push_back(A(1,2,3,4,5));
   vect.push_back(A(2,3,4,5,1));
   vect.push_back(A(3,4,5,1,2));
   vect.push_back(A(4,5,1,2,3));
   vect.push_back(A(5,1,2,3,4));
   std::min_element (vect.begin(),vect.end(),
      boost::bind(
         std::less<int>(),
         boost::bind(&A::m1,_1),
         boost::bind(&A::m1,_2)
      )
   );
   return 1;
}

06/05/2009, 17h11
Elstak

ok merci,

donc ca répond à mon problème de longueur de code, mais au niveau rapidité, quelqu'un pourrait me dire si utiliser les fonctions de STL est plus rapide que de faire les test soit meme comme je l'ai proposé au dessus?
06/05/2009, 17h13
3DArchi

Je crois que oui. Il me semble qu'il existe une telle discussion sur le forum. Fais une recherche?
06/05/2009, 17h25
Elstak

ok merci bien ;)
06/05/2009, 17h28
koala01

En théorie, les fonctions de la STL qui manipulent des intervalles n'ont aucune raison d'être ni plus ni moins rapide qu'une implémentation de l'algorithme équivalent...

Après tout, l'implémentation de ces fonctions a de fortes chances d'être identique que l'implémentation "personnelle" que tu pourrais faire du même algorithme (modulo la gestion du "problème" des templates, qui intervient principalement à la compilation, et ne modifie donc pas le temps d'exécution ;))

Mais la question à 2 cents est de savoir si ton implémentation utilisera "le meilleur algorithme", alors que tu peux estimer que, avec tout le monde qui scrute les algorithmes de la STL depuis si longtemps, il sera difficile de trouver meilleur ;)

De plus, surtout à l'heure actuelle, je ne rappellerai jamais assez que la première qualité d'un code doit être la facilité de lecture et de compréhension, suivie de très près par l'utilisation efficiente de l'existant...

Il faut avouer que, de ce point de vue, l'utilisation des fonctions qui manipulent des intervalles ont un avantage certains par rapport à une implémentation personnalisée ;) (ne serait-ce qu'en nombre d'instructions pour arriver au résultat ;))
06/05/2009, 17h42
JolyLoic

Il y a des chances que trouver 9 éléments minimaux selon des critères différents en une seule passe soit plus efficace que trouver 9 fois un élément minimal selon un critère à chaque fois différent.

Après tout, c'est pour ce genre de raison qu'une fonction retournant en une seule passe le min et le max existe.

Donc, oui, en général, les algorithmes de la STL sont très bien faits, mais là, si j'ai bien compris, tu ne veux pas faire ce que fais la STL, mais autre chose, et tu as peut-être un gain à le faire toi même.
06/05/2009, 17h58
Arzar

D'un autre coté, généralement quand on a besoin de min/max sur un vecteur d'Objet* alors les std::sort et autres std::lower_bound ne sont jamais bien loin...

Si oui, alors les structures Less pourraient être réutilisées assez fréquement. (D'ailleurs pas besoin de structure "more", les algos de la STL ne prennent que des fonctions de comparaison "inférieur à")

Par contre, s'il faut récupèrer les 9 minimums en une seule passe, alors une boucle à la main est effectivement beaucoup plus appropriée.
08/05/2009, 12h57
koala01

Citation:

Envoyé par Arzar

D'un autre coté, généralement quand on a besoin de min/max sur un vecteur d'Objet* alors les std::sort et autres std::lower_bound ne sont jamais bien loin...

Si oui, alors les structures Less pourraient être réutilisées assez fréquement. (D'ailleurs pas besoin de structure "more", les algos de la STL ne prennent que des fonctions de comparaison "inférieur à")

Par contre, s'il faut récupèrer les 9 minimums en une seule passe, alors une boucle à la main est effectivement beaucoup plus appropriée.

Dans le même genre d'idées, je me demande si, en fonction de l'utilisation des données que Elstak prévois de faire, il ne serait pas intéressant d'envisager l'utilisation de tulpes ( associée à boost::bind / tr1::bind) et / ou de boost::multi_index...

Cela n'évitera pas forcément le problème de la création de foncteurs appropriés, mais présenterait certainement un avantage certain à l'exécution, et principalement à la recherche des éléments ;)