Discussion :

[camboui]

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")

[jblecanard]

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

[camboui]

Non, l'affirmative suffit
Merci !

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

Code :

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

1
2
3
4
5
typedef unsigned char byte;
 
byte b;
...
byte inverted_b=0xFF-b;

ou

Code :

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

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.

[jblecanard]

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

[camboui]

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.

[camboui]

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 ?
Merci.