 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Nicolas Aunai
Guest
|
 Posted: Sat Jan 03, 2004 2:34 pm Post subject: trier efficacement un vector avec la stl |
 |
|
salut,
j'ai un vector d'entier de dimension n, non trié. J'aimerai le trier
selon la relation d'ordre <, d'une manière efficace, tant au niveau du
nbre de lignes de codes, qu'au niveau complexité de l'algorithme.
J'ai donc pensé a la stl, comment pourrais-je donc faire ça ?
--
Nico,
http://astrosurf.com/nicoastro
messenger : [email]nicolas_aunai (AT) hotmail (DOT) com[/email]
|
|
| Back to top |
|
 |
Nicolas Aunai
Guest
|
| Posted: Sat Jan 03, 2004 4:08 pm Post subject: Re: trier efficacement un vector avec la stl |
|
|
bon, j'ai bidouillé un code... qu'en pensez-vous ?
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> a;
a.push_back(3);
a.push_back(45);
a.push_back(2);
a.push_back( ;
a.push_back(1);
a.push_back(12);
for(unsigned int i=0; i<a.size();i++)
cout << a[i] << " ";
cout << endl;
vector
for(i = a.begin(); i!=a.end(); i ++)
{
j=min_element(i,a.end());
iter_swap(i,j);
}
for(unsigned int i=0; i
cout << a[i] << " ";
cout << endl;
return 0;
}
--
Nico,
http://astrosurf.com/nicoastro
messenger : [email]nicolas_aunai (AT) hotmail (DOT) com[/email]
|
|
| Back to top |
|
|
Patrick Mézard
Guest
|
| Posted: Sat Jan 03, 2004 4:16 pm Post subject: Re: trier efficacement un vector avec la stl |
|
|
| Quote: | j'ai un vector d'entier de dimension n, non trié. J'aimerai le trier
selon la relation d'ordre <, d'une manière efficace, tant au niveau du
nbre de lignes de codes, qu'au niveau complexité de l'algorithme.
J'ai donc pensé a la stl, comment pourrais-je donc faire ça ?
|
Si tu veux trier tes entiers (en supposant que tu parles de types de base
comme int ou long) selon la relation < par défaut :
#include
#include <algorithm>
int main(int argc, char* argv[])
{
std::vector<int> v;
//Le vector est rempli ici d'une manière ou d'une autre
std::sort(v.begin(), v.end());
// Le tri est réalisé en place
// std::sort prend un troisième paramètre template permettant de redéfinir
la relation d'ordre.
// Par défaut, il s'agit d'un std::less qui exploite operator< du type à
trier s'il est défini.
}
Et pour plus de détails :
http://www.cuj.com/documents/s=7992/cujcexp1908austern/
Patrick Mézard
|
|
| Back to top |
|
|
Nicolas Aunai
Guest
|
| Posted: Sat Jan 03, 2004 4:25 pm Post subject: Re: trier efficacement un vector avec la stl |
|
|
Patrick Mézard a utilisé son clavier pour écrire :
| Quote: | j'ai un vector d'entier de dimension n, non trié. J'aimerai le trier
selon la relation d'ordre <, d'une manière efficace, tant au niveau du
nbre de lignes de codes, qu'au niveau complexité de l'algorithme.
J'ai donc pensé a la stl, comment pourrais-je donc faire ça ?
Si tu veux trier tes entiers (en supposant que tu parles de types de base
comme int ou long) selon la relation < par défaut :
#include
#include
int main(int argc, char* argv[])
{
std::vector
//Le vector est rempli ici d'une manière ou d'une autre
std::sort(v.begin(), v.end());
// Le tri est réalisé en place
// std::sort prend un troisième paramètre template permettant de redéfinir
la relation d'ordre.
// Par défaut, il s'agit d'un std::less qui exploite operator< du type à
trier s'il est défini.
}
Et pour plus de détails :
http://www.cuj.com/documents/s=7992/cujcexp1908austern/
Patrick Mézard
|
ah oui ok, merci bcp !!
--
Nico,
http://astrosurf.com/nicoastro
messenger : [email]nicolas_aunai (AT) hotmail (DOT) com[/email]
|
|
| Back to top |
|
|
Michel Michaud
Guest
|
| Posted: Sat Jan 03, 2004 5:34 pm Post subject: Re: trier efficacement un vector avec la stl |
|
|
Dans news:bt6pqi$top$1 (AT) news-reader1 (DOT) wanadoo.fr, Patrick
Mézard <patrick.mezard (AT) ifrance (DOT) com> a écrit :
| Quote: | // std::sort prend un troisième paramètre template permettant de
redéfinir la relation d'ordre.
// Par défaut, il s'agit d'un std::less qui exploite operator< du
type à trier s'il est défini.
|
Non, il y a deux fonctions sort. La première utilise directement
< et l'autre prend la relation d'ordre. Il n'y a pas de less
impliqué (c'était indiqué ainsi dans le livre de BS mais je lui
ai fait remarquer l'erreur qui est maintenant corrigée dans les
plus récentes versions de son livre). Tu peux vérifier en
faisant une fonction less sémantiquement différente de ta
fonction < pour un type : c'est le < qui sera utilisé.
Par ailleurs, il y a aussi une fonction stable_sort (deux en fait
pour permettre aussi de fournir l'ordre désiré) qui préserve
l'ordre des éléments qui sont égaux selon la comparaison, ce qui
est parfois utile.
--
Michel Michaud [email]mm (AT) gdzid (DOT) com[/email]
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
