Inverser l'ordre lexicographique

Supposons qu'une string soit la clé pour définir l'ordre d'une structure quelconque.
Pour inverser cet ordre suffit-il d'inverser tous les bits de chaque octet de la string ?

Intuitivement je pense que oui, mais il y a un soucis quand une string est la sous-string d'une autre:
"a" < "ab"
mais
not("a") < not("ab") [alors qu'on voudrait not("ab") < not("a")]

Pour que cela puisse être généralisable il suffit me semble-t-il d'ajouter l'octet nul à la fin (qui deviendrait '\xFF' après inversion de ses bits):
"a\0" < "ab\0"
not("ab\0") < not("a\0")

Yes on dirait bien que tu as raison. Tu cherches une preuve mathématique ?

Non, l'affirmative suffit :ccool:
Merci !

Il me reste à trouver le calcul optimal pour le faire:

Code:

---

1 2 3 4 5

typedef unsigned char byte;   byte b; ... byte inverted_b=0xFF-b;

---

ou

Code:

---

byte inverted_b=b^0xFF;

---

Le deuxième code fait gagner quelques octets sur le code machine, et peut-être quelques nanosecondes à l'exécution.

Et ce serait pas plus rapide de simplement changer la callback de comparaison plutôt que d'inverser toutes les clés ?

Lorsqu'on a accès à la callback, oui bien sûr.

En dehors d'un contexte C/C++ je me posais cette simple question de logique.

Bon, je précise un peu plus le contexte.

Je fais un petit prg qui lit des fichiers textes. Ces fichiers sont des tables de données dont chaque ligne est un enregistrement, les champs étant séparés par des tabulations. Rien que du très classique donc.
L'output du prg est un fichier équivalent dont les lignes sont triés suivant certains critères.
Ces critères de tri sont définis dans une sorte de script. Exemple, trier suivant les champs 2 puis 5 puis 1, en considérant que 2 est un entier non signé, 5 un entier signé, et 1 une string (éventuellement à normaliser). Il pourrait aussi y avoir des dates ou des nombres non entiers (des flottants quoi), et l'ordre pourrait être montant ou descendant.

Il n'y a qu'une seule "callback" dans le prg, mais elle doit gérer n'importe quel cas au runtime.
Je vois deux approches.
Dans la première, la callback gère une structure contenant un vector de variant (ou de boost::any) et en fonction du type effectue la comparaison ad-hoc élément par élément.
Dans la deuxième, la callback ne gère qu'une chaine d'octet et fait un memcmp dessus, sans plus. En amount cette chaine est construite une seule fois par enregistrement de sorte à ce qu'elle soit lexicographiquement ordonnable en fonction des critères. C'est simple pour des entiers par exemple qu'il suffit d'arranger en big endian dans la chaine, ou pour des string que l'on arrange en UTF8.

Voilà, vos avis ? :zoubi:
Merci.

Salut !

Je pense que ça dépend de ce que tu privilégies : la pérennité et l'extensibilité, ou bien les performances.

Dans le 1er cas, je prendrais la 1ère approche, ça te permettrait en plus de gérer d'autres types si tu en as besoin.

Dans le 2ème cas, la seconde, quoiqu'il faut encore voir ce que te coûte la construction des clés comparée au coût du tri.

La deuxieme approche est classique. Par exemple voir strxfrm() dans C90 qui effectue la transformation necessaire pour faire un ordre lexicographique correct pour la locale (En passant, les locales sous Unix utilisent pour la plupart la norme ISO14651 definissant comment trier les chaines -- en gros l'ordre du dictionnaire sauf que la norme ne tient pas compte de regles semantiques telles que celle qui rassemblent les souverains de meme nom d'un pays donne -- qui est disponible gratuitement: http://standards.iso.org/ittf/Public...ableStandards/)