Comparison functions for qsort() and bsearch()

[Barry Margolin]

In article <WARSAW.90Dec26104259 at warsaw.nlm.nih.gov> warsaw at nlm.nih.gov writes:
>	barmar> The problem is that C++ has restrictions on casting from
>	barmar> void* into <type>*.
>Specifically, what are these restrictions?

A week or so ago someone mentioned in this list that there is a problem
such conversions and multiple inheritance.  However, I can't find any
mention of it in the "C++ Primer".

I think the problem he described was when a class D is derived from B1 and
B2, and you have the following declarations:

	B1* b1p;
	B2* b2p;
	D* dp;
	void* vp;

	vp = (void*) dp;// OK, explicit cast is optional
	dp = (D*) vp;	// OK, requires explicit cast
	b1p = (B1*) vp; // ??
	b2p = (B2*) vp; // ??

One of the last two conversions is questionable because it requires the
pointer to be offset to the beginning of the appropriate base portion of
the object.  However, the offset depends on the actual type of the object
that vp is pointing to.  Casting back to the type from which the void* was
cast is easy, but casting to a base class effectively requires a virtual
function call, and it's not clear that this is done automatically.

This comes up because the comparison function may be designed to compare
objects of a base class, so it will presumably first cast its void*
argument to a <base>* and then do whatever it does.

Actually, there *is* a solution.  The routine that casts to void* (the
caller of the qsort-like function) can first cast to the appropriate
<base>*, e.g.

	vp = (void*) ((B1*) dp);
	b1p = (B1*) vp;

This works because C++ always knows how to convert a derived pointer to any
of its base class pointers.  However, it's really inconvenient for the
kinds of functions we're discussing (qsort() and bsearch()) because it
doesn't allow arrays/trees to be operated on in place; the caller must
build a second array/tree containing void* pointers whose values come from
the above double cast, pass this to the function, and then cast the results
back to the original types.

--
Barry Margolin, Thinking Machines Corp.

barmar at think.com
{uunet,harvard}!think!barmar