Forum Clubic

C++ tri sur un vector d'objet perso - utilisation de sort et vector

Bonjour :hello:

Voila ce que je voudrai faire :

j’ai un vecteur de structure.
Ma structure est defini par :
{ int i, double n}

je voudrai trier mon vecteur selon n, en utilisant le sort de la STL :
sort( mon_vecteur.begin(),mon_vecteur.end() )

il faut aussi savoir que je dois pouvoir representer l’infini dans n, et que mes valeurs ne peuvent qu’etre positives.
Pour le moment je represente l’infini par -1 mais pour le sort je ne veux pas que ces valeurs soient au debut.

Donc ma question est :

comment trier un vecteur (vector) de structure perso ?
comment gerer l’infini ?

merci

Tente unsigned double (pour être sur que ce soit non négatif, je crois que ça marche au moins sur les float). Et pour ta réponse, je crois que les double disposent d’une valeur spéciale représentant l’infini (INFINITY? voir google).

Pour ton tri, comme tu dois normalement implémenter ta propre fonction de tri (à passer au template de la fonction, je crois)

bool myfunction (Foo& a, Foo& b) {
  if (b.isInfinity()) return true; // a avant b
  if (a.isInfinity()) return false; // b après a
  return a.n < b.n;
}

sort(v.begin(), v.end(), myfunction );

cf. http://www.cplusplus.com/reference/algorithm/sort.html

'fin bref, l’idée est de définir une méthode ou autre indiquant que ton nombre n représente l’infini, et le faire passer “manuellement” à la fin.

merci je vais essayer ca :jap:

J’ai ptet une solution qui rejoint Sans-nom mais il faut transformer ta structure en classe:

class Perso{
public:
int i;
double n;

Perso(int _i,double _n):i(_i),n(_n){}

bool operator< (const Perso& x) {
	if (n==-1) return false;
	if (x.n==-1) return true;
    return n<x.n;
}

};

vector<Perso> v;
sort(v.begin(), v.end() );

j’ai un petit probleme :
sort(CC.begin(),CC.end(),compare);
CC c’est mon vecteur de classe et compare ma fonction perso.

compare est defini dans ma classe graphe (la ou je cree mon vecteur)
pour le moment je teste avec des entiers.

bool Graphe::compare(int& a, int& b) {

}

et ca me sort ca a la compil :


Graphe.cc:31: error: argument of type ‘bool (Graphe::)(int&, int&)’ does not match ‘bool (Graphe::*)(int&, int&)’

ligne 31 c’est quand j’ appel le sort.

Je comprends pas le Graphe::* dans le message d’erreur

Parce qu’il n’en veut pas de ta méthode :slight_smile: essaye en la déclarant statique sinon.

Normalement, si tu fais une classe c’est au choix :

  1. redéfinition de l’opérateur <, et pas de comparateur dans la fonction sort (ex de popolof)
  2. fonction comparateur (mon exemple)
  3. classe comparatrice : redéfinition de l’opérateur operator () (int, int) pour faire la même chose

Et sinon, je suis pas sûr, mais à priori const int& devrait aussi fonctionner (tu n’as pas lieu de modifier les valeurs).

oui mais je ne fait pas de classe, juste une structure dans une classe.
Et je veux definir ma fonction ou mon propre operateur de comparaison pour cette structure.
static ne change rien il ne veut pas de ma fonction.
Je l’ai declare dans private.

bon ca y est :
il fallait declarer la fonction static ET les deux variables const pour la fonction compare sinon ca ne compile pas.

Je n’avais pas essaye les deux a la fois.

Par contre en static je ne peux plus acceder a des variables qui font parties de ma classe graphe.

Ce n’est pas possible de faire ca?

Personne?
je voudrai faire mon tri en fonction de variables qui sont dans ma classe graphe (de la ou j’appel le tri).

et ces variables (ou propriétés) sont privées? ta solution passe peut être par les méthodes amies, ou par un changement de niveau des dîtes propriétés, ou en arnaquant le compilo d’une façon ou d’une autre.

j’y suis arrive en modifiant un peu la solution de popolof.
Mais je suis decu car c’est trop long le sort :stuck_out_tongue:

la caracteristique de mes donnees, c’est que j’en ai un tres grand nombre, et une petite partie seulement est modifie a chaque fois que je dois les retrier.

Alors je sais pas si le sort de algo_stl est adapte a mon cas…

En effet si une petite portion de ton vector est à trier c’est pas super…

2 solutions: Passer via une insertion triée: Parcourir le vecteur pour trouver le bon emplacement d’un item.

Oublier les std::vector, cette structure de donnée n’est qu’une liste générique et n’est pas vraiment efficace pour les opérations d’accés sur les données.
Il est possible de passer par un tableau natif genre Machin*, et d’utiliser les fonctions sort de la stl dessus (operateur [] bien plus efficace). Après si la taille de ce tableau n’est pas fixe, il est toujours possible d’allouer à l’avance un grand tableau ou alors utiliser les méthodes realloc (pas évident)

Après on ne connait pas trop ton cas de figure, si tu nous en dis un peu plus sur tes intentions on pourra t’aider plus justement.

pour expliquer bievement, j’a besoin de travailler sur des tres gros graphe (1 million de sommets)

Je voudrai connaitre la distance entre un point et tous les autres points.

Pour cela j’utilise l’algo de dijkstra.

Dans cet algo, j’ai la liste des sommets qui reste à visiter (mon vector, au début ils sont tous dedans), et a chaque etape je dois extraire un minimum (c’est ma donnée n) dans ce vecteur.
Quand je l’ai extraite je met a jour les sommets reliés a ce sommet, je le supprime de mon vecteur (d’ou l’utilisation d’un vecteur), puis je retrie mon vecteur vu que certains sommets ont étés mis a jour.

Au debut je parcourrai mon vecteur j’avais donc une complexité en O(n) pour extraire le minimum.
Je pensai qu’avec le sort je gagnerai du temps en prenant le premier élément du vecteur une fois le sort effectué, mais c’est plus lent qu’avant…

Un tri a une complexité en O(nlogn) donc c’est moins efficace qu’un parcours simple en O(n).

Pour poursuivre ton idée de tri, pour gagner en efficacité, tu fais un 1er tri lorsque tous les sommets sont dans le vecteur, et à chaque sommet modifié tu le déplace dans ton vecteur au bon endroit. (via itérateurs : fonctions erase & insert)

Mais cela dit, c’est pas évident que ce soit plus rapide :frowning:

ha oui autant pour moi je pensai que le tri etait en log n… :frowning:

donc je vais reflechir a ton idée, merci.

Bonjour,

je viens de passer à builder 6 et je ne retrouve pas la fonction sort pour les vector . J’ai bien indiqué comme dans le post using std:: vector et std::sort.
et j’ai ce message d’erreur “sort is not a member of std”

que faire?

Je vous remercie d’avance pour votre réponse.

Et là : www.cplusplus.com…

www.cplusplus.com…

Tu as bien inclut le bon header?.