Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!att!cbnewsl!cbnewsk!pegasus!hansen
From: hansen@pegasus.att.com (Tony L. Hansen)
Newsgroups: comp.lang.c++
Subject: Re: Comparison functions for qsort() and bsearch()
Summary: the proper way to use qsort() & bsearch() in C++
Keywords: Sun, C++
Message-ID: <1991Jan6.045740.20458@cbnewsk.att.com>
Date: 6 Jan 91 04:57:40 GMT
References: <3069@lupine.NCD.COM> <277640DD.4A70@tct.uucp> <1990Dec26.160636.15566@clear.com>
Sender: hansen@cbnewsk.att.com (tony.l.hansen)
Organization: AT&T Bell Laboratories
Lines: 47

Lest everyone gets lost in the discussions on what's good and bad with
qsort()'s (and bsearch()'s) definition, I'm going to iterate here the proper
way to use qsort() which avoids all problems on all machine types and works
everywhere:

    o	First off, the proper prototypes are:

	void *bsearch(const void*key, const void *base,
	    size_t nmemb, size_t size,
	    int (*compar)(const void*, const void*));

	void qsort(void *base, size_t nmemb, size_t size,
	    int (*compar)(const void*, const void*));

	These functions are required to be declared within <stdlib.h>.
	This is from Section 4.10.5.1 and 4.10.5.2 of the ANSI C standard,
	which is also a base document for the draft ANSI C++.

    o	For a given type T of which an array is being searched or sorted,
	the comparison function must be declared:

	int Tcomparison(const void *a, const void *b)
	{
	    const T *Ta = (const T*)a;
	    const T *Tb = (const T*)b;
	    // now do whatever you want to compare *Ta and *Tb
	}

    o	Note that the type cast MUST be to type T and not to any base class
	of T. (This is particularly a requirement when T is multiply
	inherited.) After casting to T*, you may THEN cast to a base class of
	T if you wish, but you can't go directly to that base class from the
	void*.

Once templates become available, it will be possible to create a template
version of qsort() which looks something like this:

	template <class T>
	void qsort(T *base, size_t nmemb, int (*compar)(const T*, const T*));

(It should even be possible to implement the template qsort() using the void*
version.)

					Tony Hansen
				att!pegasus!hansen, attmail!tony
				    hansen@pegasus.att.com
				      tony@attmail.com