Est-ce que quelqu'un sait comment la fonction de recherche binaire standard est implémentée?Comment la fonction bsearch() dans la bibliothèque C standard est-elle implémentée?
Ceci est le prototype.
void * bsearch (const void*, const void*, size_t, size_t, int (*) (const void *, const void *));
Je suis vraiment curieux de savoir comment ils ont utilisé des pointeurs vides.
Je suppose que vous êtes intéressé à savoir comment void * pointeurs sont utilisés dans bsearch, plutôt que l'algorithme de recherche binaire réel lui-même. Le prototype de bsearch est:
void *bsearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
Ici, void * est utilisé de manière à pouvoir rechercher tout type arbitraire. L'interprétation des pointeurs est effectuée par la fonction compar fournie par l'utilisateur.
Depuis le pointeur base points au début d'un tableau, et les éléments d'un tableau sont garantis contigus, bsearch peut obtenir un pointeur void * à l'un des nmemb éléments du tableau en faisant l'arithmétique des pointeurs. Par exemple, pour obtenir un pointeur vers le cinquième élément du tableau (en supposant nmemb >= 5):
unsigned char *base_p = base;
size_t n = 5;
/* Go 5 elements after base */
unsigned char *curr = base_p + size*n;
/* curr now points to the 5th element of the array.
Moreover, we can pass curr as the first or the second parameter
to 'compar', because of implicit and legal conversion of curr to void *
in the call */
Dans l'extrait ci-dessus, nous ne pouvions pas ajouter size*n directement à base parce qu'il est de type void *, et l'arithmétique sur void * n'est pas défini.
Je ne pense pas que cette astuce est autorisée par la norme. –
@Dave: De quelle partie parlez-vous? –
La conversion de (void *) en (char *). De toute façon, j'ai vérifié et c'est autorisé. Je vous remercie. –
Regardez la source. Si vous avez VS Standard ou mieux, voir:
C: \ Program Files \ Microsoft Visual Studio 8 \ VC \ crt \ src \ bsearch.c
Voir bsearch @ Google's codesearch pour différentes implémentations de bsearch.
Attention au code en accord avec GCC - qui traite 'void *' comme équivalent à 'char *' pour les adresses de calcul, alors que le standard C dit que vous ne pouvez pas faire d'arithmétique d'adresse sur les valeurs 'void *'. –
@Jonathan: Je ne sais pas comment GCC intervient dans ce domaine; le prototype qu'il a listé (le seul endroit "void *" est mentionné dans la question) est tout droit sorti de la norme C99. –
Je crois que le commentaire de Jonathan portait sur une implémentation de 'bsearch' s'appuyant sur l'arithmétique sur' void * '. Une implémentation portable (c'est-à-dire une implémentation conforme à la norme elle-même) ne peut pas le faire. –