Discussion :

[hfranck]

Salut à tous,

voilà mon petit souci :
j'ai une grille composé de colonnes contenant des données de type différents :

Ex:
Libellé Montant Adresse [cette ligne correspond à l'entête de la grille]
Toto 150,00 avenue des ...
Titi 352,00 rue des ...
Tata 457,9 tour des ...
Tutu 24,5 avenue des ...

Lorsque je clique sur la colonne Libellé, je veux trier la colonne Libellé : Pas de problème, j'utilise l'algo QuickSort

Maintenant, je veux trier la colonne Montant, MAIS je dois conserver le tri déjà effectué sur la colonne Libellé.

Maintenant, je veux trier la colonne Adresse, MAIS je dois conserver le tri sur Montant et celui définie sur la colonne Libellé !!

Est-ce que quelqu'un a une petite idée sur la façon de réaliser ce code ??

Merci d'avance.

[Laurent Gomila]

Ne serait-ce pas un boulot pour boost::multi-index ?

PS : pour le tri, il y a std::sort.

[hfranck]

Salut, et merci de ta réponse.

boost::multi-index ???

si tu veux, le problème, je pense, ne se situe au niveau du tri de la première colonne, mais lorsque je vais trier la deuxième colonne, je ne vois pas trop comment gérer le truc.
J'ai récupérer un bout de code qui implémente le quicksort, et j'arrive à trier la première colonne sans soucis.

Par contre, lorsque je clique sur ma deuxième colonne, comment arriver à trier la deuxième tout en conservant la première triée ???

[Laurent Gomila]

C'est justement le but (je crois) de boost::multi_index : c'est un conteneur style tableau 2D, qui permet de trier selon plusieurs colonnes. As-tu suivi le lien que je t'ai donné ?

Et pour le tri, oublie donc ton QuickSort et utilise std::sort. Ce sera bien plus simple (1 ligne de code), plus rapide (le quick sort est loin d'être l'algo le plus performant), et plus robuste (ça fait partie de la bibliothèque standard).

[hfranck]

Effectivement, je n'ai pas regardé le lien.
Je vais y aller de ce pas, et te tiens au courant prochainement.

Merci.
A+

[hfranck]

Je viens de regarder un peu, et déjà ça me semble super compliqué.
De plus, je ne suis pas vraiment sure que ça implémente le tri !!

D'après ce que je comprends, c'est une espèce de hashtable avec les méthodes qui vont bien pour accéder aux élts rapidemment !
(Si j'ai compris !!!)

[JolyLoic]

Je ne pense pas en effet que boost::multi_index soit directement utilisable pour ça.

Si j'ai bien compris ton problème, le tout est comment trier les éléments quand il y a dess ex-aequos dans une colonne. Je vois deux voies de travail :

- Définir un objet de tri qui en cas d'égalité, va ensuite vérifier la colonne qui va bien. C'est un classique, par exemple pour trier une structure nom, prénom, à toi d'écrire pour que le code soit flexible en fonction des dernières colonnes de tri activées. On fait un code style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
bool f(S s1, S s2)
{
  if (s1.nom != s2.nom)
    return s1.nom<s2.nom;
  else
    return s1.prenom < s2.prenom;
}

- Utiliser un algorithme qui je change pas l'ordre des éléments équivalents, à savoir stable_sort, et non sort.

[hfranck]

Pas tout a fait en fait.

J'arrive à trier la première colonne
Par contre, lorsque je dois trier la seconde, il faut que je trie la seconde, mais en gardant le tri de la première. Si tu veux, c'est comme si tu faisait un order by.
Soit A la première colonne, soit B la deuxième : Tu sélectionne ta première colonne, ça fait un order by colonne_A, et si tu sélectionne la deuxième, ça va faire un order by colonne_B, colonne_A.

Et c'est cette difficulté que je n'arrive pas à voir comme coder.

Peut être que ta réponse expliquait plus ou moins, dans ce cas là, je n'ai pas compris ce que tu voulais dire !!!

[Médinoc]

Ah, j'ai eu cette discussion il n'y a pas un mois avec mon prof de système...

Le problème, c'est que la plupart des fonctions de tri sont basés sur des permutations, qui se préoccupent peu de l'ordre des doublons (éléments dont la valeur critère est identique)

Ce qu'il te faut, c'est trouver ou développer une fonction de tri qui conserve l'ordre des doublons (s'il faut un décalage pour cela, on trie généralement un tableau de pointeurs vers les objets à trier)

Là, tu pourras l'appeler sans problème pour trier successivement selon les différents critères

Edit: Ah, je n'avais pas vu que JolyLoic avait déjà répondu la même chose...

[hfranck]

Je ne vois pas trop ce que tu veux dire par doublons

[Médinoc]

struct element { int a, b ; }

struct element tab[] = {{1, 2}, {1, 3}, {2, 6}, {2, 1}}

Si tu tries selon b, il n'y aura pas de doublons (tous les éléments ont des valeurs différentes pour b)

Si tu tries selon a, tu auras deux paires de doublons ({1, 2}, {1, 3} seront des doublons car ils ont la même valeur pour a, et il en est de même pour {2, 0}, {2, 1})

L'important pour trier selon plusieurs critères, c'est que l'ordre des doublons ne soit pas modifié

Edit: Doublons, c'est ce que JolyLoic appelle "éléments équivalents"

[hfranck]

Avec ton exemple, je viens de comprendre un peu mieux le soucis que je pouvais rencontrer.

Je vais donc me lancer dans ce truc.
Merci de ton aide.

[JolyLoic]

Après avoir relu tes précisions, je pense que les deux solutions que j'ai proposée correspondent bien à ce problème. La solution avec fonction de tri spécifique correspond à expliciter tes order_by, la solution avec stable_sort (et non pas partial_sort, qui fait autre chose est que j'avais écrit ici par erreur) permet de conserver tout ordre préalable en cas de doublons, éventuellement aussi un ordre qu'aurait manuellement déterminé un utilisateur.

Pourrais-tu me dire quels points te gênent dans mes propositions ?

[hfranck]

Salut,
escuses, je pense que j'ai du mal m'exprimer.
Quand je dis :

Avec ton exemple, je viens de comprendre un peu mieux le soucis que je pouvais rencontrer.

je voulais dire que je venais de comprendre le problème auquel je pouvais être confronté avec le tri de plusieurs colonnes, et tes propositions s'adaptent totalement à cette configuration.

Par contre, je ne vois pas trop ce que tu veux dire par partial_sort ? C'est quoi au juste comme truc ?

Merci pour ton aide.

[Médinoc]

Si j'ai bien compris, stable_sort() est justement une fonction de tri qui ne change pas l'ordre des doublons.

Donc, si tu appelles cette fonction successivement avec deux comparateurs différents (on va dire d'abord sur le champ "prénom", puis le champ "nom"), tu auras un résultat du style:

COVER Harry
DUPONDT Dominique
DUPONDT Théophile
DURAND Domonique
DURAND Harry
HICIER Paul
HOCHON Bid
HOCHON Paul

Le classement le plus récent étant le classement principal.

[JolyLoic]

Mes doigts ont fourché, je parle juste de std::stable_sort, c'est un algorithme standard du C++ défini dans le header <algorithm>.

[Luc Hermitte]

Si j'ai bien compris, stable_sort() est justement une fonction de tri qui ne change pas l'ordre des doublons.

Si tu connais parfaitement ton ordre de tri, c'est pas super efficace comme approche.

Définis ton foncteur de comparaison qui compare suivant le champs42 d'abord, puis le 12 si lhs.c42 == rhs.c42, puis le 3 si si les champs 42 et 12 sont identiques, ...
Cf la FAQ et un bout de code précédemment donné par Loïc.

L'intérêt du stable sort, ce va surtout être pour des tables qui présentent plusieurs champs, afin que le gars qui manipule l'IHM puisse commander des réodonnancements à la main.