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 ?
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 );
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.
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
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
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”
essaye en la déclarant statique sinon.
