> This is pretty slow. I'm sure dynamic_cast is required to be a fast
operation. Is it O(1)? How might one achieve this?
First of all, dynamic_cast usually _is_ relatively slow (though I've
never done enough testing to figure out whether/to what degree its
speed varies with inheritance depth and such).
As far as making things faster, at least a few things are usually
pretty easy: normally, all objects of a particular class (that has
virtual functions) share a single vtable. As such, finding whether two
objects are of the same class requires only comparing their vtable
pointers rather than retrieving and comparing type_info objects.
Pointers can normally be compared in a single operation, reducing this
to O(1) instead of O(N) on the type_info size.
I doubt anybody does a lot to minimize the time taken to traverse the
inheritance tree -- the typical expectation is that inheritance trees
are fairly shallow, and dynamic_casts are fairly rare. If you're
talking about 4 pointer comparisons happening once an hour, nothing you
do with it is going to make any noticeable difference in speed.
If you honestly had a good reason to do so, I'm pretty sure you could
do this with an expected complexity of O(1). Instead of walking the
list of vtable pointers, you'd create a hash-table indexed by the value
of the vtable pointer of the current class. The value it looked up
would be a boolean indicating whether that class could be converted to
the target type for the dynamic_cast.
If you were doing this in a lot of places, you could make it a
two-dimensional lookup, first looking up the table for a given target
type, then looking up the source pointer in that table to find whether
that particular conversion could take place.
As I said, however, I doubt anybody does this -- it would only make
sense if you expected many dynamic_casts, extremely deep inheritance
trees, or both. In fact, you pretty much expect neither.
--
Later,
Jerry.
The universe is a figment of its own imagination.