Réordonner un vector

Version imprimable

15/07/2009, 18h29
Nikolai

Réordonner un vector

Bonjour,

j'essaie actuellement de compter le nombre déléments égaux dans un vector, qui contient des coordonnées (selon l'axe y, j'essaie donc de déterminer le nombre d'éléments par ligne). J'ai réussi à le faire pour le vector contenant les coordonnées selon X car les éléments étaient ordonnés, mais dans ce cas actuels ils ne le sont pas.

donc je me suis dit que je pouvais réordonner mon vector pour revenir au cas précédent. mais je ne sais pas du tout comment y parvenir. avez vous une idée? merci!
15/07/2009, 18h34
Pragmateek

La fonction "sort" prend en troisième argument un prédicat qu'elle utilise pour trier la séquence fournie.
Tu y définis ta logique de comparaison, ici la comparaison des coordonnées y.
15/07/2009, 20h20
Invité
Si ton vecteur est assez gros et a pas mal d'élements dupliqués, tu peux le faire sans trier (le problème de sort, c'est qu'il va modifier l'ordre de ton vecteur, ce qui peut être gênant).

Pour cela, tu insères les éléments de ton vecteur dans un set<> dont tu prends ensuite la taille... Tu vas donc avoir quelque chose comme ca
Code:

1 2 3 4 5 6 vector<int> v(n); // v(n) sont tes données set<int> s; s.insert(v.begin(),v.end()); int nbvals=s.size();
ou si tu es dans un tableau dynamique
Code:

1 2 3 4 5 6 int *v=new int[n]; // v(n) sont tes données set<int> s; s.insert(v,v+n); int nbvals=s.size();
Et bien sur, je prends ici des int, mais ca marche avec tous les types.

Francois
16/07/2009, 10h31
Nikolai
merci :)
donc le set insère lui meme les éléments dans le bon ordre.
et est-ce que je peux écrire :
Code:

1 2 3 4 5 6 7 8 9 10 11 int j=0; Size_C[0]=1; for (int i = 1; i < C1.size(); ++i) { if (st[i-1] != st[i]) j++; Size_C[j] += 1; }
cela marche avec des vectors, mais est-ce que cela marche avec des sets?

Salut,

Citation:

Envoyé par fcharton

Si ton vecteur est assez gros et a pas mal d'élements dupliqués, tu peux le faire sans trier (le problème de sort, c'est qu'il va modifier l'ordre de ton vecteur, ce qui peut être gênant).

Là dessus, je suis d'accord, mais

Citation:

Pour cela, tu insères les éléments de ton vecteur dans un set<> dont tu prends ensuite la taille... Tu vas donc avoir quelque chose comme ca

Attention, le set ne va assurer l'unicité des éléments équivalents...

NOTA:On parle d'équivalence parce que le set n'utilise pas l'égalité pour évaluer si deux éléments sont identique, mais bien une logique basée sur:

Citation:

Si a n'est pas plus petit que b et que b n'est pas plus petit que a, c'est qu'ils sont équivalents

Ainsi, avec un code (simplifié au maximum) proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 int main() { vector<int> tab; for(int i=0;i<10;++i) for(int j=0;j<i;++j) tab.push_back(i); set<int> s(tab.begin(),tab.end()); cout<<"taille du tableau : "<<tab.size()<<endl <<"taille du set : "<<s.size(); return 0; }
tu obtiendra le résultat:
Code:

1 2 taille du tableau : 45 taille du set : 9
parce que l'unicité aidant, alors qu'il y a normalement 9 éléments de valeur 9 dans le vector, il n'y en a plus... qu'un dans le set :aie:

Cela complique fortement les choses si le but est de compter les occurrences multiples :aie:

Il faut donc au minimum utiliser le multiset, qui trie les éléments, mais qui accepte des occurences multiples.

De plus, les logiques de tri utilisent de préférence l'opérateur < (ou le foncteur less) pour travailler...

Si ton vecteur est dores et déjà trié, et que tu as déjà utilisé sort pour ce faire, il faudra que tu crées un foncteur supplémentaire pour permettre le tri, non plus sur les X, mais sur les y, et que tu précise à ton set que tu souhaites utiliser ce foncteur particulier...
Si donc tu as une structure (ou une classe) point qui permet le tri sur les x par défaut proche de
Code:

1 2 3 4 5 6 7 8 struct point { int x; int y; point(int x,int y):x(x),y(y){} /*suffisant pour le tri en fonction des x */ bool operator<(point const& p)const{return x<p.x;} };
il te faudra un foncteur proche de
Code:

1 2 3 4 5 struct lessByY { bool operator()(point const & p1, point const & p2) const{return p1.y<p2.y;} };
(qui devra le cas échéant être déclarée amie de la classe point, ou utiliser l'accesseur sur y, si x et y sont privés)
qui te permettra d'envisager un code proche de
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 int main() { vector<point> tab; for(int i=0;i<10;++i) for(int j=0;j<10;++j) tab.push_back(point(i,j)); /* tab est "naturellement" trié sur les x, du fait de la logique * "rectiligne" de remplissage de mon tableau, * mais nous pouvons malgré tout nous assurer le tri rapide des éléments * sur base des x avec */ multiset<point> s(tab.begin(),tab.end()); /* d'ailleurs, l'affichage le confirme */ cout<<"affichons les elements tries selon les x :"<<endl; for(multiset<point>::iterator it=s.begin();it!=s.end();++it) cout<<(*it).x<<","<<(*it).y<<"\t"; cout<<endl<<endl; /* si nous voulons obtenir un tri basé sur les y, nous devrons utiliser */ multiset<point,lessByY> s2(tab.begin(),tab.end()); /* et l'affichage est la pour nous confirmer que ca s'est bien passé */ cout<<"affichons les elements tries selons les y :"<<endl; for(multiset<point>::iterator it=s2.begin();it!=s2.end();++it) cout<<(*it).x<<","<<(*it).y<<"\t"; return 0; }
qui donnera le résultat suivant
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 affichons les elements tries selon les x : 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8 2,9 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8 3,9 4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8 4,9 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8 5,9 6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8 6,9 7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8 7,9 8,0 8,1 8,2 8,3 8,4 8,5 8,6 8,7 8,8 8,9 9,0 9,1 9,2 9,3 9,4 9,5 9,6 9,7 9,8 9,9 affichons les elements tries selons les y : 0,0 1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 0,1 1,1 2,1 3,1 4,1 5,1 6,1 7,1 8,1 9,1 0,2 1,2 2,2 3,2 4,2 5,2 6,2 7,2 8,2 9,2 0,3 1,3 2,3 3,3 4,3 5,3 6,3 7,3 8,3 9,3 0,4 1,4 2,4 3,4 4,4 5,4 6,4 7,4 8,4 9,4 0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 8,5 9,5 0,6 1,6 2,6 3,6 4,6 5,6 6,6 7,6 8,6 9,6 0,7 1,7 2,7 3,7 4,7 5,7 6,7 7,7 8,7 9,7 0,8 1,8 2,8 3,8 4,8 5,8 6,8 7,8 8,8 9,8 0,9 1,9 2,9 3,9 4,9 5,9 6,9 7,9 8,9 9,9

wahou :)

sinon ca c marche bien aussi :) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
 
 map<double, int> Size_C1;
    for(size_t i=0, size=C1.size(); i<size; ++i)
        {
        Size_C1[C1[i]]++;
        }
 
 
    map<double, int>::iterator iter1, fin1;
    iter1 = Size_C1.begin();
 
    int *Size_C= new int[Size_C1.size()];
     for(int i = 0; i < Size_C1.size(); i++)
            {
                Size_C[i] = iter1->second;
                ++iter1;
            }

16/07/2009, 11h57
koala01

Citation:

Envoyé par Nikolai

wahou :)

sinon ca c marche bien aussi :) :
<sniped code>

Attention, la std::map subit les même restriction que le std::set en ce qui concerne la clé...

La clé est, par définition, unique (évaluée sur base de l'équivalence expliquée plus haut), et, si tu remplis ta map au départ d'un conteneur ayant des occurrences multiples, tu aura exactement le même problème...

En plus, je suis de ceux qui, considèrent la post incrémentation comme une aberration du langage, même si j'admet qu'elle peut avoir un impact positif sur le binaire final... Mais ca, c'est un autre débat ;)

Citation:

Envoyé par Nikolai

Bonjour,

j'essaie actuellement de compter le nombre déléments égaux dans un vector, qui contient des coordonnées (selon l'axe y, j'essaie donc de déterminer le nombre d'éléments par ligne).

Il suffit donc de faire quelque chose du style:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
/* On pourrait utiliser un vector ce qui est pratique si les lignes sont proches les unes des autres */
map<int, size_t> occurences;
 
for (vector<point>::const_iterator it = v.begin(); it != v.end(); ++it)
{
     occurences[it->y] += 1;
}
 
for(map<int,size_t>::iterator it = occurences.begin(); it != occurences.end(); ++it)
{
    cout << "Nombre d'éléments à la ligne " << it->first << " : " << it->second << "." << endl;
}

Après si on veut savoir quels sont les éléments répétés on peut faire une multimap:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* Le premier élément correspond à y, le deuxième à x */
multimap<int, int> occurences;
 
for (vector<point>::const_iterator it = v.begin(); it != v.end(); ++it)
{
     occurences.insert(pair<int,int>(it->y, it->x));
}
 
for(multimap<int,int>::iterator it = occurences.begin(); it != occurences.end(); )
{
    cout << "Nombre d'éléments à la ligne " << it->first << " : " << occurences.count(it->first) << "." << endl;
    for (int i = occurences.count(it->first); i > 0; ++it, --i)
        cout << "\ty: " << it->first << " x: " << it->second << endl;
}

16/07/2009, 14h39
Invité

Oui, faut juste être certain que, dans le type que tu utilises, a==b <=> !(a<b || b<a)...

C'est vérifié pour tous les types intégraux... (je soupconne que c'était la question d'origine, et c'est en tout cas l'exemple que je donne). Si tu redéfinis ton opérateur de comparaison, ca dépend de toi, mais il vaudrait mieux le garantir : permettre, via une surcharge d'opérateur, que certaines propriétés mathématiques que l'on tient pour évidentes soient fausses, c'est se préparer bien des déconvenues...

Enfin bon, le C++ permet de rédéfinir l'addition comme la division et la soustraction comme la multiplication, si l'on veut... Aucun langage n'est idiot-proof...

Francois
16/07/2009, 15h58
koala01

Citation:

Envoyé par fcharton

Oui, faut juste être certain que, dans le type que tu utilises, a==b <=> !(a<b || b<a)...

C'est vérifié pour tous les types intégraux...

ce qui laisse encore des problème pour les types décimaux ;)

De plus, le fonctionnement de std:: (multi) set est basé sur le fait que la clé servant au tri est... l'objet que l'on souhaite trier...

Or, lorsque l'on crée une structure, même si on n'envisage que des type intégraux (ou pouvant passer pour comme les std::string) et un tri basé sur un membre unique, on peut souhaiter plusieurs classements...

Nous devrons alors d'office préciser l'ordre de tri "officiel", qui sera, selon toutes vraisemblances, utilisé par défaut, mais aussi les autres possibilités ;)

Citation:

(je soupconne que c'était la question d'origine, et c'est en tout cas l'exemple que je donne).

Justement, non : notre ami ici présent parle de trier des coordonnées une fois par rapport à l'axe des x et une fois par rapport à l'axe des y, il semble "cohérent" de penser que ce qu'il cherche à trier c'est... des structures regroupant ces deux valeurs ;)

Citation:

Si tu redéfinis ton opérateur de comparaison, ca dépend de toi, mais il vaudrait mieux le garantir : permettre, via une surcharge d'opérateur, que certaines propriétés mathématiques que l'on tient pour évidentes soient fausses, c'est se préparer bien des déconvenues...

Dés que tu envisage un classement quelconque sur une structure, tu n'a pas vraiment le choix ;)

Parce que, pour classer des structures, tu es obligé de les comparer, et donc de savoir comment effectuer ces comparaison ;)

Citation:

Enfin bon, le C++ permet de rédéfinir l'addition comme la division et la soustraction comme la multiplication, si l'on veut... Aucun langage n'est idiot-proof...

Sur ce point, par contre, nous sommes bien d'accord ;)
16/07/2009, 19h39
Invité

Citation:

Envoyé par koala01

ce qui laisse encore des problème pour les types décimaux ;)

Je ne vois pas ce dont tu parles ...

Sur les types prédéfinis, ou de la base :

1- ca marche pour un int (ou toutes ses variantes)
2- ca marche pour un float (ou un double)
3- ca marche pour un pointeur
4- ca marche pour une chaine de caractères
5- ça marche pour une paire des types précédent, ou même des POD définis à partir des types différents...

Et bien sur, ca va marcher sur des "projections de paires", c'est à dire des opérateurs définis sur des paires (x,y), comme x1<x2 et x1==x2, (ou le même sur y), ce qui est le cas qui nous intéresse ici...

Citation:

Envoyé par koala01

Justement, non : notre ami ici présent parle de trier des coordonnées une fois par rapport à l'axe des x et une fois par rapport à l'axe des y, il semble "cohérent" de penser que ce qu'il cherche à trier c'est... des structures regroupant ces deux valeurs ;)

Et alors? un operateur défini par p.x<q.x (sur une structure de paires) vérifie bien la propriété pour l'égalité p.x==q.x... Non?

Suppose que tu travailles sur une donnée contenant deux membres, x et y.

Pour trier ton fichier par coordonnée, il te faut définir une fonction de comparaison (sur chaque coordonnée). Puis, pour calculer des différences, il va te falloir définir un operateur d'égalité. Deux opérateurs, et un processus n log n, donc, avec deux réarrangements des données de départ à la clef...

Pour mettre tes données dans un set, tu vas devoir définir une fonction de comparaison sur chaque coordonnée (la même que la précédente), et c'est tout... Et tes données de départ ne bougent pas.

Je ne vois pas le problème. Sinon que le premier cas demande davantage de code, et tournera probablement plus lentement...

Citation:

Envoyé par koala01

Parce que, pour classer des structures, tu es obligé de les comparer, et donc de savoir comment effectuer ces comparaison ;)

Justement, non?

Francois

Citation:

Envoyé par fcharton

2- ca marche pour un float (ou un double)

Justement, pour les réels (float, double et long double), cela peut ne pas marcher du fait qu'il y a toujours le problème de la précision qui fait que la comparaison entre deux valeurs décimale n'est jamais juste (surtout si l'une de ces valeurs est calculée ;))

Pour les autres, je suis d'accord ;)

Citation:

Et bien sur, ca va marcher sur des "projections de paires", c'est à dire des opérateurs définis sur des paires (x,y), comme x1<x2 et x1==x2, (ou le même sur y), ce qui est le cas qui nous intéresse ici...

Et non...

Tu peux, effectivement, dire que deux objets sont égaux si l'ensemble de leurs membres sont égaux...

Par contre, du fait que les algorithmes utilisent l'équivalence, tu peux très bien avoir deux objets considérés comme équivalents alors que l'ensemble de leurs membres ne sont pas égaux.

La raison est finalement relativement simple:

Si tu as une structure pour laquelle tu ne teste qu'un seul membre pour évaluer le résultat de l'opérateur plus petit que, il suffit que ce membre particulier soit identique dans les deux objets testés pour que les deux objets soient considérés comme équivalents...

Cela signifie que, sur une structure proche de
Code:

1 2 3 4 5 struct Personne { std::string nom; std::string prenom; };
si tu te contente de tester le nom sous la forme de
Code:

1 2 3 4 bool Personne::operator< (Personne const& p) const { return nom<p.nom; };
les algorithmes de la SL en arriveront à la conclusion que Durant André et Durant Noémie sont équivalents...

Si tu te base sur le fait qu'ils sont équivalents pour dire qu'ils sont égaux, tu risque de te faire frapper par André ou par Noémie, parce qu'il (ou elle) ne supportera pas d'être confondu(e) avec son frère ou sa soeur ;)

Et si tu te contente de vérifier le prénom, Durant André risque de ne pas être ravi d'être confondu avec Dupont André ;)

Pour assurer l'unicité des données, tu dois donc, au minimum "améliorer" ton opérateur de comparaison "plus petit que"...

Par exemple sous la forme de
Code:

1 2 3 4 5 6 7 8 bool Personne::operator< (Personne const& p) const { std::string me(nom); me+=prenom; std::string other(p.nom); other+=p.prenom; return me<other; };
Citation:

Et alors? un operateur défini par p.x<q.x (sur une structure de paires) vérifie bien la propriété pour l'égalité p.x==p.y... Non?

ca vérifie bien l'égalité p.x==q.x... mais absolument pas l'égalité potentielle (qui nous intéresse peut être ailleurs) p==q ;)

Citation:

Suppose que tu travailles sur une donnée contenant deux membres, x et y.

Pour trier ton fichier par coordonnée, il te faut définir une fonction de comparaison (sur chaque coordonnée). Puis, pour calculer des différences, il va te falloir définir un operateur d'égalité. Deux opérateurs, et un processus n log n, donc.

Pour trier ton fichier par coordonnée, il va te falloir la logique nécessaire qui permette la comparaison "plus petit que" sur l'ensemble de la structure, qui peut ne pas être simplement le résultat de la comparaison des x avec les x et des y avec les y, et le tout, si possible, en évitant les collisions...

Parce que, si tu crée ton opérateur de comparaison sous la forme (pour une structure point disposant de x et y, tous deux étant des entiers) de
Code:

1 2 3 4 bool point::operator<(point const & p) { return x*x+y==(p.x*p.x+p.y); }
tu aura une collision déjà avec
Code:

1 2 3 4 p1.x=0; p1.y=3; p2.x=1; p2.y=2;
Après, qu'il te faille d'autres opérateurs pour d'autres raisons est une autre paire de manche qui n'entre pas en ligne de compte ici ;)

Citation:

Pour mettre tes données dans un set, tu vas devoir définir une fonction de comparaison sur chaque coordonnée (la même que la précédente), et c'est tout...

Tu va devoir définir une fonction de comparaison pour chaque critère de tri que tu voudra utiliser

Car, si une structure contient deux données, tu as minimum six critères de tri potentiels:
croissant sur la première
croissant sur la deuxième
croissant sur l'ensemble ( !!! attention au risque de collision dans la logique !!! )
décroissant sur la première
décroissant sur la deuxième
décroissant sur l'ensemble ( !!! attention au risque de collision dans la logique !!! )
(et je te fais grâce des critères plus évolués sur l'ensemble ;))

Tous les critères de tri ne seront pas forcément intéressants / utiles ni même utilisés, mais, si tu décide d'utiliser un critère, tu es obligé de définir la fonction de comparaison qui va bien ;)

Ce n'est pas les données qui bougent, mais la logique qui entre en oeuvre pour effectuer la comparaison ;)

Citation:

Je ne vois pas le problème. Sinon que le premier cas demande davantage de code, et tournera probablement plus lentement...

Si tu n'adapte pas la logique de comparaison au critère qui t'intéresse, tu n'obtiendra pas tes objets triés dans l'ordre qui t'intéresse, tout simplement ;)

Citation:

Pire encore, je ne crois pas que la méthode de déduplication fondée sur un tri puisse fonctionner si l'opérateur de comparaison utilisé pour le tri ne vérifie pas la propriété x==y <=> !(x<y || y<x)... (je n'ai pas vérifié le détail, mais je suis presque sur que je peux te le démontrer...)

[/QUOTE]
C'est justement parce que je viens de te démontrer que deux objets évalués (selon une logique peut être trop restreinte ou inadaptée) comme étant équivalent peuvent parfaitement ne pas être égaux qu'il faut attirer l'attention sur le fait que les (multi) set et les (multi) map utilisent l'équivalence et non l'égalité pour effectuer leurs insertions...

Et, quand on sait que ce qui sous-tend les set et les map sont des arbres binaires, on comprend assez facilement pourquoi il en est ainsi: la méthode d'insertion suit en effet une logique proche de
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 if (a->value<this->value) { if(this->left) { this->left->insert(a); } else { this->left =a; } }else if(this->value <a->value) { if(this->rigth) { this->right->insert(a) } else { this->rigth=a; } } else this->value=a->value;
Citation:

Justement, non?

Justement, tu dois savoir comment les comparer selon le critère décidé...

Si le critère choisi change, la logique à appliquer change également ;)

Et c'est bien là tout le problème de Nikolai ;)

16/07/2009, 21h28
Invité

Citation:

Envoyé par koala01

Justement, pour les réels (float, double et long double), cela peut ne pas marcher du fait qu'il y a toujours le problème de la précision qui fait que la comparaison entre deux valeurs décimale n'est jamais juste (surtout si l'une de ces valeurs est calculée ;))

Tu veux dire que pour deux flottants on peut avoir (Edité) !(x<y || y<x) sans avoir x==y ? Je ne le crois pas, mais je suis à l'écoute de ton contre exemple...

La représentation en virgule flottante, c'est un problème différent, qui pose des difficultés particulières (notamment le fait que les opérations usuelles ne sont pas toujours associatives et commutatives, et que, donc, certaines comparaisons ou égalités n'ont pas les propriétés normales de ces opérateurs). Mais elle n'a rien à voir avec la situation présente (en fait, toutes les méthodes 'basiques' de recherches d'égaux échoueront dans ce cas, ne serait ce que parce que des nombres réels différents peuvent avoir la même représentation flottante).

Citation:

Envoyé par koala01

Par contre, du fait que les algorithmes utilisent l'équivalence, tu peux très bien avoir deux objets considérés comme équivalents alors que l'ensemble de leurs membres ne sont pas égaux.

Je comprends ceci, ce que je conteste c'est l'applicabilité d'une méthode tri+déduplication (par égalité stricte), dans le cas ou l'opérateur de comparaison ne vérifie pas la propriété usuelle d'équivalence (cad le fait qu'équivalence vale égalité).

Ce que j'essaie de te dire, c'est que, quel que soit le problème posé (et je ne crois pas que tu fasses une lecture correcte de la question de départ, mais bon), si tu veux utiliser, pour éliminer (ou repérer) des éléments égaux une méthode consistant à les trier, puis à parcourir le vecteur trié à la recherche d'éléments (contigus, sinon à quoi bon les trier) égaux, alors l'opérateur que tu utilises dans ton tri doit vérifier la propriété d'équivalence...

En d'autres mots, si ce que tu veux faire c'est

1- trier tes données (selon l'opérateur d'inégalité de ton choix)
2- parcourir le vecteur trié
3- comparer chaque élément à son successeur (selon l'opérateur d'égalité de ton choix)

Pour que cette méthode repère les doublons, il faut absolument que deux éléments égaux (au sens de l'égalité), soient contigus dans le vecteur trié. La condition d'équivalence (x==y)<=> !(x<y || y<x) garantit cela (elle n'est pas nécessaire : tu auras le même effet si ta condition d'équivalence est plus "forte" que ta condition d'égalité, mais je douterais qu'une telle situation se présente en pratique, et de toutes façons, dans ce cas, on 'affaiblirait' l'opérateur de comparaison).

En revanche, si on n'a pas équivalence=égalité, la méthode ne marchera pas.

Par exemple, sur le jeu de données suivant

(1,1)
(1,3)
(2,1)
(1,2)
(1,3)

Si tu tries sur la première coordonnée, mais que l'égalité est définie sur les 2 (cas non équivalent) tu peut avoir, après tri

(1,1)
(1,3)
(1,2)
(1,3)
(2,1)

et tu ne vas pas trouver ton doublon avec la méthode de recherche séquentielle (qui est la raison d'être de ce tri).

Mais, inversement, si cette méthode implique que l'équivalence et l'égalité doivent être identiques, alors, la méthode des set<> ou des map<> fonctionnera...

En d'autres mots, indépendamment de la solution technique choisie (sets, ou tris), la méthode proposée ici pour dédoublonner présuppose cette équivalence .

A titre personnel, j'aurais tendance, pour toutes les classes utilisateurs où la notion d'ordre a une importance, à forcer, par définition operator== à valoir !(x<y || y<x), cela évite toute mauvaise surprise...

Francois

(Edité : formule d'équivalene cf post de GL si dessous...)
16/07/2009, 22h03
coyotte507

Dans ce cas précis, on demande le nombre d'éléments par ligne (cf post original) donc on considère égalité si point1.y == point2.y même si point1.x != point2.x.

Le code de koala trie tous les éléments selon y (bon d'accord après c'est plus facile de compter le nombre d'éléments par ligne) et celui de fcharton le nombre de lignes différentes ou le surplus d'éléments (mais c'est vrai le PO n'était pas très explicite au début de son poste, il faut regarder bien caché dans les parenthèses)

Donc vous n'avez pas de raisons d'argumenter, d'autant qu'on ne parle pas de doublons exacts mais plutôt d'éléments sur une même ligne :mouarf:
17/07/2009, 21h14
Kalith
Citation:

Envoyé par fcharton

Tu veux dire que pour deux flottants on peut avoir (Edité) !(x<y || y<x) sans avoir x==y ? Je ne le crois pas, mais je suis à l'écoute de ton contre exemple...

Si x et/ou y sont NaN ;)
Code:

1 2 3 4 5 float x = 0.0f/0.0f; float y = 2.0f; cout << (x == y) << endl; cout << !(x<y || y<x) << endl;
17/07/2009, 21h41
Invité

NaN (not a number) est il un flottant, ou seulement un nombre ?

Francois
17/07/2009, 21h49
Kalith

Citation:

Envoyé par fcharton

NaN (not a number) est il un flottant ?

Mathématiquement non. Mais étant donné qu'on peut le stoker dans un float... C'est une (des ?) valeur(s) qui ne vérifie pas l'équivalence dont vous parliez.
17/07/2009, 22h15
Invité

Je ne sais pas, j'ai un peu tendance à le considérer comme une "valeur d'erreur". La seule chose qu'on puisse en faire, c'est constater sa présence et renvoyer une erreur.

Ce qui est sur, c'est que si l'on autorise des nan à etre présents dans le tableau, je ne crois pas que quoi que ce soit fonctionne (on ne peut plus trier, par exemple, car pour tout x on va avoir x < NaN et Nan<x...)

Francois